递归复杂度计算疑惑：为何递归式为T(n)=2T(n/2)+cn²？

嘿，我来帮你解开这个困惑！你之所以觉得递归式应该是T(n)=T(n/2)+cn²，核心是误解了for循环的执行次数，咱们一步步拆解代码来看：

关键细节：for循环执行两次 #

先看这段代码里的for循环：

for i = 0 to 1 do
    if n >1 then
        analizz(n/2)

这里的i=0 to 1意味着循环会执行两次（i取0和1各一次），每次循环只要n>1，就会触发一次analizz(n/2)的递归调用。所以每一轮while循环里，这个for循环会带来两次递归调用，这就是递归式中2T(n/2)的来源——你之前可能误以为for只执行一次，但实际上是两次哦。

递归式的完整推导 #

再整体看analizz(n)的执行流程：

1. 初始化c=1和k=n*n都是O(1)的操作，可忽略。
2. while循环的次数：初始k是n²，每次减2直到k≤1，循环次数约为n²/2，也就是Θ(n²)的时间成本，对应递归式里的cn²项。
3. 每一轮while循环中，除了k=k-2的O(1)操作，还会执行上述的for循环，触发两次analizz(n/2)的递归。

所以完整的递归式就是：
T(n) = 2T(n/2) + Θ(n²)

最终时间复杂度计算 #

用主定理来分析这个递归式：

• 这里a=2（每次递归调用2个子问题），b=2（子问题规模是n/2），f(n)=Θ(n²)
• 计算log_b a = log2(2) = 1，而f(n)=n²的增长阶比n^1高，满足主定理的情况3（正则条件也满足：2f(n/2)=2(n²/4)=n²/2 ≤ c*n²，c=1/2<1），因此最终时间复杂度是O(n²)

你之前直觉的O(n²)结果是对的，递归调用的部分并没有主导时间复杂度，因为n²的增长速度远快于递归带来的开销。

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