0

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

4

1 回答 1

1

这可能是你的功课，但我建议你阅读 Cormen、Lierson 和 Rivest 的第 2 章。

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

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

Note - here logarithm is of base 3 .
于 2012-12-26T13:59:49.607 回答