Почему сложность во времени сортировки кучи, O (nlogn)? - PullRequest
Новая
       22

Почему сложность во времени сортировки кучи, O (nlogn)?

0 голосов
/ 07 января 2019

Я пытаюсь понять временную сложность различных структур данных и начал с сортировки кучи. Из того, что я прочитал, я думаю, что в целом люди согласны, что сортировка кучи имеет временную сложность O (nlogn); Однако мне трудно понять, как это произошло.

Большинство людей сходятся во мнении, что метод heapify принимает O (logn), а метод buildmaxheap принимает O (n), то есть O (nlogn), но почему heapify принимает O (logn)?

С моей точки зрения, heapify - это просто метод, который сравнивает левый и правый узел узла и корректно меняет их местами в зависимости от того, является ли он минимальной или максимальной кучей. Почему это занимает O (logn)?

Я думаю, что я что-то здесь упустил и был бы очень признателен, если бы кто-то мог объяснить мне это лучше.

Спасибо.

1 Ответ

0 голосов
/ 09 января 2019

Вы пропускаете рекурсивный вызов в конце метода heapify. 

Heapify(A, i) {
   le <- left(i)
   ri <- right(i)
   if (le<=heapsize) and (A[le]>A[i])
      largest <- le
   else
      largest <- i 
   if (ri<=heapsize) and (A[ri]>A[largest])
      largest <- ri
   if (largest != i) {
      exchange A[i] <-> A[largest]
      Heapify(A, largest)
   }
}

В худшем случае после каждого шага largest будет примерно в два раза i. Чтобы достичь конца кучи, мне потребуется O(logn) шагов.

...