Какое количество уровней в сортировке слиянием? - PullRequest
Новая
       29

Какое количество уровней в сортировке слиянием?

0 голосов
/ 12 мая 2019

Я запутался, каково количество уровней (высота дерева) в сортировке слиянием.

Где-то, где я видел, дана функция потолка $ \ log {2} {n} $, нотам, где написано, это $ \ log {2} {n} + 1 $

Может кто-нибудь объяснить, как это правильно.

1 Ответ

0 голосов
/ 13 мая 2019

Функция потолка необходима для обработки случая, когда n не является степенью 2.

Ответ в

Как получается высота дерева рекурсии в сортировке слиянием lg (n) + 1

вводит в заблуждение, потому что каждый узел в двоичном дереве состоит из значения и двух ссылок (каждая из которых может быть нулевой), в то время как каждый кадр стека в рекурсивной сортировке слиянием сверху вниз состоит из 0 значений и двух индексов, итераторов или указатели.

Что касается формулы, если есть проверка базового случая размера подмассива == 1, сделанная вызывающей стороной, включая начальный вызов, такой как 

    if(end-begin > 1) call mergesort();

тогда формула - это число уровней стека кадров = потолок (log2 (n)).

Если проверка для базового случая выполняется только в верхней части сортировки слиянием, то формула будет иметь число уровней кадров стека = 2 + потолок (log2 (n)). Рассмотрим случай n = 7, есть 5 уровней стековых фреймов, если вы включаете начальный вызов mergesort. При сортировке слиянием сверху вниз рекурсия продолжается до тех пор, пока размер подмассива не уменьшится до базового случая одного элемента, и в этом случае он возвращает: 

level
1                           0,6
2             0,3                         3,6
3      0,1          1,3             3,4          4,6
4      ret       1,2   2,3          ret       4,5   5,6
5                ret   ret                    ret   ret
...