最优时间复杂度(不可靠)

最坏时间复杂度(保证)

平均时间复杂度(平均状况)

不同语句的时间复杂度:

(1)顺序语句:使用加法

(2)循环语句:使用乘法

(3)分支语句:使用坏时间复杂度

例如:如下代码的时间复杂度:

#!/usr/bin/env python
#! _*_ coding:UTF-8 _*_

for a in range(1001):
    for b in range(1001):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print "a=%d, b=%d, c=%d" % (a, b, c)

首先,最外面两层是循环语句,所以使用乘法

然后,是顺序语句,使用加法

最后,是分支语句,使用最坏时间复杂度

T(n) = n * n * (1 + max(1, 0))

  = n^2 * 2

  = O(n^2)

3.常见时间复杂度

12O(1)常数阶
2n+3O(n)线性阶
3n^2+2n+1O(n^2)平方阶
5logn+20O(logn)对数阶
2n+3nlogn+19O(nlogn)nlogn阶
6n^3+2n^2+3n+4O(n^3)立方阶
2^nO(2^n)指数阶

4.常见时间复杂度的大小比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

05-11 09:37