Page 40 - Bkhargava_-_Grokaem_algoritmy

Шпаргалка 39

Какой ужасный алгоритм! Значит, коммивояжер должен найти другое
решение, верно? Но у него ничего не получится. Это одна из знаменитых
нерешенных задач в области теории вычислений. Для нее не существует
известного быстрого алгоритма, и ученые считают, что найти более эф­
фективный алгоритм для этой задачи в принципе невозможно. В лучшем
случае для нее можно поискать приближенное решение; за подробностями
обращайтесь к главе 10.

И последнее замечание: если у вас уже есть опыт программирования, почи­
тайте о бинарных деревьях поиска! Эти структуры данных кратко описаны
в последней главе.

Шпаргалка

c:i Бинарный поиск работает намного быстрее простого.

1:1 Время выполнения O(log п) быстрее О(п), а с увеличением размера спи­
ска, в котором ищется значение, оно становится намного быстрее.

1:1 Скорость алгоритмов не измеряется в секундах.
1:1 Время выполнения алгоритма описывается ростом количества операций.

1:1 Время выполнения алгоритмов выражается как «О-большое~.

www.trk.kg