计算规则

如果一个算法对于一个数学函数 f 执行一系列的步骤 f(N) 次，他需要 O(f(N)) 步。

如果一个算法对于函数 f 执行了一个需要 O(f(N)) 步的步骤， 然后对于函数 g 执行了第二个需要 O(f(N)) 步的操作，这个算法的总体复杂度是 O(f(N) + g(N))。

如果一个算法的复杂度是 O(f(N) + g(N))， 并且对于足够大的N，函数 f(N) 远大与 g(N)，这个算法的性能可以被简化为 O(f(N))。

如果一个算法执行了一个需要 O(f(N)) 步的操作，对于操作中的每一(步执行了另外 O(g(N)) 步，这个算法的总体复杂度是 O(f(N) * g(N))。

忽略常数的倍数。如果 C 是一个常数， O(C * f(N)) 等同于 O(f(N))，并且 O(f( C * N)) 等同于 O(f(N))。

常见复杂度

• O(1)
• O(log N)
• O(sqrt(N))
• O(N)
• O(N log N)
• O(N ^ 2)
• O(2 ^ N)
• O(N!)