1.5. 算法评价标准及分析方法¶

$1+2+3+\cdots+100 = 5050$

$\frac{100\times(1+100)}2 = 5050$

算法的复杂性是度量算法效率、评价其优劣的重要依据.
算法分析技术即利用数学工具, 对每一个具体算法讨论其各种复杂度, 以探讨某种具体算法适用于哪类问题, 或某类问题宜采用哪种算法.
算法复杂性体现在运行该算法所需要的计算机资源的多少上, 所需的资源越多表明该算法的复杂性越高. 计算机中最重要的是:
- 时间资源 (时间复杂度)
- 空间资源 (空间复杂度)

1.5.1. 解决同一问题的不同算法¶

1.5.1.1. 将数字添加到一个列表中¶

让我们来做一个小实验, 简单地将一堆数字添加到一个最初为空的列表中, 然后反转该列表:

count = 10**5
nums = []
for i in range(count):
    nums.append(i)
nums.reverse()

当然我们有另一种思路: 与其到最后才将整个列表反转过来, 何不在数字出现的时候就将它插到列表头部?

count = 10**5
nums = []
for i in range(count):
    nums.insert(0,i)

看上去似乎第二种方法更好, 我们来验证下

#计算append、insert 操作的运行时间在规模从 10^3 到 10^5 的耗时
cost_time1 = []
for count in range(1, 101):
    start = time.time()
    nums = []
    for i in range(count*1000):
        nums.append(i)
    nums.reverse()
    cost_time1.append(time.time()-start)

cost_time2 = []
for count in range(1, 101):
    start = time.time()
    nums = []
    for i in range(count*1000):
        nums.insert(0,i)
    cost_time2.append(time.time()-start)


#加载 matplotlab 相关作图模块
%pylab inline

mpl.rcParams['font.sans-serif'] = ['FangSong'] # 指定默认字体
mpl.rcParams['axes.unicode_minus'] = False # 解决保存图像是负号'-'显示为方块的问题

plot(cost_time1, label = 'append')
plot(cost_time2, label = 'insert')
xlabel('$\\times 10^3$')
ylabel('Time costs (second)')
title(u'append、insert 操作的运行时间在规模从 $10^3$ 到 $10^5$ 的变化图')
legend()

1.5.1.2. 考虑斐波那契数列的第 $n$ 项:¶

$\begin{split}\begin{array}{l} F_0=F_1=1,\\ F_n=F_{n-1}+F_{n-2} \end{array}\end{split}$

求斐波那契数列的递归算法

将 $n$ 看做问题的规模, 不难得到计算 $F_n$ 的时间代价 (考虑求加法操作的次数) 大致等于

$\lim_{n\to\infty}F_n=(\frac{\sqrt5+1}2)^n$

因此计算 $F_n$ 的时间代价按 $n$ 的指数增长. 当 $n=100$ 时, 大约为 $8\times 10^{20}$ . 如果使用2014年全球运算速度最快计算机”天河二号”进行计算 (每秒运算 33.86千万亿次), 大约需要运算 6.5 小时.

求解斐波那契数列的递推算法

用这个算法计算 $F_n$ 的值, 循环前工作只要做一次, 循环需要做 $n-1$ 次. 因此总的工作量(基本操作执行次数)与 $n$ 呈线性关系.

1.5.2. 算法复杂度的渐近分析¶

需要注意的是, 算法设计首先要担心的并不是常数级别的性能差异. 即使相关程序完成任务所需要的时间是另一程序的两倍, 甚至十倍, 但这样的速度可能依然是够快的.

我们并不考虑常数单位上的差距, 这通常取决于编程语言的性能、硬件速度等
我们重点关注当问题规模扩大时运行时间的增长幅度
即将焦点集中在解决问题方法中那些独立于具体实现的属性

1.5.2.1. 渐近记号¶

$f(n)=n^2+100n+log_{10}n+1000$

当数据规模 $n$ 逐步增大时, $f(n)$ 的增长趋势当n增大到一定值以后, 计算公式中影响最大的就是n的幂次最高的项, 其他的常数项和低幂次项都可以忽略
大 $O$ 表示法 (上界)
- 如果存在正数 $c$ 和 $n_0$ , 使得对任意 $n>n_0$ , 都有 $f(n)\leq cg(n)$ , 则称
  
  $f(n)=O(g(n))$
- 表示函数增长的上界
- 注意: 一个函数增长的上界不唯一
大 $\Omega$ 表示法 (下界)
- 如果存在正数 $c$ 和 $n_0$ , 使得对任意 $n>n_0$ , 都有 $f(n)\geq cg(n)$ , 则称
  
  $f(n)=\Omega(g(n))$
