Big-Oh记号判断疑问：阶数高于T(n)的上界是否成立？

Big-Oh记号问题解答 #

核心结论先给：

• 问题(3)的结论为真
• 线性阶的算法时间复杂度，严格来说确实可以用O(n²)等更高阶的Big-Oh记号表示上界，只是这种写法在工程实践中没有实用价值。

依据（基于Big-Oh的严格数学定义）

Big-Oh的正式定义为：若存在正的常数c和n₀，使得对所有n ≥ n₀，都满足 T(n) ≤ c·f(n)，则可称 T(n) = O(f(n))。
这个定义只要求f(n)是T(n)的上界，没有要求是最紧的上界，所以：

1. 对于问题(3)的T(n) = 10n^4 + 850n，取c=860、n₀=1，当n≥1时n^30 ≥ n^4，因此 10n^4 + 850n ≤ 10n^4 + 850n^4 = 860n^4 ≤ 860·n^30，完全满足Big-Oh的定义，所以结论成立。
2. 对于线性阶T(n)=O(n)的算法，同理，我们可以取c=1、n₀=1，对所有n≥1都有T(n) ≤1·n ≤1·n²，因此严格来说T(n)=O(n²)是正确的表述。

额外注意

我们日常讨论算法复杂度时，默认说的是渐近紧上界，也就是阶数最小的那个Big-Oh上界。如果把上界放得太宽，比如把线性算法写成O(n^100)，虽然严格数学上没错，但完全无法体现算法的实际性能优势，没有参考意义，所以工程上不会这么用。

三个问题的统一结论汇总

• T(n) = 10n^4 + 850n = O(n^3)：假，n足够大时四次项增速远高于三次项，不存在符合要求的常数c和n₀
• T(n) = 10n^4 + 850n = O(n^4)：真，是最紧的上界，也是日常会使用的表述
• T(n) = 10n^4 + 850n = O(n^30)：真，数学上成立，但无实际参考价值

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