Как определить временную сложность реализации mergesort?

Question

Мы все знаем, что сложность алгоритма сортировки слиянием - «N Log N». Но из этого ниже кода, как поэтапно рассчитать эту «N Log N» большую нотацию O? Есть несколько ответов на этот вопрос в Интернете, но они очень сложны для понимания. Пожалуйста, помогите мне понять. Миллион спасибо заранее.

#include<stdio.h> 
#define MAX 50 

void mergeSort(int arr[],int low,int mid,int high); 
void partition(int arr[],int low,int high); 

int main(){ 

    int merge[MAX],i,n; 

    printf("Enter the total number of elements: "); 
    scanf("%d",&n); 

    printf("Enter the elements which to be sort: "); 
    for(i=0;i<n;i++){ 
     scanf("%d",&merge[i]); 
    } 

    partition(merge,0,n-1); 

    printf("After merge sorting elements are: "); 
    for(i=0;i<n;i++){ 
     printf("%d ",merge[i]); 
    } 

    return 0; 
} 

void partition(int arr[],int low,int high){ 

    int mid; 

    if(low<high){ 
     mid=(low+high)/2; 
     partition(arr,low,mid); 
     partition(arr,mid+1,high); 
     mergeSort(arr,low,mid,high); 
    } 
} 

void mergeSort(int arr[],int low,int mid,int high){ 

    int i,m,k,l,temp[MAX]; 

    l=low; 
    i=low; 
    m=mid+1; 

    while((l<=mid)&&(m<=high)){ 

     if(arr[l]<=arr[m]){ 
      temp[i]=arr[l]; 
      l++; 
     } 
     else{ 
      temp[i]=arr[m]; 
      m++; 
     } 
     i++; 
    } 

    if(l>mid){ 
     for(k=m;k<=high;k++){ 
      temp[i]=arr[k]; 
      i++; 
     } 
    } 
    else{ 
     for(k=l;k<=mid;k++){ 
      temp[i]=arr[k]; 
      i++; 
     } 
    } 

    for(k=low;k<=high;k++){ 
     arr[k]=temp[k]; 
    } 
} 

Я нашел этот исходный код в этот адрес:

http://www.cquestions.com/2011/07/merge-sort-program-in-c.html

Answer 1

Функция в коде, обозначенном как mergeSort(), принимает O(n) времени, это циклическое постоянное число раз над элементами в пределах диапазона (low,high).

Функция, обозначенная как partition(), которая является фактической функцией сортировки, занимает время O (nlogn). Это на самом деле может быть обозначен как:

T(n) = 2T(n/2) + C*n //for some constant C 

Пояснение:

Каждый рекурсивный вызов разбиения T(n/2). Их два, поэтому 2T(n/2). Кроме того, он называет mergeSort(), то есть O(n), поэтому мы добавляем C*n, для некоторых CONSTANT C.

К master theorem case 2, с: c=log_2(2)=1, k=0, мы получаем, что функция находится в Theta(n^c* log(n)^(k+1)) = Theta(nlogn).

Т.Л., др:
Алгоритм сортировки занимает O(nlogn) время.

В качестве примечания стороны, назначение функций действительно запутывает.

partition(), который является фактическим алгоритм сортировки должен быть назван mergeSort(), а функция в настоящее время mergeSort() просто объединение двух подмассива, поэтому он должен быть назван merge(). Это почти так, как это обычно называют, как вы можете видеть, например, в wikipedia

Answer 2

В принципе, извлекая из here, он делает слияние (что занимает O (п)) и делать это O (lon n), так как массив чисел сокращается пополам каждый раз.

Answer 3

Если вы хотите найти временную сложность как уравнение T (n) = что-то, тогда присвойте значения каждой строке. например, каждый оператор присваивания получает 1unit (такие утверждения, как эти scanf ("% d", & n);). максимальное число раз, когда цикл работает, является значением времени для этого цикла. Например, {для (i = 0; i меньше, чем n; i ++} эта строка получает значение n, поскольку она проходит через n раз после добавления каждого шага и значения вы получите уравнение вида T (n) = n + что-то. Высшим порядком будет Big O всего алгоритма, например, вы получите T (n) = n^3 + n^2 + 700, здесь n^3 - член высшего порядка, поэтому большой O всего алгоритма n^3 (n куб). Неважно, что остальное T (n) ,

Answer 4

Давайте эту реализацию сортировки слияния в качестве примера

void mergesort(Item a[], int l, int r) { 
if (r <= l) return; 
int m = (r+l)/2; 
mergesort(a, l, m); ------------ (1) 
mergesort(a, m+1, r); ------------(2) 
merge(a, l, m, r); 

а) Временная сложность этого сортировка слияния представляет собой О (NLG (п)). Распараллеливает ли (1) и (2) практический выигрыш? Теоретически, кажется, что после их распараллеливания вы окажетесь в O (nlg (n). Но практически мы можем получить какую-либо прибыль?

b) Пространственная сложность этого слияния здесь: O (n). Однако, если я захочу выполнить сортировку слияния на месте с помощью связанных списков (не уверен, что это можно сделать с массивами разумно) будет сложность пространства O (lg (n)), так как вам приходится учитывать размер кадра стека рекурсии ? Можно ли рассматривать O (lg (n)) как постоянную, так как она не может быть больше 64? Возможно, я неправильно понял это в нескольких местах. Что такое значение 64?

c) http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html говорит, что для сортировки merge требуется постоянное пространство, используя связанные списки. Как ? Возможно, они относятся к O (Г (п) константа?

d) [Добавлен, чтобы получить больше ясности] Для расчета пространства сложности Справедливо предположить, входной массив или список уже в памяти? Когда я выполняю вычисления сложности, я всегда вычисляю «лишнее» пространство, которое мне понадобится, помимо пространства, уже взятого с помощью ввода. В противном случае сложность пространства всегда будет O (n) или хуже.

e) Списки требуют только некоторых указателей, измененных в процессе слияния. Это требует постоянной дополнительной памяти.

f) Именно поэтому при анализе сложности сортировки людей упоминается «дополнительное пространство» или такие вещи. Очевидно, что вам нужно хранить элементы где-то, но всегда лучше упомянуть «дополнительную память», чтобы держать пуристов в страхе.

Answer 5

Если вы знаете, как получить рекуррентное соотношение для сортировки слияния, то для временной сложности выше объяснение должно быть достаточно.