三次递归场景下递推式T(n)推导与主定理求解时间复杂度咨询

1. 递推式与边界条件正确性验证 #

首先说明：原代码存在笔误，第一个if分支的len(L)应为len(mylist)，否则会触发未定义变量错误，以下分析默认修正该笔误。

• 递推式部分：你对两次相同递归调用的规模计算是正确的，t = n//3，所以len(mylist[:len(mylist)-t-1]) = n - t -1 ≈ 2n/3，对应T(⌊2n/3⌋)没有问题。但你对第二个递归调用的规模计算有误：mylist[t:len(mylist)-1]的长度为(n-1) - t ≈ 2n/3，和前两次递归的规模基本一致，并非你推导的⌊n/3⌋。如果你是做假设性的递推式推导，那2T(⌊2n/3⌋) + T(⌊n/3⌋)的数学形式是自洽的，但和实际代码的递归逻辑不符。
• 边界条件部分：你的设定存在小误差，n=2时虽然没有进入递归，但函数调用、分支判断本身存在固定常数开销，所以T(2)应该和T(0)、T(1)一样为常数（可统一记为Θ(1)，或设为1），而非0。不过边界条件的常数取值不影响最终时间复杂度的量级判定。

2. 时间复杂度推导方法 #

两种场景的推导方法分别如下：

场景1：按你给出的假设递推式T(n) = 2T(⌊2n/3⌋) + T(⌊n/3⌋) + Θ(1)求解 #

该递推式的非递归开销f(n)为常数级Θ(1)，采用代入验证法求解：
我们假设T(n) = O(n^k)，即存在常数c>0，当n足够大时T(n) ≤ c·n^k。
将假设代入递推式，忽略向下取整和常数项后可得：
c·n^k ≤ 2c·(2n/3)^k + c·(n/3)^k
两边约去c·n^k，得到系数等式：
2·(2/3)^k + (1/3)^k = 1
试值可得k=2时刚好满足等式：2*(4/9) + 1/9 = 1，因此该递推式的时间复杂度为Θ(n²)。

场景2：按实际代码的正确递推式T(n) = 3T(⌊2n/3⌋) + Θ(1)求解 #

该递推式符合主定理的标准形式T(n) = aT(n/b) + f(n)，其中a=3，b=3/2，f(n)=Θ(1)：

1. 计算临界指数：log_b a = log_{3/2}3 = ln3/(ln3 - ln2) ≈ 2.71
2. 由于f(n)=Θ(1)多项式小于n^2.71，满足主定理第一种情况
   因此实际代码的时间复杂度为Θ(n^{log_{3/2}3})，近似为Θ(n^2.71)。

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