一、算法性能评估

概论

时间复杂度
空间复杂度

时间复杂度

规模：数据的大小对算法至关重要，不同量级有不同的速度，比如水 vs 水杯: 水
测试环境：环境的快慢对算法至关重要，在不同测试环境，速度也不同，比如手机 vs 电脑: 电脑

大O表示法

def tmp(n):
    add = 0  # 运行 1unit 次
    for i in range(n):  # 运行 nunit 次
        add += i  # 运行 nunit 次
    return add

假设每行代码的运行时间为1unit
总共运行： $T(n) = (2n+1)*unit`$
$T(n) = O(f(n))$ ， $O$ 表示 $T(n)$ 与 $f(n)$ 成正比
$O$ 表示渐近时间复杂度
表示代码执行时间数据规模增长的变化趋势

当 n 很大时，低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，就可以记为： $T(n) = O(n)$ ； $T(n) = O(n^2)$

只关注循环次数多的代码

def tmp(n):
    add = 0  
    for i in range(n):
        add += i
    return add

$O(n)$ ，将规模变为无穷大，就不必关注循环次数少或没有循环的代码

选大量级

def tmp(n):
    for i in range(999):
        print(123)

    for i in range(n):
        print(123)

    for i in range(n):
        for j in range(n):
            print(2)

$O(n^2)$ ，最后一个循环为n的2次方

嵌套循环要乘积

def tmp(n):
    for i in range(n):
        a(i)

def a(n):
    for i in range(n):
        print('C')

$O(n^2)$ ，嵌套循环要乘积，这里表示n的2次方

常见复杂度分析

非多项式量级（过于低效）： $O(2^n)$ 和 $O(n!)$
多项式量级： $O(1)$ , $O(logn)$ , $O(n)$ , $O(nlogn)$ , $O(n^k)$

$O(1)$

不是说只有一行代码
是指代码的执行时间不随着规模增加

a=2
b=3
c=4

$O(logn)$

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

$i = 2, 2^2, 2^3, ... , 2^x$

退出循环的条件是： $2^x = n$ ，即 $x = log_2n$ ，时间复杂度为 $O(log_2n)$

def tmp(n):
    i = 1
    while i < n:
        i = i * 3

$log_3n$ 就等于 $log_32 * log_3n$ ，所以 $O(log_3n) = O(C * log_2n)$ ，其中 $C=log_32$ 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 $O(Cf(n)) = O(f(n))$ 。所以， $O(log_2n)$ 就等于 $O(log_3n)$ 。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 $O(logn)$

$O(m+n)$ 、 $O(m*n)$

def tmp(m, n):
    for i in range(m):
        print(1)

    for i in range(n):
        print(2)

空间复杂度

空间复杂度是 存储空间与数据规模之间的增长关系
渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度(asymptotic space complexity)，表示算法的存储空间与数据规模之间的增长关系。

渐进时间复杂度：表示算法的 执行时间 与数据规模之间的增长关系。
渐进空间复杂度：表示算法的 存储空间 与数据规模之间的增长关系。

def tmp(n):
    a = [1]*n
    for i in a:
        print(i)

空间复杂度是： $O(n)$

一、算法性能评估

概论

时间复杂度

大O表示法

只关注循环次数多的代码

选大量级

嵌套循环要乘积

常见复杂度分析

、

空间复杂度

推荐阅读更多精彩内容

$O(m+n)$ 、 $O(m*n)$