Этот раздел посвящен не просто 'алгоритмам', а именно мощным и оптимальным.
О каждом методе я постараюсь сказать, для каких целей он хорош и когда оптимален. 'Тупиковыми' и неэффективными методами постараюсь страничку не засорять.
Оценки времени исполнения
Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n). Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.
n
log n
n*log n
n2
1
0
0
1
16
4
64
256
256
8
2,048
65,536
4,096
12
49,152
16,777,216
65,536
16
1,048,565
4,294,967,296
1,048,476
20
20,969,520
1,099,301,922,576
16,775,616
24
402,614,784
281,421,292,179,456
Если считать, что числа в таблице соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму с временем работы O(log n) потребуется 20 микросекунд, а алгоритму с временем работы O( n2 ) - более 12 дней.
ВАЖНО, что если оба алгоритма, например, O ( n*log n ), то это отнюдь не значит, что они одинакого эффективны. Символ О не учитывает константу, то есть первый может быть, скажем в 1000 раз эффективнее. Это значит лишь то, что их время возрастает приблизительно как функция n*log n.
Алгоритмы
ЕСЛИ ЧТО-ТО НЕ РАБОТАЕТ или ЕСТЬ ОШИБКА -
пишите на nlpstudent@mail.ru !!! Исправим в момент.