big O的定义是:
O(f(n))= {g | 存在N并且c> 0使得g(n)
用英语来说,O(f(n))是最终增长率小于或等于f的所有函数的集合。
因此O(n)= O(2n)。就渐进复杂性而言,任何一个都不比另一个“更快”。它们代表相同的增长率-即“ 线性 ”增长率。
O(n)是O(2n)的子集: 令g是O(n)中的一个函数。那么存在N并且c> 0使得对于所有n> N的g(n)
O(2n)是O(n)的子集: 令g是O(2n)中的一个函数。那么存在N且c> 0,因此对于所有n> N,g(n)
通常,当人们指渐近复杂性(“大O”)时,他们指的是规范形式。例如:
(以下是更完整的列表:常见时间复杂度表)
所以通常您会写O(n),而不是O(2n);O(n log n),而不是O(3 n log n + 15 n + 5 log n)。