Почему дерево решений для сортировки на основе сравнения имеет "по крайней мере" n! уходит "а не точно п?

Question

Модель дерева решений можно использовать для сортировки, но я запутался в теореме, что она говорит, по крайней мере, n! уходит но не совсем п! листья? какие еще возможности?

Answer 1

Рассмотрим, например, быстрая сортировка , алгоритм, который случайным образом выбирает сводные элементы как часть сортировки на основе сравнения.

Из-за этого случайного элемента быстрая сортировка не всегда будет следовать одному и тому же решению.путь даже с одним и тем же входом, поэтому мы можем получить больше листьев, чем возможных входных данных.