算法效率：大O记法

BZR

本来不想细究这个的，但是最近被USACO的题折磨得不轻，又加上刚好看到讲这个的文章，就想着研究一下发个帖子吧。
在具体讲大O记法之前，先看2组代码：

1. def sum(n):
   
2.   s = 0
   
3.   for i in range(n + 1):
   
4.     s += i
   
5.   return s

复制代码

1. def sum2(n):
   
2.   return n * (n + 1) // 2

复制代码

这两组代码都是计算前n个整数之和。
第一个算法的思路是使用一个初始值为0的变量，然后遍历n个整数，并将值逐一累加到这一变量上；
第二个算法就是利用公式（n(n + 1) / 2），避免循环。
我们都知道，这两组代码的效率是不一样的。如果我们对它们求前1000000个整数的和这一操作进行计时：

1. def sum(n):
   
2.   start = time.time()
   
3.   s = 0
   
4.   for i in range(n + 1):
   
5.     s += i
   
6.   end = time.time()
   
7.   return s, end - start
   
8. for i in range(5):
   
9.   print(sum(1000000))

复制代码

第一个函数运行结果如下：
(500000500000, 0.03009796142578125)
(500000500000, 0.019148826599121094)
(500000500000, 0.019774913787841797)
(500000500000, 0.019537687301635742)
(500000500000, 0.019414186477661133)


......差不多就在0.02秒
如果对第二个函数做同样的基准测试，n分别取10000、100000、1000000、10000000、100000000，会得到（近似后）：
(50005000, 0.00000095)
(5000050000, 0.00000191)
(500000500000, 0.00000095)
(50000005000000, 0.00000095)
(5000000050000000, 0.00000119)
注：不同电脑有不同结果
关于这个结果，有两点要注意。首先，所有的执行时间都比之前的函数短。其次，不管n取什么值，函数的执行时间都较稳定。


大O记法
接下来真正讲大O记法。当我们试图摆脱程序和计算机的影响来描述算法的效率时，对算法的操作或步骤进行量化非常重要。如果将每一个步骤看成基本计算单位，那么算法的执行时间就可以表述为解决问题所需要的步骤数。
对于之前的累加函数，计算组合所用的赋值语句的数量就是一个好的基本计算单位。在第一个函数中，赋值语句是1（s = 0）加上n（s += i）次。我们暂且将其定义为函数T，令T(n) = 1 + n。参数n常被称作问题规模，可以将函数解读为“当问题规模为n时，解决问题所需的时间是T(n)，即需要1+n步”。
在我们的累加函数中，用累加次数定义问题规模是合理的。我们可以说处理前100000个整数的问题规模比处理前1000个整数的大。所以前者运行的时间比后者长就很合理。


而计算机科学学家分析得出，随着问题规模的增长，T(n)函数的某一部分会比其余部分增长得更快。起主导作用的那一部分最后会被用于比较。数量及函数描述的是在n增长的时候，T(n)增长最快的部分。
数量级（order of magnitude）常被称作大O记法（O指order），记作O( f (n))。这个计法提供了计算所需要实际步骤数的一个近似值。
对于我们上面的例子T(n) = 1 + n，随着n越来越大，常数1对最终结果的影响会越来越小。所以如果要给出T(n)的近似值，可以舍去1，直接说执行时间是O(n)。注意，1对于T(n)来说是重要的，但是随着n的增长，近似值在没有1的情况下也会很精确。


以下是一些常见的大O函数：

1	常数
logn	对数
n	线性
nlogn	线性对数
n^2	平方
n^3	立方
2^n	指数

如上图（来源：《Python数据结构与算法分析（第3版）》2.2.1），当n较小时，这些函数之间的界限不是很明确，很难看出谁起主导作用。但随着n的增长，他们之间的差别就很明显了。


如何进行性能分析
那么如何用大O计法进行代码的性能分析呢？
看一下以下代码例子（假设n是已经定义了的常数）：

1. a = 5
   
2. b = 6
   
3. c = 10
   
4. for i in range(n):
   
5.   for j in range(n):
   
6.     x = i ** 2
   
7.     y = j ** 2
   
8.     z = i * j
   
9. for k in range(n):
   
10.   p = a * k + 100
    
11.   q = b ** 2
    
12. d = c + 2025

复制代码

赋值操作的数量是4项之和：T(n) = 3 + 3n^2 + 2n + 1。第1项是常数3，对应起始部分的3个赋值语句。第2项是3n^2，因为有3个语句要在二重循环中重复n^2次。第3项是2n，因为有两个语句要循环n遍。第4项是常数1，因为最后还有一个赋值。
化简并降幂排列：T(n) = 3n^2 + 2n + 4
很明显，n^2起主导作用，所以这段代码的时间复杂度是O(n^2)。再次强调，当n变大时，其他项以及主导项的系数都可以忽略。