- 表示函数增长的下界
- 注意: 一个函数增长的下界不唯一
大 $\Theta$ 表示法
- 如果存在正数 $c_1,c_2$ 和 $n_0$ , 使得对任意 $n>n_0$ , 都有 $c_1 g(n)\leq f(n)\geq c_2 g(n)$ , 则称
  
  $f(n)=\Theta(g(n))$
- 表示函数增长的上、下界相同
常用渐近复杂度

$O(1),O(\log n),O(n),O(n\log n),O(n^2),O(n^3),O(2^n),O(n!)$

思考:

对数通常有各自不同的底数, 但在算法分析中, 我们往往并不会在意它. 为了明白其中的原因, 考虑以下等式

$\log_b n =\frac{\log_a n}{\log_a b}.$

为什么它能告诉我们并不需要操心对数的底数问题?
证明任何指数级操作 ( $\Theta(k^n)$ , 其中 $k>1$ ) 的增长都要快于多项式级操作 ( $\Theta(n^j)$ , 其中 $j>0$ ).
证明任何多项式级操作的渐近增长都要快于对数级操作 ( $\Theta(\log n)$ ).

1.5.3. 算法分析¶

算法分析的目的是推导出算法的复杂度, 其中最主要技术是构造和求解递归方程.

基本循环程序的时间复杂度
1. 基本操作
  
  认为其时间复杂度为 $O(1)$ . 如果是函数调用, 应将其时间复杂度带入, 参与整体时间复杂度的计算.
2. 加法规则 (顺序结构)
  
  如果算法是两个部分的顺序复合, 其复杂性是这两部分的复杂性之和 $O(T_1(n)+T_2(n))=O(\max(T_1(n),T_2(n)))$
3. 乘法规则 (循环结构)
  
  如果算法是一个循环, 循环体将执行 $T_1(n)$ 次, 每次循环执行需要时间 $T_2(n)$ , 则总的时间为 $O(T_1(n)\times T_2(n))$
4. 取最大规则 (分支结构)
  
  如果算法是条件分支, 两个分支的时间复杂度分别是 $T_1(n)$ 和 $T_2(n)$ , 则有 $O(\max(T_1(n),T_2(n)))$

练习:

递归算法的时间复杂度递归算法通常具有如下的算法模式:
```
def fun(n):
if n == 0:
    return g(...)
somework
for i in range(a):
    x = fun(n/b)
    somework
somework
```
也就是说, $n=0$ 时直接得到结果, 否则将原问题归结为 $a$ 个规模为 $n/b$ 的子问题, 其中 $a,b$ 是由具体问题决定的两个常数. 另外, 在本层递归中还需要做一些工作, 即 somework, 其时间复杂度可能与 $n$ 有关, 设为 $O(n^k)$ . 这样就得到了递归方程:

$\begin{align}\begin{aligned}T(n)=O(n^k)+a\times T(n/b)\\有如下结论:\end{aligned}\end{align}$
- 如果 $a>b^k$ , 则 $T(n)=O(n^{\log_ba})$
- 如果 $a=b^k$ , 则 $T(n)=O(n^k\log n)$
- 如果 $a<b^k$ , 则 $T(n)=O(n^k)$

思考: 在上面的算法中, 元素是从序列每一半的尾端弹出 (pop()) 的. 或许选择从首端弹出 (pop(0))会更直观一点, 避免我们要对 res 进行反向处理 (res.reverse()). 但注意 pop(0) 和 insert(0) 一样, 是一个线性级操作, 而 pop() 是常数级的. 那么这种调整对会对整体运行时间产生什么影响呢?

三种重要情况

到目前为止, 我们所设想的运行时间都是完全确定的, 并且只取决于输入的规模, 而与输入的实际内容无关. 但这显然不是特别现实. 例如, 如果想要构造一个排序算法, 我们或许会这样开始:
```
def sort(seq):
n = len(seq)
for i in range(n-1) #如果for循环没有被break语句提前中止, 则执行 else 分支
    if seq[i] > seq[i+1]:
        break
else:
    return
...
...
```
这意味着无论我们的主排序算法效率有多低, 只要遇到一个已经排序的序列, 则其运行时间始终是线性级别的. 而在一般情况下是没有排序算法能达到线性级运行时间的.
- 最好情况: 当算法遇上最理想输入时的运行时间.
- 最坏情况: 可能会遇上的最糟糕的运行时间, 这通常也是最有用的情况.
- 平均情况: 最复杂的一种情况, 大部分时间里会回避对这种情况的讨论.

1.5.4. 时间、空间权衡¶

数据结构
- 一定的空间来存储它的每一个数据项
- 一定的时间来执行每一个操作
代价和效益
- 空间和时间的限制
- 增大空间开销可能改善算法的时间开销
- 想要节省空间, 往往需要增大运行时间

Next Section - 1.6. 作业