如何找出合并排序实现的时间复杂度？

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

基本上，从 here 开始，它正在执行合并（需要 O(n) 时间）并执行 O(lon n) 次 - 因为数字数组每次都被减半.

Answer 2

代码中表示为 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).

tl；博士：
排序算法需要 O(nlogn) 时间。

附带说明一下，函数的命名真的很混乱。

partition()，也就是实际的排序算法应该命名为mergeSort()，而目前的mergeSort()函数只是合并两个子数组，所以应该命名为merge().这几乎就是它通常的命名方式，例如您可以在 wikipedia

中看到

Answer 3

如果您想将时间复杂度作为 T(n)= 的等式求出，则为每一行赋值。例如，每个赋值语句都得到 1unit（像这样的语句 scanf("%d",&n); ）。循环运行的最大次数是那个 loop.For 例子的时间值 {for(i=0;i is less than n; i++} 这一行得到一个值n 的，因为它循环了 n 次。在添加每个步骤和值之后，您将得到一个形式为 T(n)= n+something 的等式。最高阶项将是整个算法的大 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);

a) 这个Merge Sort的时间复杂度是O(nlg(n))。并行化 (1) 和 (2) 会带来任何实际收益吗？从理论上讲，似乎在将它们并行化之后你也会以 O(nlg(n) 结束。但实际上我们可以获得任何收益吗？

b) Space 这里合并排序的复杂度是 O(n)。但是，如果我选择使用链接列表执行就地合并排序（不确定是否可以合理地使用数组完成），space 复杂度是否会变为 O(lg(n))，因为您必须考虑递归堆栈帧大小？我们可以将 O(lg(n)) 视为常数，因为它不能超过 64 吗？我可能在几个地方误解了这一点。 64到底有什么意义？

c) http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html 表示合并排序需要常量 space 使用链表。如何？他们是否将 O(lg(n) 视为常数？

d) [添加以获得更清晰] 对于 space 复杂度计算，假设输入数组或列表已经在内存中是否公平？当我进行复杂度计算时，我总是计算 "Extra" space 除了输入已经采用的 space 之外我还需要。否则 space 复杂度将始终为 O(n) 或更糟。

e) 列表只需要在合并过程中更改一些指针。这需要不断增加内存。

f) 这就是人们在合并排序复杂性分析中提到 'additional space requirement' 或类似内容的原因。很明显，您必须将元素存储在某个地方，但最好提及 'additional memory' 以防止纯粹主义者。

Answer 5

如果您知道如何获得归并排序的递归关系，那么对于时间复杂度，上面的解释就足够了。

如何找出合并排序实现的时间复杂度？

How to find out time complexity of mergesort implementation?

algorithm

big-o

time-complexity