时间复杂度

案例1

考虑这样一个函数：

def func(n):  
    total = 0  
    for i in range(1, n + 1):  
        total += i  
    return total

它实现了从1 + 2 + 3 + ... + n，即求解从1一直加到n的和是多少。

考虑这一条语句 total += i ,

• 当我传入 n=1 时，它会执行1次
• 当我传入 n=2 时，它会执行2次
• 当我传入 n=3 时，它会执行3次
• 。。。
• 当我传入 n=n 时，它会执行n次

也就是说，它的执行次数与n成正比。

一条语句的重复执行次数称作“语句频度”（Frequency Count）。

重复执行的次数，往往与执行的时间成正比，也就是说，语句频度之和决定了时间复杂度。

时间复杂度通常采用大O记法，这个函数的时间复杂度就是O(n)。

案例2: 这个函数的时间复杂度是多少？

def func2(n, m):  
    for i in range(n * n):  
        print(i)  # 1  
    for j in range(m):  
        print(j)  # 2  
    for k in range(n * n * n):  
        print(k)  # 3

其中语句1会被执行O(n^2)次， 语句2是O(n)次，语句3 是O(n^3)。即 f(n) = n^2 + n + n^3 ，但是一般来说，只看数量级或规模，所以当n足够大，趋近无穷时，f(n) = O(n^3)。也即时间复杂度为 O(n^3)。

案例3：常见时间复杂度

常量阶 O(1)

def o1():  
    x = 0  
    y = x + 1  
    print('hello world', x, y)

线性阶 O(n)

def on(n):  
    for i in range(n):  
        print(i)

平方阶 O(n^2)

def on2(n):  
    for i in range(n):  
        for j in range(n):  # 1
            print(i * j)

可以对比一下这个：

def on2(n):  
    for i in range(n):  
        for j in range(i):  # 2
            print(i * j)

很显然，#1 语句的执行次数比 #2 语句要多。但当n趋近于无穷时，他们的时间复杂度都是在n^{2（n的平方）这个量级。所以，前者的程序执行时间会更长，但两者依然属于O(n}2)这一时间复杂度。

立方阶 O(n^3)

def on3(n):  
    for i in range(n):  
        for j in range(i):  
            for k in range(j):  
                print(i + j + k)

对数阶 O(log_2 n)

def ologn(n):  
    i = 1  
    while i < n:  
        print(i)  
        i *= 2

（这里，下划线表示底数的意思， ^表示指数的意思）

我们来分析一下print(i)语句，每次执行完之后，i都会乘以2，也就是说，i的变化是乘以2，乘以2的平方， 乘以2的三次方，……。

而循环的终止条件是 i >= n，假设print(i)执行m次，也就是只需要 2 ^ m > = n 即可，取临界值即相等的情况，即 2 ^ m = n，推出 m = log_2 n，也就是说，print(i)大概会执行log_2 n 次。

常见时间复杂度的总结

常见时间复杂度按数量级依次递增可排序为：

• 常量阶 O(1)
• 对数阶 O(log_2 n)
• 线性阶 O(n)
• 线性对数阶 O(n log_2 n)
• 平方阶 O(n^2)
• 立方阶 O(n^3)
• k次方阶 O(n^k) （又称多项式阶）
• 指数阶 O(2^n)