关于大O符号定义与递归时间复杂度的疑问求解

疑问1：递归式T(n) = T(n/4) + T(n/2) + cn²的大O边界问题 #

你说得完全没错！从大O的严格数学定义来看：如果存在常数C和n₀，当n≥n₀时，T(n) ≤ C·f(n)，那么T(n)=O(f(n))。按照这个标准，O(n³)和O(n² log n)确实都是T(n)的合法上界——毕竟n²的增长速度比n² log n慢，n² log n又比n³慢，既然T(n)被n²约束，那它自然也会被更宽松的n² log n和n³约束。

那为什么题目把T(n)=O(n²)作为“正确答案”？因为这类算法题里的“正确答案”通常默认指向紧确上界（tight upper bound），也就是最精确的那个上界——它不仅是上界，同时也是下界（即T(n)=Θ(n²)），而O(n³)和O(n² log n)是更宽泛的上界，虽然数学上成立，但不是对该递归式复杂度最精准的描述。

我们可以用递归树简单验证：

• 第一层代价是cn²，第二层是c(n/4)² + c(n/2)² = (5/16)cn²，第三层是c(n/16)² + 2c(n/8)² + c(n/4)² = (21/256)cn²，以此类推。
• 这是一个公比为5/16 < 1的等比数列，求和后结果是(16/11)cn²，是常数乘以n²，所以T(n)=Θ(n²)，这意味着O(n²)是紧确的上界，其他选项虽然合法，但不够精准，题目要的是最优解。

疑问2：T(n) = (1/2)n² + 3n的复杂度陈述判断 #

结合常见的选项逻辑，我们逐一分析：

• T(n)=O(n)：不成立。当n趋向无穷大时，(1/2)n²的增长速度远快于n，找不到常数C使得(1/2)n² + 3n ≤ C·n对所有足够大的n成立。
• T(n)=O(n²)：成立。取C=2，当n≥6时，3n ≤ 0.5n²，所以(1/2)n² + 3n ≤ n² ≤ 2n²。
• T(n)=Ω(n²)：成立。取C=1/2，对所有n≥1，(1/2)n² ≤ (1/2)n² + 3n。
• T(n)=Θ(n²)：成立。因为它同时满足O(n²)和Ω(n²)，是紧确的复杂度描述。
• T(n)=Ω(n)：成立。取C=1，对所有n≥1，n ≤ (1/2)n² + 3n显然成立。

所以如果选项包含O(n²)、Θ(n²)、Ω(n)、Ω(n²)，这些都是正确的陈述。

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