Ray

楼主可以查询并细分一下big O big Ω和big Θ Notation，这些东西的定义有什么联系和区别

脆脆大奶酪

初学大O的时候觉得这玩意很简单，后来用的多了发现里头门道还挺多的，这里补充一些查到的数学性质：
O(f(n))+O(g(n))=O(max(f(n),g(n)))加法规则
O(f(n))⋅O(g(n))=O(f(n)⋅g(n))乘法规则
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)常见复杂度大小排序
O(loga​n)=O(logb​n)由于换底公式所有对数函数的复杂度可以视为相同

脆脆大奶酪

Ray 发表于 8-11-2025 22:33
楼主可以查询并细分一下big O big Ω和big Θ Notation，这些东西的定义有什么联系和区别 ...

我先搬运一下数学定义：
f(n)=O(g(n))正式的数学定义：存在正常数c、n、n0，当 n>n0 的时，任意的 f(n) 符合 0 <= f(n) <= c.g(n)
f(n)= Ω(g(n)) 正式的数学定义：存在正常数c、n、n0，当 n > n0 的时，任意的 f(n) 符合 0 <= c.g(n) <= f(n)
f(n)= θ(g(n)) 正式的数学定义：存在正常数c1、c2、n、n0，当 n > n0 的时，对于任意的f(n）对符合 c1.g(n) <= f(n) <= c2.g(n)，c1.g(n)、c2.g(n)都是渐进正函数（当n趋于无穷大的时候，f(n)为正）
当且仅当函数 f(n) = O(g(n)) 并且 f(n）= Ω(g(n)) 时，才有 f(n) = θ(g(n))

脆脆大奶酪

脆脆大奶酪 发表于 8-11-2025 22:58
我先搬运一下数学定义：
f(n)=O(g(n))正式的数学定义：存在正常数c、n、n0，当 n>n0 的时，任意的 f(n) 符 ...

可以看到大O类似上界，大Ω类似下界，因此分别代表了最坏/最优复杂度
而当最坏最优复杂度相同时，才有大θ，可以理解为时间复杂度基本稳定在这一水平

BZR

脆脆大奶酪 发表于 8-11-2025 22:58
我先搬运一下数学定义：
f(n)=O(g(n))正式的数学定义：存在正常数c、n、n0，当 n>n0 的时，任意的 f(n) 符 ...

研究了亿会会后，我来当数学翻译了。注：以下“.”是乘号
1. 大O
定义：若存在正整数c和n_0，使得对所有n >= n_0，有 f (n) <= c.g(n)，则称 f (n) = O(g(n))。
也就意味着f(n)的增长率不超过g(n)，即g(n)是f(n)的上界，这用于描述算法的最坏时间复杂度；
例：2n^2 + 3n + 1 = O(n^2)，因为当 c = 3 和 n_0 = 2 时，2n^2 + 3n + 1 <= 3n^2。
再比如：我们遍历一个数组查找元素，最坏情况要查n次 -> O(n)；
或者是冒泡排序，最坏情况要比较n^2次 -> O(n^2)。


2. 大Omega
定义：若存在正整数c和n_0，使得对所有n >= n_0，有 f (n) >= c.g(n)，则称 f (n) = Omega(g(n))。
也就意味着f(n)的增长率不低于g(n)，即g(n)是f(n)的下界，这用于描述算法的最佳时间复杂度；
例：n^2 + 100n = Omega(n^2)，因为当 c = 1 和 n_0 = 1 时，n^2 + 100n >= n^2。
再比如：二分查找在最佳情况下只需要1次比较 -> Omega(1)。


3. 大Theta
定义：若存在正整数c_1，c_2，n_0，使得对所有n >= n_0，有 c_1.g(n) <= f (n) <= c_2.g(n)，则称 f (n) = Theta(g(n))。
也就意味着f(n)的增长率与g(n)同阶，同时满足 f(n) = O(g(n)) 和 f(n) = Omega(g(n)) ，这用于描述算法的平均时间复杂度；
例：1/2 n^2 - 3n = Theta(n^2)，因为当 c_1 = 1/4，c_2 = 1 和 n_0 = 12 时，1/4 n^2 <= 1/2 n^2 - 3n <= n^2。
比如：遍历数组查找元素，无论最好最坏都是O(n) -> Theta(n)。

Ray

BZR 发表于 8-12-2025 10:08
研究了亿会会后，我来当数学翻译了。注：以下“.”是乘号
1. 大O
定义：若存在正整数c和n_0，使得对所有n  ...

主播这是学过数学的