时间复杂度Time Complexity

时间消耗量化

干嘛？

要比较两个算法谁快谁慢

比较需要量化

量化案例

1 2 3 4 5 6 7 8 9 
public boolean exist(int[] arr) {    for (int i = 0; i < arr.length; i++) {        int value = arr[i];        if (value == 0) {            return true;        }    }    return false;}

1 2 3 4 5 6 7 8 9 
function exist(arr: number[]): boolean {    for (let i = 0; i < arr.length; i++) {        const value = arr[i];        if (value === 0) {            return true;        }    }    return false;}

思考

有哪些会影响代码的时间？

影响代码时间的因素

代码

语言

硬件

数据量

数据内容

数据内容分析

最差的情况 Worst Case

平均的情况 Average Case

最好的情况 Best Case

时间消耗的量化基准

代码

当前代码

语言

无视不同语言 同样操作 的时间差异

硬件

忽略硬件的影响 认为是公平竞争

数据量

N

数据内容

针对最差情况的数据内容

时间消耗计算

计算规则

以最小运算单元 为一个量，

对 n 个大小的输入数据求和

用 T(n) 表达

样例

1 2 3 4 5 6 7 8 9 
public boolean exist(int[] arr) {    for (int i = 0; i < arr.length; i++) {        int value = arr[i];        if (value == 0) {            return true;        }    }    return false;}

我们假设以下运算都消耗 1 个单元

赋值 
    i = 0
运算
    i < 3, value == 0
地址跳跃
    arr.length
    arr[0]
组合
    i++ -> i = i + 1

