如何找出mergesort实现的时间复杂度？ [英] How to find out time complexity of mergesort implementation?
问题描述
我们都知道合并排序算法的时间复杂度为 N Log N。但是，从下面的代码如何逐步计算出此 N Log N大O符号？互联网上对此问题有一些答案，但是它们很难理解。请帮助我理解。
＃include< stdio.h>
＃定义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（输入元素总数：）;
scanf（％d，& n）;
printf（输入要排序的元素：）;
for（i = 0; i
}
partition（merge，0，n-1）;
printf（合并后的排序元素为：）;
for（i = 0; i
}
返回0；
}
void partition（int arr []，int low，int high）{
int mid;
if（low< high）{
mid =（low + high）/ 2;
分区（arr，low，mid）;
分区（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 =低；
i =低；
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
代码中以 mergeSort（）表示的函数需要 O（n）时间，它在循环在（低，高）范围内的元素上具有恒定的次数。
该函数表示为 partition（）是实际的排序函数，需要花费O（nlogn）时间。它实际上可以表示为：
T（n）= 2T（n / 2）+ C * n //对于某些常数C
说明：
每个递归分区调用为 T（n / 2）。它们有两个，所以 2T（n / 2）。另外，它调用 mergeSort（），即 O（n），因此我们添加 C * n ，对于某些常量 C 。
通过主定理案例2 ，其中： c = log_2（2）= 1，k = 0 ，我们得到函数在 Theta（n ^ c * log（n）^（k + 1））= Theta（nlogn）。
tl; dr ：
排序算法采用 O（nlogn） 时间。
这些函数的命名确实令人困惑。 / p>
partition（），这是实际的排序算法，应命名为 mergeSort（），当前的 mergeSort（）函数只是合并两个子数组，因此应将其命名为 merge（）。这几乎就是通常的命名方式，例如您可以在维基百科
We all know that merge sorting algorithm time complexity is "N Log N". But from this below code how to calculate this "N Log N" big O notation step by step ? There are some answer about this question on internet but they are very complicated to understand. Please help me to understand. Million thanks in advance.
#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];
}
}
I found this source code in this address:
http://www.cquestions.com/2011/07/merge-sort-program-in-c.html
The function in the code denoted as mergeSort() takes O(n) time, it is looping constant number of times over the elements within range (low,high).
The function denoted as partition(), which is the actual sorting function, takes `O(nlogn) time. It can actually be denoted as:
T(n) = 2T(n/2) + C*n //for some constant C
Explanation:
Each recursive call to partition is T(n/2). There are two of them, so 2T(n/2). In addition, it calls mergeSort(), which is O(n), so we add C*n, for some CONSTANT C.
By master theorem case 2, with: c=log_2(2)=1, k=0, we get that the function is in Theta(n^c* log(n)^(k+1)) = Theta(nlogn).
tl;dr:
The sorting algorithm takes O(nlogn) time.
As a side note, the naming of the functions are really confusing.
partition(), which is the actual sorting algorithm should be named mergeSort(), and the currently mergeSort() function is just merging the two subarrays, so it should be named merge(). This is pretty much how it is usually named, as you can see for example in wikipedia
这篇关于如何找出mergesort实现的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
