3 时间复杂度

学习目标:

理解究竟什么是时间复杂度

3.1 步骤计算

为了理解时间复杂度,我们先来算一下我们刚才使用的 方法一 和 方法二 的总步骤数量.

方法一:

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

方法二

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

规律总结:

以方法二为例：通过规模的不同，来计算时间总量T

总量为1000：
T = 1001*1001*10 次

总量为2000:
T = 2001*2001*10 次

总量为3000：
T = 3001*3001*10 次

总量为n：
T = n*n*10 次

我们就将上面的算数，总结为一个表达式：
T(n) = n*n*10
我们把这个表达式称为：时间复杂度

  通过上面的总结出来的表达式，我们知道，表达式中具体的数字10其实处于一个次要的关系，其实我们在总结规律的时候，其实就是将所有和主干无关的条件都抛开，就分析主干，在我们这里其实本质上是T和n的关系。

  如果将次要关系都慢慢的省略掉的话，就会逐渐演变成一个渐变的函数O(g(n)),我们一般把这种渐进的表示方法，称为：大O记法
  渐变函数(规律函数)：其实就是所谓的“g(n)长大后我就成了你O(g(n))”. 他的重点是：规律趋势,所以，我们可以将这个表达式，最终演变成一个T和n的表达式:

• 假设存在算法A函数g(n)=n*n*10，总结规律时候，把无关紧要的条件10去除掉，就变成了一个渐进的算法A函数O(g(n))，所以最终的时间T(n)=O(g(n))

• 我们一般称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，标记为T(n)

小结:

时间复杂度实际上就是在规模量级上对算法的衡量