Сколько элементов можно отсортировать за Θ(log n), используя сортировку кучи?

Question

Сколько элементов можно отсортировать за Θ(log n), используя сортировку кучи?

Когда мы делаем heapsort, для построения heap нам нужна сложность Θ (n), а затем сделать heapsort O (nlog n). Я понимаю эту концепцию. Но что касается нашего вопроса, мы не можем даже построить кучу из n элементов за время elements (log n). Так ответ O (1) учитывает размер ввода n?

Я также видел другое объяснение, которое выводит сложность как log (log n / log log n) с учетом входного размера logn. Я тоже не совсем следую этому методу. Так какой правильный ответ и почему?

Answer 1

Я думаю, что вопрос заключается в том, "предполагая, что где-то есть известное значение n, какова асимптотическая граница для размера массива, как функция от n, где сортировка этого массива с помощью heapsort займет время Θ(log n)?"

Сортировка массива с k элементами занимает время Θ (k log k) при увеличении k. Вы хотите выбрать k таким, что Θ(k log k) = Θ(log n). Выбор k = Θ(log n) не обязательно работает, так как Θ(k log k) = Θ(log n log log n) ≠ log (log n). С другой стороны, если вы выберете k = Θ(log n / log log n), то время выполнения сортировки будет

Θ((log n / log log n) log (журнал n / log log n))

= Θ ((log n / log log n) (log log n - журнал log n))

= Θ (log n - log n log log log n / log log n)

= Θ (log n (1 - log log log n / log log n))

Обратите внимание, что 1 - log log log n / log log n стремится к 1, когда n переходит в бесконечность, поэтому приведенное выше выражение фактически равно Θ (log n), как требуется.

Поэтому, если вы попытаетесь отсортировать массив размера Θ (log n / log log n), используя сортировку кучи, как функцию от n, время выполнения будет равно Θ (log n).

Надеюсь это поможет!

Answer 2

Для сортировки N элементов время = O(NlogN), что в основном означает, что сортировка каждого элемента займет время O(logN)