递归算法时间复杂度计算及算法复杂度量级对比相关问题咨询

1. my_func 相关问题解答 #

对应代码如下：

def my_func(A): 
   if (n < 4):
     some_func(); /* O(1) time */
   else:
     [G1, G2, G3, G4] = split(A) /* split A into 4 disjoint subarrays of size n/4 each */
     my_func([G1, G3]); /* recurses on size n/2 */
     my_func([G1, G4]); /* recurses on size n/2 */
     my_func([G2, G3]); /* recurses on size n/2 */
     my_func([G2, G4]); /* recurses on size n/2 */
     some_other_func(); /* split() and some_other_func() take O(n) time */

（1）递推式正确性判断 #

你的判断完全正确，my_func的渐近运行时间确实符合递推式：
T(n) = 4T(n/2) + O(n)，T(1) = O(1)
你给出的判断依据完全成立：每次递归触发4次规模为n/2的子调用，split和some_other_func总耗时为O(n)，n<4的基例耗时为常数O(1)。

（2）总运行步数及Ω(n³)结论判断 #

根据主定理计算该递推式：

• 子问题数a=4，子问题规模系数b=2，非递归操作耗时f(n)=O(n)
• 计算log_b a = log₂4 = 2，f(n)的阶数低于n²，符合主定理第一种情况
  最终可得T(n) = Θ(n²)，你搜索到的Ω(n³)结论是错误的。

2. new_func 相关问题解答 #

对应代码如下：

def new_func(A): /* A is array of length n */
   if (n < 4):
     some_func(); /* O(1) time */
   else:
     [G1, G2, G3, G4] = split(A) /* split A into 4 disjoint subarrays of size n/4 each */
     new_func([G1, G2])
     new_func([G2, G3])
     new_func([G3, G4]); /* recurses on size n/2  */
     some_other_func(); /* split() and some_other_func() take O(n) time */

（1）总运行步数及Ω(n³)结论判断 #

new_func对应的递推式为：
T(n) = 3T(n/2) + O(n)，T(1) = O(1)
同样用主定理计算：

• 子问题数a=3，子问题规模系数b=2，非递归操作耗时f(n)=O(n)
• 计算log_b a = log₂3 ≈ 1.585，f(n)的阶数低于n^1.585，符合主定理第一种情况
  最终可得T(n) = Θ(n^{log₂3}) ≈ Θ(n^1.585)，你判断的Ω(n³)是错误的。

（2）与nlogn量级算法的速度比较 #

n^1.585的增长速度远快于nlogn，因此new_func的运行速度慢于nlogn量级的算法，数据规模越大，性能差距越明显。 #

内容的提问来源于stack exchange，提问作者James Parker