为何时间复杂度O(n²)的算法也属于O(n)？求通俗解释与实例

你可能搞反了大O符号的逻辑——一个时间复杂度为O(n²)的算法，不可能同时属于O(n)；但反过来，O(n)的算法一定属于O(n²)。这得从大O符号的核心定义说起：

大O描述的是算法运行时间的渐近上界——当输入规模n足够大时，算法的运行时间不会超过某个常数乘以f(n)的增长速度。用数学语言说：

若存在常数C > 0 和 n₀ ≥ 0，使得当n ≥ n₀时，算法的实际运行时间T(n) ≤ C * f(n)，则称T(n) = O(f(n))。

举两个通俗例子： #

1. O(n)算法属于O(n²)的情况
   比如写一个遍历数组的简单算法：

   def traverse(arr):
       for num in arr:
           print(num)
   

   这个算法的运行时间T(n)=n（n是数组长度）。对于f(n)=n²，我们可以取C=1，n₀=1——当n≥1时，n ≤ 1*n² 显然成立（比如n=5，5≤25；n=100，100≤10000）。所以这个O(n)的算法，同时也满足O(n²)的定义（因为n²是比n更宽松的上界）。

2. O(n²)算法不能属于O(n)的情况
   再看一个双重循环的算法：

   def print_pairs(arr):
       for i in arr:
           for j in arr:
               print(i, j)
   

   这个算法的运行时间T(n)=n²。现在假设它属于O(n)，那需要找到常数C和n₀，使得当n≥n₀时，n² ≤ Cn。整理一下不等式得n ≤ C——但n可以无限增大，当n超过C的时候（比如C=100，n=101），101²=10201 > 100101=10100，不等式不成立。不存在这样的固定C能满足所有足够大的n，所以O(n²)的算法不可能属于O(n)。

总结 #

大O符号是“上界”，意味着更宽松的上界可以包含更严格的——比如O(n)是更严格的上界（增长慢），O(n²)是更宽松的上界（增长快），所以符合O(n)的算法一定符合O(n²)，但反过来不行。你的笔记大概率是写反了逻辑。

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