1 2 3 4 5 6 7 8 9 
public boolean exist(int[] arr) {    for (int i = 0; i < arr.length; i++) {  // for (1, (n + 1) x 2, 2n)        int value = arr[i];                 // 1 + 1 \        if (value == 0) {                   // 1      \ x n                  return true;                    }    }    return false;}

  1 + (n + 1) x 2 + 2n
+ 3 x n 
======================
  7n + 3

相对优势 与 绝对优势2233

大于 某个值之后

我们比较大于某个值 $\epsilon$ 后面的

相对优势

什么是

通过对 时间公式 叠加 常量倍数 会影响比较结果

案例

实际

如果设备一样 那么一个比一个好

但是可以通过砸钱在硬件设备上，彻底改变结果

函数图

$\exists \text{ } \epsilon > 0$

$\text{when } n > \epsilon \text{ and } n \rightarrow \infty$

    $\exists \text{ } c_1 > 0, c_1 \cdot g(n) \geq f(n) \text{ and }$

    $\exists \text{ } c_2 > 0, f(n) \geq c_2 \cdot g(n)$

绝对优势

什么是

通过对 时间公式 叠加 常量倍数 不会 影响比较结果

案例

实际

就算通过砸钱在硬件设备上，当数据量大时也无法改变结果

函数图

$\forall \text{ } c > 0$

$\exists \text{ } \epsilon > 0$

$\text{when } n > \epsilon \text{ and } n \rightarrow \infty$

    $c \cdot g(n) \geq f(n) \text{ and }$

优势研究

应该优先专注 提高绝对优势

时间消耗档位

时间消耗档位

相同档位

互相有相对优势的时间函数，被归类到一个时间消耗档位内，他们的时间复杂度一样

$n$ 和 $2n$ 就在一个档位，时间复杂度一样

不同档位

有绝对优势的时间函数，就不会再一个时间消耗档位上，他们的时间复杂度也不一样

时间消耗档位 与 时间复杂度

时间消耗档位 就是 时间复杂度

$\Theta(n)$

什么是

时间消耗档位一样

样例

$n = \Theta(n)$ 意思就是 n 的时间复杂度 = n 的时间复杂度

$n = \Theta(2n)$ 意思就是 n 的时间复杂度 = 2n 的时间复杂度

$O(n)$

什么是

时间消耗档位 一样 或者 相比更低

样例

$n = O(n)$ 意思就是 $n$ 的时间复杂度 $<=$ $n$ 的时间复杂度

$n = O(n^2)$ 意思就是 $n$ 的时间复杂度 $<=$ $n^2$ 的时间复杂度

练习

以下哪个是对的

1. $n = \Theta(n)$

2. $n = \Theta(2n)$

3. $2n = \Theta(n)$

4. $n = \Theta(n^2)$

5. $n^2 = \Theta(n)$

6. $n = O(n)$

7. $n = O(2n)$

8. $2n = O(n)$

9. $n = O(n^2)$

10. $n^2 = O(n)$

完整对比

常用推论与公式

证明档位

$\lim_{n \to \infty} \frac{f(n)}{g(n)}$

多项式后面抹除

如果时间公式为一个多项式，只需要保留最高档位的部分

比如

$T(n) = n^2 + 2n + 1 = O(n^2)$

常量系数抹除

如果时间公式为乘积，可以抹除常量系数

比如

$T(n) = 3n^2 = O(n^2)$

log 相关公式

$a, b, c$ 均为常数

去底

$\log_a n = \frac{\log_c{n}}{\log_c{a}} = \frac{1}{\log_c{a}}\cdot\log_c{n} = O(\log_c{n}) = O(\log{n})$

去幂

$\log{n^a} = a\log{n} = O(\log{n})$

去系数

$\log_{a}{bn} = \log_{a}{b} + \log_a{n} = O(\log_a{n}) = O(\log{n})$

几何序列

$1 + 2 + 4 + 8 + ... = 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k = 2^{k+1} - 1$

档位列表

$O(1) = O(c) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^c) < O(c^n)$

挑战

A

1 2 3 4 5 
public void run(int[] arr) {    for (int i = 0; i < arr.length; i++){        arr[i] = 0;    }}

B

1 2 3 4 5 
public void run(int[] arr) {    for (int i = 1; i < arr.length; i *= 2){        arr[i] = 0;    }}

C

1 2 3 4 5 6 7 
public void run(int[] arr) {    for (int i = 0; i < arr.length; i++){        for (int j = 0; j < arr.length; j++){            arr[i] = arr[j];        }    }}

D

1 2 3 4 5 6 7 
public void run(int[] arr) {    for (int i = 0; i < arr.length; i++){        for (int j = 0; j < i; j++){            arr[i] = arr[j];        }    }}

E

1 2 3 4 5 6 7 
public void run(int[] arr) {    for (int i = 1; i < arr.length; i *= 2){        for (int j = 0; j < i; j++){            arr[i] = arr[j];        }    }}

一些结论

两个 for 循环 不一定会慢

时间复杂度分析

问题

给定一个数组 A 里面都是正整数, 而且没有重复

求取两个数之和的最大值

方法 1

找到所有 两个数 配对的可能

保留最高值

代码

1 2 3 4 5 6 7 8 9 
public int max2Sum(int[] arr) {    int max = Integer.MIN_VALUE;    for (int i = 0; i < arr.length; i++){        for (int j = 0; j < arr.length; j++){            max = Math.max(max, arr[i] + arr[j]);        }    }    return max;}

方法 2

循环一遍 找到最大值

再循环一遍 找到第二个大的值

代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
public int max2Sum(int[] arr) {    int max1 = Integer.MIN_VALUE;    for (int i = 0; i < arr.length; i++){        max1 = Math.max(max1, arr[i]);    }     int max2 = Integer.MIN_VALUE;    for (int i = 0; i < arr.length; i++){        if (arr[i] != max1) {            max2 = Math.max(max2, arr[i]);        }    }     return max1 + max2;}

方法 3

跟方法 2 一样，但只走一趟

代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
public int max2Sum(int[] arr) {    int max1 = Integer.MIN_VALUE;    int max2 = Integer.MIN_VALUE;    for (int i = 0; i < arr.length; i++){        if (arr[i] > max2) {            max2 = arr[i];        }        if (max2 > max1) {            int temp = max1;            max1 = max2;            max2 = temp;        }    }     return max1 + max2;}

分析

方法1

$O(n^2)$

方法2

$O(n)$

方法3

$O(n)$ + One pass

符号解释

一个算法是 $O(n)$ 意思就是这个的代码所产生的时间复杂度 $<=$ $n$ 的时间复杂度

可读性 与 one pass

如果没有 one pass 的要求 且 只有相对优势时

我们可以 专注代码可读性