合并排序和O(n log n)神秘
我读了所有的解释，这里，但仍然不相信。我认为合并是n*n，我知道我错了，但不确定在哪里。以下是我的想法：
假设我们对8个元素进行排序，这就是算法(假设我对此有正确的想法)：
doSort(int begin, int end, int[] arr) {
if(end != begin) {
int mid = begin + (end - begin)/2;
doSort(begin,mid);
doSort(mid + 1, end);
merge(arr, begin, mid, mid + 1, end);
}
}
merge(int[] arr,int i_begin, i_end, j_begin, j_end) {
// Do the comparison and all that
}现在，根据我的理解，merge()本身具有复杂性O(n)。现在，让我们看看doSort()和merge()调用了多少次。以下索引需要doSort()：
- 0-7
- 0-3
- 4-7
- 0-1
- 2-3
- 4-5
- 6-7
它是O(n)的7倍，我们要对8个元素进行排序。类似地，对于16个元素，merge()被调用15次，依此类推。因此，虽然我们每次将数组分成一半，但我们并没有用任何方法消除另一半。将其与BST搜索进行比较，在BST搜索中，我在每一步中删除了树的一半，因为我知道另一半对我来说是无用的，这在我看来是真正的log(n)。在合并排序的情况下，我们要调用merge n-1次，每次合并都需要o(n)操作，所以O(n*n)。
我哪里出错了？如有任何建议，将不胜感激。
回答 2
Software Engineering用户
发布于 2016-02-20 16:32:45
排序(例如1024个数字)，您将执行两个512元素数组的合并。您执行两个256个元素数组的两个合并，两个128个元素数组的4个合并，8个tims 64个元素，两个1个元素数组的512个合并。
您刚刚检查了单个最大合并(1x512元素)和合并总数(1,023个合并)的时间，但是您没有意识到，合并的一半只是一个元素数组，剩下的一半只是两个元素数组，依此类推。每组合并需要n= 1024步(一个合并1024个元素结果，2个合并512个元素结果，.，512个合并两个元素结果)，还有log2 (n) = 10组合并，总共有10x1024或(n log2 n)步骤。
Software Engineering用户
发布于 2016-02-20 15:09:00
合并排序的复杂性是O(nlogn)而不是O(n*n)。
合并排序是一种分治算法。从三个步骤来考虑-
除法步骤计算每个子阵列的中点.该步骤中的每一步都只是采用O(1) time.The征服步骤，递归地对n/2 (偶数n)元素的两个子数组进行排序，each.The合并步骤合并n个元素，这需要O(n)时间。
现在，对于步骤1和步骤3，即在O(1)和O(n)之间，O(n)更高。让我们考虑步骤1和步骤3总共需要O(n)时间。假设它是cn，表示某个常数c。
这些步骤执行了多少次？
为此，请查看下面的树--对于从上到下的每个级别，对长度为n/2的两个子数组调用merge方法。这里的复杂性是2* ( cn /2) =cn级别3对长度为n/4的4个子数组调用合并方法。这里的复杂性是4* ( cn /4) =cn等等.
对于给定的n，这棵树的高度是(logn + 1)，因此总的复杂度是(logn + 1)*(cn)。这是合并排序算法的O(nlogn)。
https://softwareengineering.stackexchange.com/questions/310390
复制相似问题
腾讯云开发者
