Дерево решений иллюстрирует возможные исполнения алгоритма для определенной категории c входов. В случае сортировки на основе сравнения категория будет состоять из всех входных списков определенного размера, поэтому существует одно дерево для n = 1, одно для n = 2, одно для n = 3 и т. Д. Каждое дерево имеет отношение c к точным входным значениям, но отслеживает возможные направления вычисления go в зависимости от того, как входные значения сравниваются друг с другом.
Одно из применений дерева решений заключается в причина верхних и нижних границ сложности во время выполнения. Как вы упомянули, высота дерева представляет верхнюю границу времени выполнения для входного размера этого дерева, и если вы можете найти общее соотношение между входным размером и высотой дерева для всех деревьев решений алгоритма, вы нашли выражение для верхней границы времени выполнения. Например, если вы проанализируете Bubble Sort, вы обнаружите, что дерево решений для входного размера n имеет высоту, примерно равную n * (n + 1) / 2, поэтому теперь вы знаете, что его время выполнения ограничено O(n^2). И поскольку у нас есть верхняя граница для общего времени выполнения, она также становится верхней границей для времени выполнения в худшем случае.
При рассмотрении конкретного алгоритма c нас обычно интересует скорость его выполнения. может быть (в лучшем случае), как быстро это обычно (в среднем случае) и насколько медленно это может быть (в худшем случае). И мы часто express в лучшем случае используем нижнюю границу (Омега), потому что нижняя граница для лучшего случая также является нижней границей для общего времени выполнения; аналогично, мы часто express в худшем случае используем верхнюю границу (O), потому что верхняя граница для наихудшего случая также является верхней границей для общего времени выполнения. Но нам не нужно - O, Omega и Theta - только математические инструменты, которые говорят что-то о функции, не заботясь о том, что функция в нашем случае описывает сложность времени выполнения. Итак, давайте сделаем что-то необычное: давайте рассмотрим все возможные алгоритмы для проблемы и используем деревья решений, чтобы попытаться выяснить что-то о all их сложностях наихудшего случая. Тогда интересный вопрос не в том, какова верхняя граница, потому что легко сделать чрезвычайно медленные алгоритмы сортировки. Вместо этого нас интересует нижняя граница: каков наилучший наихудший случай? Какой алгоритм дает наилучшую гарантию того, насколько медленным он будет в худшем случае?
Любой алгоритм сортировки должен уметь обрабатывать любой порядок своих входных элементов. Каждый листовой узел представляет одну конкретную конечную перестановку (перестановку) входных элементов, и с размером ввода n существует n! перестановок. Таким образом, дерево решений для входного размера n имеет как минимум n! конечных узлов. Любой алгоритм, который хочет иметь хороший наихудший случай, должен иметь сбалансированное дерево, где все конечные узлы находятся на самом глубоком или втором по глубине уровне. И сбалансированное дерево с n! листовыми узлами должно иметь высоту Omega(n lg n). Теперь мы знаем кое-что очень интересное: для любого алгоритма сортировки, основанного на сравнении, best возможная высота (которая представляет время выполнения в худшем случае) равна по крайней мере n lg n! Другими словами, невозможно создать алгоритм сортировки на основе сравнения, который всегда будет быстрее, чем n lg n.
(Примечание: height <= log2(leaf nodes) относится только к сбалансированным деревьям. Восемь деревьев может быть как столько, сколько число узлов минус один.)