Алгоритм является оптимальным, если любой алгоритм, решающий ту же задачу, работает не быстрее данного.
- Как узнать, оптимален ли наш алгоритм?
- Или, быть может, он не оптимален, но все-таки достаточно хорош?
Для ответа на эти вопросы мы должны знать наименьшее количество операций, необходимое для решения конкретной задачи, которое называется нижней границей. Для этого следует изучать именно задачу, а не решающие ее алгоритмы. Нижняя граница определяет объем работы, необходимый для решения поставленной задачи, и показывает, что любой алгоритм, претендующий на то, что решает ее быстрее, обязан неправильно обрабатывать некоторые ситуации.
Для анализа процесса сортировки списка из трех чисел вновь воспользуемся бинарным деревом. Внутренние узлы дерева будем помечать парами сравниваемых элементов. Порядок элементов, обеспечивающий проход по данной ветви дерева, изображается в соответствующем листе дерева. Дерево для списка из трех элементов изображено на следующем рисунке. Такое дерево называется деревом решения.
Всякий алгоритм сортировки создает свое дерево решений в зависимости от того, какие элементы он сравнивает.
Как же можно получить границы для сложности алгоритма с помощью дерева решений? Мы знаем, что корректный алгоритм должен упорядочивать любой список данных, независимо от исходного порядка элементов в нем. Для любой перестановки входных значений должен существовать по крайней мере один лист, а это означает, что в дереве решений должно быть не меньше N! листьев. Если алгоритм по-настоящему эффективен, то каждая перестановка появится в нем лишь однажды. Сколько уровней должно быть в дереве с N! листьями? Мы уже видели, что в каждом очередном уровне вдвое больше узлов, чем в предыдущем. Число узлов на уровне К равно 2K-1, поэтому в нашем дереве решений будет L уровней, где L — наименьшее целое число, для которого N <= 2L-1. Логарифмируя это неравенство, получаем log2N! <= L - 1.
Можно ли избавиться от факториала, чтобы найти наименьшее значение L? Обратимся к свойствам факториала. Воспользуемся тем, что log2N! = log2(N(N-1)(N-2)...1), откуда в силу равенства logb(xy) = logbx + logby (1.5)
.
Из равенства 
(1.21) получаем
.
Это означает, что минимальная глубина L дерева решений для сортировки имеет порядок O(Nlog2N). Теперь мы знаем, что любой алгоритм сортировки порядка O(NlogN) является наилучшим, и его можно считать оптимальным. Более того, из этого исследования вытекает, что любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно.
При выводе нижней границы для алгоритма сортировки предполагалось, что алгоритм работает путем последовательного попарного сравнения элементов списка. Существует другой алгоритмом сортировки (корневая сортировка), который требует линейного времени. Для достижения цели этот алгоритм не сравнивает значения ключей, а разбивает их на «кучки».
 |
| Дерево решений для сортировки трехэлементного списка |
Всякий алгоритм сортировки создает свое дерево решений в зависимости от того, какие элементы он сравнивает.
- Самый длинный путь в дереве решений от корня к листу соответствует наихудшему случаю.
- Наилучшему случаю отвечает кратчайший путь.
- Средний случай описывается частным от деления числа ребер в дереве решений на число листов в нем.
Как же можно получить границы для сложности алгоритма с помощью дерева решений? Мы знаем, что корректный алгоритм должен упорядочивать любой список данных, независимо от исходного порядка элементов в нем. Для любой перестановки входных значений должен существовать по крайней мере один лист, а это означает, что в дереве решений должно быть не меньше N! листьев. Если алгоритм по-настоящему эффективен, то каждая перестановка появится в нем лишь однажды. Сколько уровней должно быть в дереве с N! листьями? Мы уже видели, что в каждом очередном уровне вдвое больше узлов, чем в предыдущем. Число узлов на уровне К равно 2K-1, поэтому в нашем дереве решений будет L уровней, где L — наименьшее целое число, для которого N <= 2L-1. Логарифмируя это неравенство, получаем log2N! <= L - 1.
Можно ли избавиться от факториала, чтобы найти наименьшее значение L? Обратимся к свойствам факториала. Воспользуемся тем, что log2N! = log2(N(N-1)(N-2)...1), откуда в силу равенства logb(xy) = logbx + logby (1.5)
. (1.21) получаем.При выводе нижней границы для алгоритма сортировки предполагалось, что алгоритм работает путем последовательного попарного сравнения элементов списка. Существует другой алгоритмом сортировки (корневая сортировка), который требует линейного времени. Для достижения цели этот алгоритм не сравнивает значения ключей, а разбивает их на «кучки».
