算法的时间复杂度解读笔记
计算规则
如果一个算法对于一个数学函数 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!)