跳至主要內容

《数据结构与算法分析》C语言描述

LincZero大约 11 分钟

《数据结构与算法分析》C语言描述

目录

算法分析

算法（algorithm），若某种算法正确可用，分析其需要多少诸如时间或空间等资源量很重要

本章内容

  • 如何估计一个程序所需要的时间
  • 如何将一个程序的运行时间从天或年降低到秒
  • 粗心地使用递归的后果
  • 将一个数自乘得到其幂以及计算两个数的最大公因数的非常有效的算法

数学基础

定义与概念

四个数学定义

  • 定义一：如果存在正常数cc和n0n_0使得当N≥n0N\geq n_0时T(N)≤cf(N)T(N)\leq cf(N)，则记为T(N)=O(f(N))T(N)=O(f(N))
  • 定义二：如果存在正常数cc和n0n_0使得当N≥n0N\geq n_0时T(N)≥cf(N)T(N)\geq cf(N)，则记为T(N)=Ω(f(N))T(N)=\Omega(f(N))
  • 定义三：当且仅当T(N)=O(h(N))T(N)=O(h(N))且T(N)=Ω(h(N))T(N)=\Omega(h(N))时， 则记为T(N)=Θ(h(N))T(N)=\Theta(h(N))
  • 定义四：如果T(N)=O(p(N))T(N)=O(p(N))且T(N)≠Θ(p(N))T(N)\neq\Theta(p(N))， 则记为T(N)=o(p(N))T(N)=o(p(N))

定义解释

  • 举例解释

    • 比较1000N1000N和N2N^2，虽然N较小时前者较大，但后者的增长速度更快，最终也会更大

    • 其中N=1000是转折点，即c=1，n0=1000c=1，n_0=1000，或者c=1000，n0=0c=1000，n_0=0（cc和n0n_0取其他情况也可）

    • 可以说1000N=O(N2)（N平方级）1000N=O(N^2)（N平方级），这种记法称为大O记法

  • 用不等式来解释

    • 定义一：T(N)T(N)的增长率小于等于f(N)f(N)，（念作大O......）
    • 定义二：T(N)T(N)的增长率大于等于f(N)f(N)，（念作omega）
    • 定义三：T(N)T(N)的增长率等于h(N)h(N)， （念作theta）
    • 定义四：T(N)T(N)的增长率小于p(N)p(N)， （念作小o......，这个和微积分的小o是相似的）

  • 用微积分解释（用我自己的话来解释）

    • 简单来讲就是比较N趋向于无穷时的增长率的无穷级数
    • 相对增长率的定义和比较法则其实也和解极限分式时所用到的 “比无穷小阶数法” 极度相似
    • 书里可能是为了兼顾没有学过微积分的人，并没有从微积分角度来讲。但实际上用微积分来看其实非常简明

  • 关于定义的吐槽

    • 居然有小o而没有小ω\omega，不太对称
    • 第三、四条定义你就不能完成定义嘛，非得依靠定义一、二、三来定义......本来简单的都被你弄复杂了

概念补充

  • 相对增长率：比较的都是相对增长率（relative rate of growth）。就像比较无穷小的阶数一样，这里没有绝对增长率和基准增长率，都是相对
  • 上界：若T(N)=O(f(N))T(N)=O(f(N))，则f(N)f(N)是T(N)T(N)的上界（upper bound）
  • 下界：若f(N)=Ω(g(N))f(N)=\Omega(g(N))， 则T(N)T(N)是$ f(N)$的下界（lower bound）

证明

  • 证明某个函数T(N)=O(f(N))T(N)=O(f(N))，一般不是使用定义，而是使用一些已知结果。即一般不需要复杂的计算

法则

