机器学习之数学基础(六)～时间复杂度和空间复杂度

算法背景 background

1. 时间复杂度 Time Complexity

1.1 时间复杂度分类

1.1.1 O(1) 常数阶

1.1.2 O(n) 线性阶

1.1.3 O(n^2) 平方阶

1.1.4 O(logn) 对数阶

1.1.5 O(nlogn) 线性对数阶

1.1.6 O(2^n) 指数阶

1.1.7 O(n!) 阶乘阶

1.1.8 时间复杂度分类

1.2 时间复杂度 Rules

1.3 时间复杂度计算流程

2. 空间复杂度 Space Complexity

参考

算法背景 background

核心：Algorithms + Data Structures = Programs

-》高性能的代码 = 相应速度快的代码。需要初级程序员了解算法，灵活地运用算法。

-》发明设计一款算法：要去推导证明算法的可行性。

数据结构是为算法服务的，而算法又需要作用在特定的数据结构上。

-》谁的算法快，谁的算法更优！！

如果两种算法实现的速度差不多，那我们还可以去评价算法所占用的空间。

时间复杂度：执行当前算法所消耗的时间。--》快

空间复杂度：执行当前算法所消耗的内存空间。--》省

1. 时间复杂度 Time Complexity

时间复杂度 time complexity：全称为算法的渐进时间复杂度，表示执行当前算法的最高运算次数，记作T(n)=O(f(n))，表示算法的执行时间与数据规模n之间的增长关系。

核心：分析算法时间复杂度的关键在于分析出代码循环了多少次！

Note：时间复杂度反映的只是一个趋势，也就是随着n的变化，算法执行时间的也是会变化的。

1.1 时间复杂度分类

1.1.1 O(1) 常数阶

本质：复杂度与数据规模n无关！

public static void print(int n){
    int a = 1;
    int b = 2;
    int c = 3;
    int sum = a + b + c;
    System.out.println(sum);
}

1.1.2 O(n) 线性阶

对应：单层for循环

public static void print1(int n){
    int a = 0;  // 复杂度：T
    for (int i=0;i<n;i++){
        System.out.println(i);  // 复杂度：n*T
    }
}

假设每一行代码的执行时间是T，那上段代码的执行时间T(n)= T+n*T=(n+1)T.

->算法时间复杂度 Rule 1: 常量可以被忽略。

所以，T(n) = nT = O(n).

1.1.3 O(n^2) 平方阶

双层循环平方阶 $O(n^2)$ ；

三层循环立方阶 $O(n^3)$ ；

K层循环就是K次立方阶。

1.1.4 O(logn) 对数阶

对应：while 循环

e.g. 二分查找，二叉树问题

public static void print2(int n){
    int i=1;
    while (i <= n) {
        i = i * 2;
    }
}

分析算法时间复杂度的关键在于分析出while循环了多少次。

1->2->4->8...

$2^x=n$ ，只要能得到x的值，就得到了循环次数。

$x = {log_2}^{n} = O({log_2}^{n})$

同理， ${log_3}^{n} = {log_3}^{2} * {log_2}^{n} = O({log_2}^{n})$ ，不管底数是多少，最终都可以转换为以2为底的对数阶 =》 $O({log_2}^{n}) = O({log}^{n})$

=》算法时间复杂度 Rule 2: 当循环中下标以指定倍数形式衰减，那么这就是一个对数阶。

1.1.5 O(nlogn) 线性对数阶

时间复杂度 = 代码执行次数！

for (int j=1;j<=n;j++){
    int i=1;   // 时间复杂度 O(n)
    while (i <= n) {
        i = i * 2;  // 时间复杂度 O(logn)
    }
}

嵌套代码的时间复杂度 $O(nlog_n)$ = 单独的嵌套内循环 * 单独的嵌套外循环 $O(n) * O(logn)$

= 嵌套内外循环时间复杂度之和 $O(n) + O(nlogn)$

1.1.6 O(2^n) 指数阶

def exponential(n: int) -> int:
    """指数阶（循环实现）"""
    count = 0
    base = 1
    # 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
    for _ in range(n):
        for _ in range(base):
            count += 1
        base *= 2
    # count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count

单独的嵌套内循环次数无法计算

无法利用乘积求时间复杂度，只能用加法了

嵌套外循环时间复杂度 O(n)

base：1, 2, 4, 8, 2^(n-1)

嵌套内循环次数：等比数列求和公式 $S_n = a \frac{1-r^n}{1-r} \rightarrow 2^n-1$

1.1.7 O(n!) 阶乘阶

def factorial_recur(n: int) -> int:
    """阶乘阶（递归实现）"""
    if n == 0:
        return 1
    count = 0
    # 从 1 个分裂出 n 个
    for _ in range(n):
        count += factorial_recur(n - 1)
    return count

1.1.8 时间复杂度分类

最好时间复杂度、最坏时间复杂度、平均时间复杂度

1.2 时间复杂度 Rules

只要是常数级别，不论n多大，代码效率都是一样的。
忽略常量、低次幂和高次幂系数。
嵌套代码的时间复杂度 $O(nlog_n)$ = 单独的嵌套内循环 * 单独的嵌套外循环 $O(n) * O(logn)$

= 嵌套内外循环时间复杂度之和 $O(n) + O(nlogn)$
在同一个算法中，存在明确大小关系的，可以直接取最大值作为这个算法的复杂度。

多项式时间复杂度关系： $O(1) < O(log_n) < O(n) < O(nlog_n) < O(n^2) < O(n^3)$

指数时间复杂度关系： $O(n^2) < O(2^n) < O(n!) < O(n^n)$

1.3 时间复杂度计算流程

Note：只有可运行的语句才会增加时间复杂度，除了循环外，其他可执行语句的时间复杂读都是O(1)，可以被忽略。

(1) 计算出基本操作的执行次数T(n). 计算算法中每条语句的执行次数；在做算法分析时，一般默认为考虑最坏的情况，而不是考虑循环break or continue情况。

(2) 计算出T(n)的数量级。忽略常量、低次幂和高次幂系数。

(3) 用O表示时间复杂度。只保留最高项

for（i=1;i<=n;++i）
  {
     for(j=1;j<=n;++j)
     {
         c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n^2
          for(k=1;k<=n;++k)
               c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n^3
     }
  }