合并排序的复杂性是nlogn？

Question

你好我有一个关于合并排序的复杂性的问题，下面提到的代码如果代码对于合并排序是完美的，那么为什么“cou”值大于“nlogn”，在这种情况下，数组的大小是9 9log9意味着= 28.5293，但“cou”值是：75为什么？请用例子来描述。 高级谢谢大家。

#include<bits/stdc++.h> 
using namespace std; 
int data[] = {7,3,2,10,13,1,25,30,9}; 
int newdata[1000000],cou=0; 
void M_sort(int low, int high) 
{ 
    //--------- 
    cou++; 
    //-------- 
    if(low==high) return ; 
    int mid = (int)(low+high)/2; 
    M_sort(low, mid); 
    M_sort(mid+1, high); 

    int i,j,k; 
    for(int i = low,j =mid +1,k=low;k<=high;k++) 
    { 
     if(i == mid+1) newdata[k] = data[j++]; 
     else if(j == high+1) newdata[k] = data[i++]; 
     else if (data[i]<data[j]) newdata[k] = data[i++]; 
     else newdata[k] = data[j++]; 
     //--------- 
     cou++; 
     //-------- 
    } 

    for(int i =low; i<=high; i++) 
    { 
     data[i] = newdata[i]; 
     //--------- 
     cou++; 
     //-------- 
    } 
} 

int main() 
{ 
    M_sort(0,8); 
    for(int i =0; i<9; i++) 
     cout<<data[i]<<" "; 
    cout<<endl<<"Value of 'cou' is :"<<cou<<endl; 
    return 0; 
} 

Answer 1

首先，n log n并不意味着“正是许多操作”，但运行时间是成比例的数量。例如，它可能是3 *（n log n），并且由于我们忽略了常量因素，它仍然是O（n log n）。

其次，这取决于实施。在您的实施中，例如，最后一个循环：

for(int i =low; i<=high; i++) 
{ 
    data[i] = newdata[i]; 
    //--------- 
    cou++; 
    //-------- 
} 

并非严格必要。使用迭代解决方案，您可以使用两个缓冲区和交换，这是输入，哪个是输出。这本身可以节省近50％的基本操作。您的cou将是40或50，而不是现有实施报告的75。

但是，这只是一个不变的因素。占主导地位的是n log n。但取决于实施，它可能是100*n*log(n) + 27n。它仍然被认为是O（n log n）。