三个法则

  • 法则一：如果T1(N)=O(f(N))且T2(N)=O(g(N))，那么(1)  T1(N)+T2(N)=max(O(f(N))，O(g(N))(2)  T1(N)∗T2(N)=O(f(N)∗g(N))如果T_1(N)=O(f(N))且T_2(N)=O(g(N))，那么\\ (1)~~T_1(N)+T_2(N)=max(O(f(N))，O(g(N))\\ (2)~~T_1(N)*T_2(N)=O(f(N)*g(N))
  • 法则二：如果T(N)T(N)是一个kk次多项式，则T(N)=Θ(Nk)T(N)=\Theta(N^k)
  • 法则三：对任意常数kk，log⁡kN=O(N)\log^kN=O(N)。它告诉我们对数增长得非常缓慢

注意项

  • 不要将常数或低阶项放入大O
    • 举例：不要写成T(N)=O(2N2)T(N)=O(2N^2)或T(N)=O(N2+N)T(N)=O(N^2+N)，而应写成T(N)=O(N2)T(N)=O(N^2)
  • 我们总能通过计算极限lim⁡n→∞f(N)/g(N)\lim_{n\rightarrow\infty}f(N)/g(N)来确定两个函数的相对增长率，必要时可以使用洛必达法则。该极限可能有四种可能的值
    • 极限是0：则f(N)=o(g(N))f(N)=o(g(N))
    • 极限是c≠0c\neq0，则f(N)=Θ(g(N))f(N)=\Theta(g(N))
    • 极限是∞\infty，则g(N)=o(f(N))g(N)=o(f(N))
    • 极限摆动：二者无关

典型增长率

函数名称
cc常数
log⁡N\log N对数级
log⁡2N\log^2N对数平方根（若对数指数能抵消，增长率变回O(N)O(N)）
NN线性级
Nlog⁡NN\log N
N2N^2平方级
N3N^3立方级
2N2^N指数级

模型

为分析算法需要一个计算模型：模型机（不同于实际计算机）

  • 做任意一件D简单的工作都恰好花费一个时间单元（实际计算机不是）
  • 有无限的内存（实际计算机不是）
  • 有固定范围的整数
  • 不存在诸如矩阵求逆或排序等运算，它们显然不能再一个时间单元内完成

要分析的问题

定义两个函数

  • Tavg(N)T_{avg}(N)：输入为N时，算法花费的平均运行时间
  • Tworst(N)T_{worst}(N)：输入为N时，算法最坏情况下的运行时间

运行时间计算

一个简单的例子

程序目的：计算∑i=1Ni3\sum_{i=1}^Ni^3

int Sum(int N)
{
    int i, PartialSum;
    PartialSum = 0;				// 1
    for(i=1; i<=N; i++)			// 2
        PartialSum += i*i*i;	// 3
    return PartialSum;			// 4
}

详尽分析

  • 声明不计入时间
  • 注1和注4各占一个时间单元，共2
  • 注3每执行一次占用4个时间单元（两次乘法、一次加法、一次赋值），共4N
  • 注2隐含开销，初始化1、循环测试N+1、自增N，共2N+2
  • 总占用时间：6N+4，即函数是O(N)O(N)的

简化分析

  • 不可能分析得这么细，只要求大O的结果，可以简化一些末节。如这里可以简化掉O(c)O(c)的语句

一般法则

  • 法则一：for循环
    • 一次for循环的运行时间至多是该for循环内语句（包括测试）的运行时间乘以迭代次数
  • 法则二：嵌套的for循环
    • 从里向外分析这些循环
  • 法则三：顺序语句
    • 将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）
  • 法则四：if/else语句
    • 运行时间不超过判断的时间加上可能运行的代码中运行时间较长者的总的运行时间（进行高估）
  • 补充：递归语句
    • 有的可以直接转换成for语句，而有的不易转换。后者可以通过求运行时间的递推公式和类比原式来求解（如求Fib数列和）

最大子序列和

四种算法

  • 问题描述

    • 给定整数A1，A2，⋯，ANA_1，A_2，\cdots，A_N（可能有负数），求∑k=ijAk\sum_{k=i}^jA_k的最大值 （为方便起见：如果所有整数均为负数则最大子序列和为0）

  • 举例

    • 输入（-2，11，-4，13，-5，-2）时，答案为20（从第二项到第四项）

  • 四种算法

    • 算法时间N=10N=100N=1000N=10000N=100000
      1O(N3)O(N^3)0.001030.47015448.77NANA
      2O(N2)O(N^2)0.000450.011121.1233111.13NA
      3O(Nlog⁡N)O(N\log N)0.000660.004860.058430.686318.01130
      4O(N)O(N)0.000340.000630.003330.030420.29832

    • 显然算法4最佳

  • 补充说明

    • 算法给出的时间不包括读入数据所需要的时间
    • 对于算法4，仅仅从磁盘读入数据所用的时间可能在数量级上比求解上述问题所需要的时间还要多
    • 这是许多有效算法中的典型特点，数据的读入一般是个瓶颈
    • 但对于低效率的算法情况不同，它必然要耗费大量的计算机资源

算法一：三重嵌套for循环

程序

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for(i=0; i<N; i++)
        for(j=i; j<n; j++)
        {
            ThisSum = 0;
            for(k=i; k<=j; k++)
                ThisSum += A[k];
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    return MaxSum;
}

增长率：

∑i=0N−1∑j=iN−1∑k=ij1=N3+3N2+2N6=O(N3) \sum_{i=0}^{N-1} \sum_{j=i}^{N-1} \sum_{k=i}^{j} 1=\frac{N^3+3N^2+2N}{6}=O(N^3)

算法二：减少一次for

程序

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for(i=0; i<N; i++)
        ThisSum = 0;
        for(j=i; j<n; j++)
        {
            ThisSum += A[j];
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    return MaxSum;
}

增长率

  • 基本同算法一，为O(N2)O(N^2)

算法三：分治策略 + 递归

思想

  • 采用 “分治”（divide-and-conquer）策略：把问题分成两个大致相等的子问题，然后递归丢他们求解。然后合并
  • 不断取中值插值进行细分，把序列从中间切分成左右两部分，结果有三种可能：最大子序列和仅出现在左边、仅出现在右边、同时出现在左右
  • 前两种情况可以递归求解，第三种情况的最大和为前半部分最大和（包含最后一个元素）加后半部分最大和（包含第一个元素）

程序

static int MaxSubSum(const int A[], int Left, int Right)
{
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    int LeftBorderSum, RightBorderSum;
    int Center, i;
    
    if(Left==Right)		// 基准情形
        if(A[Left]>0)
            return A[Left];
    	else
            return 0;
    
    /*(1) 最大子序列在左边或右边的情况，递归调用*/
    Center = (Left+Right)/2;
    MaxLeftSum = MaxSubSum(A, Left, Center);		// 递归调用
    MaxRightSum = MaxSubSum(A, Center+1, Right);	// 递归调用
    
    /*(2) 最大子序列在两边的情况，求边界最值*/
    MaxLeftBorderSum=0; LeftBorderSum =0;
    for(i=Center; i>=Left; i--)
    {
        LeftBorderSum += A[i]
        if(LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    MaxRightBorderSum=0; RightBorderSum =0;
    for(i=Center; i<=Right; i++)
    {
        RightBorderSum += A[i]
        if(RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    
    /*返回最大的情况*/
    return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum+MaxRightBorderSum)
    
}

int MaxSubsequenceSum(const int A[], int N)
    return MaxSubSum(A, 0, N-1);

增长率

  • 使用了递归会比较难分析，需要看时间的递归
  • T(1)=1，T(N)=2T(N/2)+O(N)T(1)=1，T(N)=2T(N/2)+O(N)
  • 通过找规律：T(1)=1，T(2)=4=2∗2，T(8)=32=8∗4，T(16)=80=16∗5T(1)=1，T(2)=4=2*2，T(8)=32=8*4，T(16)=80=16*5
  • 设N=2kN=2^k，可推得：T(N)=N∗(k+1)=Nlog⁡2N+N=O(Nlog⁡N)T(N)=N*(k+1)=N\log_2 N+N=O(N\log N)
  • 当N是奇数时，不能这样推，但大O的结果是一样的

算法四：联机算法

思想

  • 简单来讲就是若左侧和<0时则舍弃左侧并重新累加，若左侧和>0时则应在左侧的基础上继续累加

程序

int MaxSubsequenceSum(const intA[], int N)
{
    int ThisSum, MaxSum, j;
    ThisSum = MaxSum = 0;
    for(j=0; j<N; j++)
    {
        ThisSum += A[j];
        if(ThisSum>MaxSum)
            MaxSum = ThisSum;
        else if(ThisSum < 0)
            ThisSum = 0;
    }
    return MaxSum;
}

增长率

  • 易知为O(N)O(N)

联机算法补充

  • 该算法还是一个联机算法（on-line algorithm），特点：只对数据进行一次扫描

  • 即在任意时间，算法都能对它已经读入的数据给出子序列问题的正确答案

  • 仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法

  • 一个我曾经混淆的点：联机算法和”联机“的关系

    • 联机算法（on-line algorithm），起名的本意是在一条线上的。而online的翻译是“联机”或“在线” 和联机渲染（Online rendering）的online不是同一个意思 离线同理 离线算法/脱机算法（off-line algorithms）本意非线性的，和离线渲染（offline rendering）的offline不是同一个意思
    • 启示：看来专业名词得看英文

运行时间中的对数

分析算法中对数可能会比较混乱，这章深入剖析一下运行时间中的对数

  • 可能会出现对数的情况
    • 一个算法用常数时间（O(1)O(1)）将问题的大小进行分割
    • 如果削减为其一部分（通常是1/2），那么该算法就是O(log⁡N)O(\log N)的
    • 如果仅减少一个常数（如将问题减少1），那么这种算法就是O(N)O(N)的
  • 具有对数特点的三个例子
    • 对分查找（binary search，也叫二分查找、折半查找）
      • 举例：在一个排序过的列表里找一个项的下标，若不在则返回-1
      • 思路：一直中间插入就行
      • 程序：略
    • 欧几里得算法
      • 举例：计算最大公因数（Gcd）（经典老题型了）
      • 思路：相除、除数变被除数、余数变除数（比不比大小都行）
      • 程序：略
    • 幂运算
      • 举例：就是幂运算
      • 思路：偶数则XN=XN/2⋅XN/2X^N=X^{N/2}\cdot X^{N/2}，奇数则XN=X(N−1)/2⋅X(N−1)/2⋅XX^N=X^{(N-1)/2}\cdot X^{(N-1)/2}\cdot X。乘法次数最多是2log⁡N2\log N
      • 程序：略

检验你的分析

完成分析后，一是看答案是否正确，是否最优。

  • 验证方法一：可以编程并比较实际运行时间和分析的运行时间是否相匹配（如N*2，N*4、仅比较增长率）

    但有时候很难区分线性程序和O(Nlog⁡N)O(N\log N)程序，后者的曲线几乎也是线性的

  • 验证方法二：可以比较T(N)/f(N)T(N)/f(N)，前者是实际运行时间，后者是理想近似，若收敛与一个正常数则吻合

分析结构的准确性

有时候分析会估计过大，可以分析得更细，又或者是平均运行时间显著小于最坏情形的情况

但对于大多数情况，平均情形的分析极其复杂（在许多情形下还是未解决的），而最坏情形的界尽管有时过分悲观但却是最好的已知解析结果

杂记

选择问题（selection problem），如选择最大值

排序问题，方法：冒泡排序等