Временная сложность итеративной быстрой сортировки

Question

Я узнал о рекурсивной быстрой сортировке, и для наилучшего случая требуется O (nlogn), а для худшего - O (n ^ 2). Но я пытаюсь найти временную сложность итеративной быстрой сортировки. Я знаю, что это O (nlogn) для лучшего случая и O (n ^ 2). Но я не оправдываю это в лучшем случае. Я слежу за этим уроком

https://www.techiedelight.com/iterative-implementation-of-quicksort/

скажу, что у нас есть 15 элементов, так что позиции сводного индекса всегда будут в середине, что делает его идеальным сценарием в лучшем случае. Но я нахожу это условием "while (! Stack.empty ())", т. Е. Количество разделов будет 6 раз, что не близко к log (n). Как можно оправдать временную сложность лучшего случая в итеративной быстрой сортировке O (nlogn).?

Answer 1

На первом проходе разбиения вы разделяетесь на два раздела. Это занимает O (N). На следующем проходе у вас есть два раздела, каждый из которых имеет размер n / 2. Требуется O (n / 2), чтобы разделить каждый из них. Общее время для второго прохода составляет O (n / 2 + n / 2): O (n). Каждый проход имеет больше разделов, но разделов меньше. В общей сложности вы выполняете log (n) проходов, каждый из которых требует O (n) общего времени.

Он работает точно так же, как рекурсивная версия. Единственное отличие состоит в том, что в итерационной версии вы управляете стеком явно, а не зависите от неявного стека в рекурсивной версии.