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()
../_images/output_25_1.png

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!)\]

思考:

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

    \[\log_b n =\frac{\log_a n}{\log_a b}.\]

    为什么它能告诉我们并不需要操心对数的底数问题?

  2. 证明任何指数级操作 (\(\Theta(k^n)\), 其中 \(k>1\)) 的增长都要快于多项式级操作 (\(\Theta(n^j)\), 其中 \(j>0\)).

  3. 证明任何多项式级操作的渐近增长都要快于对数级操作 (\(\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. 作业