Пространственная сложность сортировки слиянием с использованием массива

Question

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

Если мы посмотрим на дерево повторения функции слияния и попробуемпроследите алгоритм, тогда размер стека будет log(n).Но так как функция merge также существует внутри mergesort, которая создает два массива размером n/2, n/2, то сначала я должен найти пространственную сложность отношения повторения, а затем, если я добавлю в это n/2 + n/2 это станет O(log(n) + n).

Я знаю ответ, но я запутался в процессе.Может кто-нибудь сказать мне правильную процедуру?

Эта путаница происходит из-за функции слияния, которая не является рекурсивной, но вызывается в рекурсивной функции

И почему мы говорим, что сложность пространства будет O(log(n) + n) иПо определению сложности пространства рекурсивных функций мы обычно вычисляем высоту рекурсивного дерева

Merge(Leftarray, Rightarray, Array) {
    nL <- length(Leftarray)
    nR <- length(Rightarray)
    i <- j <- k <- 0
    while (i < nL && j < nR) {
        if (Leftarray[i] <= Rightarray[j])
            Array[k++] <- Leftarray[i++]
        else
            Array[k++] <- Rightarray[j++]
    }
    while (i < nL) {
        Array[k++] <- Leftarray[i++]
    }
    while (j < nR) {
        Array[k++] <- Rightarray[j++]
    }    
}  

Mergesort(Array) {
    n <- length(Array)
    if (n < 2)
        return
    mid <- n / 2
    Leftarray <- array of size (mid)
    Rightarray <- array of size (n-mid)
    for i <- 0 to mid-1
        Leftarray[i] <- Array[i]
    for i <- mid to n-1
        Right[i-mid] <- Array[mid]
    Mergesort(Leftarray)
    Mergesort(Rightarray)
    Merge(Leftarray, Rightarray) 
}    

Answer 1

MergeSort time Сложность - O (nlgn), которая является фундаментальным знанием.Сложность пространства сортировки слиянием всегда будет O (n), в том числе с массивами.Если вы вытянете космическое дерево, то сложность пространства будет равна O (nlgn).Однако, поскольку код является кодом глубины первой, вы всегда будете расширяться только по одной ветви дерева, поэтому требуемое общее использование пространства всегда будет ограничено O (3n) = O (n).

Например, если вы рисуете космическое дерево, кажется, что оно O (nlgn)

                         16                                 | 16
                        /  \                              
                       /    \
                      /      \
                     /        \
                    8          8                            | 16
                   / \        / \
                  /   \      /   \
                 4     4    4     4                         | 16
                / \   / \  / \   / \
               2   2 2   2.....................             | 16
              / \  /\ ........................
             1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1              | 16

, где высота дерева O (logn) => Пространственная сложность O (nlogn + n) = O (nlogn).Однако в реальном коде это не так, поскольку он не выполняется параллельно.Например, в случае, когда N = 16, так выполняется код для сортировки слиянием.N = 16.

                       16
                      /
                     8
                    /
                   4
                 /
                2
               / \
              1   1

обратите внимание, как число используемых мест равно 32 = 2n = 2 * 16 <3n </p>

Затем оно сливается вверх

                       16
                      /
                     8
                    /
                   4
                 /  \
                2    2
                    / \                
                   1   1

, что34 <3н.Затем он сливается вверх </p>

                       16
                      /
                     8
                    / \
                   4   4
                      /
                     2
                    / \ 
                   1   1

36 <16 * 3 = 48 </p>

, затем сливается вверх

                       16
                      / \
                     8  8
                       / \
                      4   4
                         / \
                        2   2
                            /\
                           1  1

16 + 16 + 14 = 46 <3 * n= 48 </p>

в большем случае, n = 64

                 64
                /  \
               32  32
                   / \
                  16  16
                      / \
                     8  8
                       / \
                      4   4
                         / \
                        2   2
                            /\
                           1  1

, что составляет 64 * 3 <= 3 * n = 3 * 64 </p>

.индукция для общего случая.

Следовательно, сложность пространства всегда ограничена O (3n) = O (n), даже если вы реализуете с массивами до тех пор, пока вы очищаете используемое пространство после объединения и не выполняете код впараллельно, но последовательно.

Пример моей реализации приведен ниже:

Answer 2

Эта реализация MergeSort довольно неэффективна в области памяти и имеет некоторые ошибки:

• память не освобождена, я полагаю, вы полагаетесь на сборку мусора.
• целевой массив Array не передается Merge с помощью MergeSort.

Дополнительный пробел в размере Array выделяется MergeSort для каждого уровня рекурсии,поэтому требуется как минимум вдвое больше размера исходного массива ( 2 * N ), если сборка мусора является оптимальной, например, если он использует счетчик ссылок, и до N * log2 (N) пробел используется, если сборщик мусора ленив.Это намного больше, чем требуется, поскольку тщательная реализация может использовать всего лишь N / 2 дополнительного пространства.