Lesson 02

时间复杂度Time Complexity

案例

方法 1

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

保留最高值

伪代码

 $Max2Sum(A, n)$

     $sum \leftarrow 0$

     $\text{for } i \leftarrow 1 \text{ to } n$

         $\text{for } j \leftarrow 1 \text{ to } n$

             $\text{if } i != j \text{ then}$

                 $\text{if } A_i + i_j > sum \text{ then}$

                     $sum = A_i + A_j$

 $\text{return } sum$

方法 2

循环一遍找到最大值

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

伪代码

 $Max2Sum(A, n)$

     $max_1 \leftarrow 0$

     $\text{for } i \leftarrow 1 \text{ to } n$

         $\text{if } A_i > max_1 \text{ then}$

             $max_1 \leftarrow A_i$

     $max_2 \leftarrow 0$

     $\text{for } i \leftarrow 1 \text{ to } n$

         $\text{if } A_i > max_2 \text{ and } A_i != max_1 \text{ then}$

             $max_2 \leftarrow A_i$

 $\text{return } max_1 + max_2$

方法 3

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

伪代码

 $Max2Sum(A, n)$

     $max_1 \leftarrow 0$

     $max_2 \leftarrow 0$

     $\text{for } i \leftarrow 1 \text{ to } n$

         $\text{if } A_i > max_2 \text{ then}$

             $max_2 \leftarrow A_i$

         $\text{if } A_i > max_1 \text{ then}$

             $Swap(max_1, max_2)$

 $\text{return } max_1 + max_2$

相对优势与绝对优势

大于某个值之后

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

相对优势

什么是

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

案例

情况	$f(n) = n$	$g(n) = 2n, c \cdot g(n)$	更好
$n = 10, c = 1$	10	20	$f(n)$
$n = 100, c = 1$	100	200	$f(n)$
$n = 10, c = 1/10$	10	2	$g(n)$
$n = 100, c = 1/10$	100	20	$g(n)$

实际

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

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

函数图

 $\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)$

绝对优势

什么是

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

案例

情况	$f(n) = n$	$g(n) = n^2, c \cdot g(n)$	更好
$n = 2, c = 1$	2	4	$f(n)$
$n = 2, c = 1/10$	2	0.4	$g(n)$
$n = 20, c = 1/10$	20	40	$f(n)$
$n = 20, c = 1/100$	20	4	$g(n)$
$n = 200, c = 1/100$	200	400	$f(n)$
$n = 200, c = 1/1000$	200	40	$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$ 就在一个档位，时间复杂度一样

不同档位

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

$n$	时间增长慢	低档位	时间复杂度低	更好
$n^2$	时间增长快	高档位	时间复杂度高	不好

$\Theta(n)$

什么是

如果 $T_1(n) = f(n)$ 和 $T_2(n) = g(n)$ 在一个速度档位上

就说 $f(n) = \Theta(g(n))$

含义

意思就是 $f(n)$ 与 $g(n)$ 档位相同

集合含义

$\Theta(g(n))$ 代表跟 $g(n)$ 档位相同的那些函数所组成的集合

那么 $f(n) = \Theta(g(n))$

意思就是 $f(n) \in \Theta(g(n))$

样例

$n = \Theta(n)$

$n = \Theta(2n)$

$O(n)$

什么是

如果 $T_1(n) = f(n)$ 和 $T_2(n) = g(n)$ 在一个速度档位上

或者 $T_1(n) = f(n)$ 比 $T_2(n) = g(n)$ 有绝对优势

就说 $f(n) = O(g(n))$

含义

意思就是 $f(n)$ 档位差不过 $g(n)$

集合含义

$O(g(n))$ 代表跟 $g(n)$ 档位相同以及更好的那些函数所组成的集合

那么 $f(n) = O(g(n))$

意思就是 $f(n) \in O(g(n))$

样例

$n = O(n)$

$n = O(n^2)$

$\Theta(n)$ 与 $O(n)$ 对比

如果 f(n) = \Theta(g(n))，那么 f(n) = O(g(n))。

不能反过来。

练习

以下哪个是对的

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)$

值	意义
1	档位一样
0	$f(n)$ 比 $g(n)$ 有绝对优势
$\infty$	$g(n)$ 比 $f(n)$ 有绝对优势

Lesson 02

时间复杂度Time Complexity

案例

方法 1

伪代码

方法 2

伪代码

方法 3

伪代码

相对优势 与 绝对优势

大于 某个值之后

相对优势

什么是

案例

实际

函数图

绝对优势

什么是

案例

实际

函数图

优势研究

侧重点

代码可读性

速度档位

速度档位

相同档位

不同档位

Θ(n)\Theta(n)Θ(n)

什么是

含义

集合含义

样例

O(n)O(n)O(n)

什么是

含义

集合含义

样例

Θ(n)\Theta(n)Θ(n) 与 O(n)O(n)O(n) 对比

练习

以下哪个是对的

完整对比

相关推论 与 常用数学公式

证明档位

多项式后面抹除

比如

常量系数抹除

比如

log 相关公式

去底

去幂

去系数

档位列表

相对优势与绝对优势

大于某个值之后

$\Theta(n)$

$O(n)$

$\Theta(n)$ 与 $O(n)$ 对比

相关推论与常用数学公式