big O的定义是：

O（f（n））= {g | 存在N并且c> 0使得g（n） N}

用英语来说，O（f（n））是最终增长率小于或等于f的所有函数的集合。

因此O（n）= O（2n）。就渐进复杂性而言，任何一个都不比另一个“更快”。它们代表相同的增长率-即“ 线性 ”增长率。

证明：

O（n）是O（2n）的子集： 令g是O（n）中的一个函数。那么存在N并且c> 0使得对于所有n> N的g（n）
N的g（n）<（c / 2）* 2n。因此g在O（2n ）。

O（2n）是O（n）的子集： 令g是O（2n）中的一个函数。那么存在N且c> 0，因此对于所有n> N，g（n）
N，g（n）<2c * n。因此，g在O（n）中。

通常，当人们指渐近复杂性（“大O”）时，他们指的是规范形式。例如：

• 对数：O（log n）
• 线性：O（n）
• 线性运算：O（n log n）
• 二次：O（n 2）
• 指数：O（c n）对于固定的c> 1

（以下是更完整的列表：常见时间复杂度表）

所以通常您会写O（n），而不是O（2n）；O（n log n），而不是O（3 n log n + 15 n + 5 log n）。