Большой выбор слияния

Question

void mergeSort(int arr[], int l, int r) 
{ 
   if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 

        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 

        merge(arr, l, m, r); 
    } 
} 

вот код сортировки слиянием

Я не могу понять, как его большое значение равно n log (n), в то время как функция большого слияния равна n, а функция слияния вызывается 7 разчто равно n - 1

, если в качестве входных данных у нас есть следующий массив {8,7,6,5,4,3,2,1}

, то вызовы слияния будут

слияние ({8,7,6,5,4,3,2,1}, 0,0,1)

слияние ({7,8,6,5,4,3,2,1}, 2,2,3)

слияние ({7,8,5,6,4,3,2,1}, 0,1,3)

слияние ({5,6,7,8,4,3,2,1}, 4,4,5)

слияние ({5,6,7,8,3,4,2,1}, 6,6,7)

слияние ({5,6,7,8,3,4,1,2}, 4,5,7)

слияние ({5,6,7,8,1,2,3,4}, 0,3,7)

тогда результат будет {1,2,3,4,5,6,7,8}

так, насколько большой вычисляется, я увидел метод master, знаю его формулу и увидел 3 уровня алгоритма сортировки слиянием

, но я хочу вычислять шаг за шагом

Answer 1

Простой способ увидеть его O (nlogn) - использовать дерево рекурсии, поскольку T(n) = O(n) + 2T(n/2) вы можете нарисовать дерево рекурсии для T (n) следующим образом:

             n
          /     \
     (n/2)       (n/2)
     /   \       /   \
 (n/4)  (n/4) (n/4) (n/4)
            .
            .
            .

В каждой строкедерево сумма равна n (n = n, n / 2 + n / 2 = n, n / 4 + n / 4 + n / 4 + n / 4 = n, ...)

А выиметь log(n) строк (потому что в каждой строке n делится на 2), поэтому общая сумма узлов в дереве равна: O(nlogn)

Answer 2

Сложность по времени для сортировки массива длины n с помощью Mergesort составляет T(n)=2 * T(n/2) + O(n), где T - функция сложности времени, * 2 * T(n/2) - рекурсивные вызовы, а O(n) объединяет эти две рекурсии.Теперь вы можете доказать, что T(n) ∈ O(n * log(n)) с доказательством по индукции свыше m = log2(n), если хотите.Одно из таких доказательств указано здесь: https://www.cs.auckland.ac.nz/compsci220s1c/lectures/2016S1C/CS220-Lecture09.pdf