问改进的归并排序算法
EN

Stack Overflow用户

提问于 2012-11-12 12:55:11

回答 1查看 1.4K关注 0票数 0

描述一种改进的合并排序算法，在该算法中，给定的序列被分割成大小相等的大约三分之一的三个子序列。渐进地分析算法的时间复杂度。如何解决这个问题？

发布于 2012-12-26 21:59:50

这可能是你的家庭作业，但我建议你读科尔曼，利尔森和里维斯特的第二章。

解这个递归关系- T(n) = 3T(n/3) + O(n)

每个问题被细分为3个子问题，包含原始数据的n/3部分。对它应用masters定理，你会发现答案是0( n*log(n) )。

Note - here logarithm is of base 3 .

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/13338568

复制

相似问题

问改进的归并排序算法EN