python数据结构与算法第三天【时间复杂度计算方法】

时间:2022-02-13 17:14:19

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

最坏时间复杂度(保证)

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

 

不同语句的时间复杂度:

(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.常见时间复杂度

12 O(1) 常数阶
2n+3 O(n) 线性阶
3n^2+2n+1 O(n^2) 平方阶
5logn+20 O(logn) 对数阶
2n+3nlogn+19 O(nlogn) nlogn阶
6n^3+2n^2+3n+4 O(n^3) 立方阶
2^n O(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)