通常,归并排序是将序列一分为二,递归排序。
但是,是否也可以通过将序列除以三分之一来执行归并排序?
mergesort(array, start, last) {
tri_mid = (start+last)/3;
mergesort(array, start, tri_mid);
mergesort(array, tri_mid+1, last);
merge(array, start, last);
}
这会起作用吗?
如果是,那么 bigO 表示法是什么?
最佳答案
是的,它肯定会起作用,但归并排序的优势在于递归分而治之的方法。如果每次将列表分成两半,那么您将得到 O(log2(n)),但由于计算复杂性的工作原理,这等效于 O(log n)。如果你把列表分成不相等的两部分,那么你的大O表达式仍然是O(log n),因为你在每一层把列表分成几部分,但可能比把列表分成两半要慢,因为算法不会以最佳状态工作,即拆分列表,对每个部分进行排序,并合并已排序的子列表。作为思考的食物,想象一下如果合并排序只选择第一个项目作为左子列表,其他所有项目作为右子列表会发生什么。然后大 O 表达式将是 O(n^2),这与其他更糟糕的算法一样糟糕。当然,如果你想尝试你的想法,就这样做,并计时!然后你会确切地知道什么是更快。
关于归并排序将序列不分成两半,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16255782/