这段C语言递归代码的时间复杂度是O(n)还是O(logN)？求解析

结论先行：这段代码的时间复杂度确实是O(n)，下面一步步拆解原因：

1. 定义递归时间复杂度函数 #

设T(n)为处理n个元素（即q - p + 1 = n）时，函数F的总执行时间：

• 当n = 1（p == q）：仅执行L[p] * L[p]和返回操作，属于常数时间，即T(1) = O(1)。
• 当n > 1（p < q）：函数会将问题拆分为两个规模为n/2的子问题（p到r、r+1到q各占约一半元素），分别调用一次F，再执行两次乘法和一次加法（均为常数时间操作）。因此递推公式为：

  T(n) = 2 * T(n/2) + O(1)
  

2. 用主定理求解递推式 #

根据算法复杂度的主定理，对于形如T(n) = a*T(n/b) + f(n)的递推式：

• 这里a=2（每次递归拆分为2个子问题），b=2（每个子问题规模是原问题的1/2），f(n)=O(1)（额外操作是常数时间）。
• 计算log_b a = log₂2 = 1，而f(n) = O(n⁰)，显然0 < 1，符合主定理的第一种情况，因此T(n) = O(n¹) = O(n)。

3. 纠正对递归深度的误解 #

你可能误将递归深度当成了时间复杂度：这段递归的深度确实是O(logn)（每次问题规模减半，层数是log₂n），但时间复杂度统计的是所有递归调用的总次数，而非层数。
以n=8为例：

• 第1层（顶层）：1次调用
• 第2层：2次调用
• 第3层：4次调用
• 第4层：8次调用
  总调用次数是1+2+4+8=15，约等于2n，显然是线性规模，对应O(n)的复杂度。

补充：代码的实际计算逻辑 #

顺带提一句，这段代码的实际功能是计算数组中所有元素的平方和乘以2^log₂n（也就是n），比如n=8时，结果等于8*(1²+2²+3²+4²+5²+6²+7²+0²)，这也从侧面验证了每个元素的平方都会被计算n次（因为每次递归都会把结果乘以2，经过log₂n层后，初始的平方值会被乘2^log₂n =n次），总操作次数和元素数量成正比。

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