我的博客 第一课 算法设计

作者：SUN 更新于： 围观群众： 点赞人数： 评论人数：

这里是文章的简介部分

第一课 算法设计

Created At： Updated At：

算法

什么是算法

算法是求解问题的一系列计算步骤，用来将输入数据转换成输出结果 ：

graph LR
A[输入]
B[算法]
C[输出]
A-->B
B-->C

如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的。

算法，满足的目标

  • 正确性
  • 可使用性
  • 可读性
  • 健壮性
  • 高效率与低存储量需求

例子

  • 【例1.1】以下算法用于在带头结点的单链表h中查找第一个值为x的结点，找到后返回其逻辑序号（从1计起），否则返回0。分析该算法存在的问题。

    int findx(LNode *h;int x)
{   LNode *p=h->next;
　　int i=0;
　　while (p->data!=x)
　　{	i++;
    p=p->next;
　　}
　　return i;
}

    单链表示意图

    • 解：问题

      • 当单链表中首结点值为x时，该算法返回0，此时应该返回逻辑序号1。

      • 当单链表中不存在值为x的结点时，该算法执行出错，因为p为NULL时仍执行p=p->next。

      • 所以该算法不满足正确性和健壮性。应改为：

        int findx(LNode *h;int x)
{   LNode *p=h->next;	
　　int i=1;
　　while (p!=NULL && p->data!=x)
　　{	i++;
    p=p->next;
　　}
　　if (p==NULL)
    return 0;
　　else
    return i;
}

算法具有以下五个重要特征

  • 有限性
  • 确定性
  • 可行性
  • 输入性
  • 输出性

例1.2

//描述1
void exam1() 
{  int n; 
　 n=2; 
　 while (n%2==0) 
　　　n=n+2;	 
　 printf("%d\n",n); 
}

//描述2
void exam2() 
{  int x,y; 
　 y=0; 
　 x=5/y; 
　 printf("%d,%d\n",x,y); 
}
  • 这两段描述均不能满足算法的特征，试问它们违反了算法的哪些特征？
    • 解：（1）是一个死循环，违反了算法的有限性特征。（2）出现除零错误，违反了算法的可行性特征。

算法的描述

以设计求1+2+…+n值的算法为例说明C/C++语言描述算法的一般形式，该算法如下：

返回值		形参列表
bool fun(int n,int s)
{
   if (n<0) return false;
   s=0;
   for (int i=1;i<=n;i++)
      s+=i;
   return true;
}

  • 用函数的返回值表示算法能否正确执行。

  • 用形参表示算法的输入输出。

  • C语言中只有从实参到形参的单向值传递，若改变形参而对应的实参不会同步改变。

  • 例如，设计以下主函数调用上面的fun函数：

    void main()
{   int a=10,b=0;
　　if (fun(a,b)) printf("%d\n",b);
　　else printf("参数错误\n");
}

    执行时发现输出结果为0，因为b对应的形参为s，fun执行后s=55，但s并没有回传给b。

    可以用传指针方式实现形参的回传，但增加了函数的复杂性。

    C语言中增加了引用型参数，参数名前需加上&，形参在执行后会将结果回传给对应的实参。上例采用C语言描述算法如下所示。

    bool fun(int n,int &s)
{
   if (n<0) return false;
   s=0;
   for (int i=1;i<=n;i++)
      s+=i;
   return true;
}

    当形参s改为引用类型的参数后，执行main函数的输出结果就输出55。

  • 结论：在设计算法时，如果某个形参需要将执行结果回传给实参，需要将该形参设计为引用型参数。

算法和数据结构

既有联系又有区别

  • 联系

    数据结构是算法设计的基础。算法的操作对象是数据结构，在设计算法时，要构建适合这种算法的数据结构。数据结构设计主要是选择数据的存储方式，如确定求解问题中的数据采用数组存储还是采用链表存储等。算法设计就是在选定的存储结构上设计一个满足要求的好算法。

  • 区别

    数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。

算法设计的基本步骤

graph TD
a[分析求解问题]-->b[选择数据结构和算法设计策略]-->c[描述算法]-->d[证明算法正确性]-->e[算法分析]

设计步骤

算法分析

算法分析是分析算法占用计算机资源的情况。主要是分析算法的时间复杂度和空间复杂度。

算法时间复杂度分析

时间复杂度分析概述

算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，运行时间取决于两者的综合效果。

bool Solve(double a[][MAX],int m,int n,double &s)
{
   int i; s=0;					//顺序结构
   if (m!=n) return false;		//分支结构
   for (i=0;i<m;i++)			//循环结构
     s+=a[i][i];
   return true;					//顺序结构
}

  • 设n为算法中的问题规模，通常用大O、大和Θ等三种渐进符号表示算法的执行时间与n之间的一种增长关系。

    • 分析算法时间复杂度的一般步骤：

      graph TD
算法-->d["分析问题规模n，找出基本语句，求出其运行次数f(n)"]-->p["用o、Ω或Θ表示其阶"]

    渐进符号（O、Ω和ΘO、Ω和Θ）

    • 定义1（大O符号大O符号），f(n)=O(g(n))（读作“f(n)是g(n)的大O”）f(n)=O(g(n))（读作“f(n)是g(n)的大O”）当且仅当存在正常量c和n0，使当n≥n0时，f(n)≤cg(n)，即g(n)为f(n)c和n_0，使当n≥n_0时，f(n)≤cg(n)，即g(n)为f(n)的上界。

      如3n+2=O(n)3n+2=O(n)，因为当n≥2时，3n+2≤4n3n+2≤4n。

      10n2+4n+2=O(n4)10n^2+4n+2=O(n^4)，因为当n≥2时，10n2+4n+2≤10n410n^2+4n+2≤10n^4。

      大O符号大O符号用来描述增长率的上界，表示$f(n)的增长最多像g(n) $增长的那样快，即当输入规模为n时，算法消耗时间的最大值。这个上界的阶越低，结果就越有价值，所以，对于$10n2+4n+2，O(n2)比O(n^4) $有价值。

      一个算法的时间用大O符号表示时，总是采用最有价值的g(n)g(n)表示，称之为“紧凑上界”或“紧确上界”。

      一般地，如果f(n)=amnm+am−1nm−1+…+a1n+a0，有f(n)=O(nm)f(n)=a_mn^m+a_{m-1}n^{m-1}+…+a_1n+a_0，有f(n)=O(n^m)。

    • 定义2（大Ω符号），f(n)=Ω(g(n))（大Ω符号），f(n)= Ω (g(n))（读作“f(n)是g(n)的大Ω”）当且仅当存在正常量c和n0f(n)是g(n)的大Ω”）当且仅当存在正常量c和n_0，使当n≥n0时，f(n)≥cg(n)，即g(n)为f(n)的n≥n_0时，f(n)≥cg(n)，即g(n)为f(n)的下界。

      如3n+2=Ω(n)，因为当n≥1时，3n+2≥3n。3n+2=Ω(n)，因为当n≥1时，3n+2≥3n。 　　10n2+4n+2=Ω(n2)，因为当n≥1时，10n2+4n+2≥n2。10n^2+4n+2=\Omega (n2)，因为当n≥1时，10n^2+4n+2≥n^2。

      大Ω符号用来描述增长率的下界，表示f(n)的增长最少像g(n) 增长的那样快，也就是说，当输入规模为n时，算法消耗时间的最小值。 与大O符号对称，这个下界的阶越高，结果就越有价值，所以，对于$10n2+4n+2，Ω(n2)比Ω(n) 有价值。一个算法的时间用大有价值。一个算法的时间用大Ω符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。一般地，如果符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。 一般地，如果f(n)=a_mnm+a_{m-1}n{m-1}+…+a_1n+a_0，有f(n)=Ω(n^m)$。

    • 定义3（大Θ符号），f(n)=Θ(g(n))（读作“f(n)是g(n)的大Θ”）当且仅当存在正常量c1、c2和n0，f(n)= Θ(g(n))（读作“f(n)是g(n)的大Θ”）当且仅当存在正常量c_1、c_2和n_0， 使当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，即g(n)与f(n)的同阶使当n≥n_0时，有c_1g(n)≤f(n)≤c_2g(n)，即g(n)与f(n)的同阶。

      如3n+2=Θ(n)，10n2+4n+2=Θ(n2)如3n+2=Θ (n)，10n^2+4n+2=Θ(n^2)。 　　一般地，如果f(n)=amnm+am−1nm−1+…+a1n+a0，有f(n)=Θ(nm)一般地，如果f(n)=a_mn^m+a_{m-1}n^{m-1}+…+a_1n+a_0，有f(n)=Θ(n^m)。 　　大Θ符号比大O符号和大符号Θ都精确，f(n)=Θ(g(n)Θ符号比大O符号和大符号Θ都精确，f(n)=Θ(g(n)，当且仅当g(n)既是f(n)的上界又是f(n)当且仅当g(n)既是f(n)的上界又是f(n)的下界。函数图像

      • 【例1.3】分析以下算法的时间复杂度：

        void fun(int n)
{  int s=0,i,j,k;
   for (i=0;i<=n;i++)
    for (j=0;j<=i;j++)
         for (k=0;k<j;k++)
          s++;
}
        解：该算法的基本语句是s++，所以有：f(n)=∑i=0n∑j=0i∑k=0j−1=∑i=0n∑j=0j(j−1−0+1)=∑i=0n∑j=0ij=∑i=0ni(i+1)2=12(∑i=0ni2+∑i=0ni)=2n3+6n2+4n2=O(n3)则该算法的时间复杂度为O(n3)。\begin{aligned} 解：该算法&的基本语句是s++，所以有：\\ f(n)&=\sum^n_{i=0}\sum^i_{j=0}\sum^{j-1}_{k=0}=\sum^n_{i=0}\sum^j_{j=0}(j-1-0+1)\\ &=\sum^n_{i=0}\sum^i_{j=0}j=\sum^n_{i=0}\frac{i(i+1)}{2}=\frac{1}{2}(\sum^n_{i=0}i^2+\sum^n_{i=0}i)\\ &=\frac{2n^3+6n^2+4n}{2}\\ &=O(n^3)\\ 则该算法&的时间复杂度为O(n^3)。 \end{aligned}

  • 算法的最好、最坏和平均情况

    • 定义4 设一个算法的输入规模为n，Dnn，D_n是所有输入的集合，任一输入I∈Dn，P(I)是II∈D_n，P(I)是I出现的概率，有∑P(I)=1，T(I)\sum P(I)=1，T(I)是算法在输入II下所执行的基本语句次数，则该算法的平均执行时间为：A(n)=∑I∈DnP(I)∗T(I)A(n)=\sum_{I∈D_n}P(I)*T(I)。

    • 算法的平均情况指各种特定输入下的基本语句执行次数的带权平均值。

    • 算法的最好情况为：G(n)=MINIeDn{T(I)}G(n)=\underset{IeD_n}{MIN}\{T(I)\}，是指算法在所有输入II下所执行基本语句的最少次数。 算法的最坏情况为：W(n)=MINIeDn{T(I)}W(n)=\underset{IeD_n}{MIN}\{T(I)\}，是指算法在所有输入II下所执行基本语句的最大次数。

  • 【例1.4】采用顺序查找方法，在长度为n的一维实型数组a[0…n-1]中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。找到后返回1，否则返回0，对应的算法如下：

    int Find(double a[],int n,double x)
{  int i=0;
   while (i<n)
   {  if (a[i]==x) break;
      i++;
   }
   if (i<n) return 1;
   else return 0;
}

    • 回答以下问题： 　（1）分析该算法在等概率情况下成功查找到值为x的元素的最好、最坏和平均时间复杂度。 　（2）假设被查值x在数组a中的概率是q，求算法的时间复杂度。

    • 解：（1）算法的while循环中的if语句是基本语句。a数组中有n个元素，当第一个元素a[0]等于x，此时基本语句仅执行一次，此时呈现最好的情况，即G(n)=O(1)。

      ​ 当a中最后一个元素a[n-1]等于x，此时基本语句执行n次，此时呈现最坏的情况，即W(n)=O(n)。

      ​ 对于其他情况，假设查找每个元素的概率相同，则P(a[i])=1/n（0≤i≤n-1），而成功找到a[i]元素时基本语句正好执行i+1次，所以：

      A(n)=∑i=0n−11n(i+1)=1n∑i=0n−1(i+1)=n+12=O(n)A(n)=\sum_{i=0}^{n-1}\frac{1}{n}(i+1)=\frac{1}{n}\sum_{i=0}^{n-1}(i+1)=\frac{n+1}{2}=O(n)

      （2）当被查值x在数组a中的概率为q时，算法执行有n+1种情况，即n种成功查找和一种不成功查找。 　　对于成功查找，假设是等概率情况，则元素a[i]被查找到的概率P(a[i])=qnP(a[i])=\frac{q}{n}​，成功找到a[i]元素时基本语句正好执行i+1次。 　　对于不成功查找，其概率为1-q，不成功查找时基本语句正好执行n次。 　　所以：

      A(n)=∑I∈DnP(I)∗T(I)=∑i=0nP(I)∗T(I)=∑i=0n−1qn(i+1)+(1−q)n=(n+1)q2+(1−q)n如果已知需要查找的x有一半的机会在数组中，此时q=12，则A(n)=[(n+1)4]+n2=3n4。\begin{aligned} A(n)&=\sum_{I∈D_n}P(I)*T(I)\\ &=\sum^n_{i=0}P(I)*T(I)\\ &=\sum_{i=0}^{n-1}\frac{q}{n}(i+1)+(1-q)n\\ &=\frac{(n+1)q}{2}+(1-q)n\\ 如果已知需要查找&的x有一半的机会在数组中，此时q=\frac{1}{2}，则A(n)=[\frac{(n+1)}{4}]+\frac{n}{2}=\frac{3n}{4}。 \end{aligned}

    非递归算法的时间复杂度分析

非递归算法，关键是求出代表算法执行时间的表达式。 　　基本语句的执行次数是一个关于问题规模n的表达式，用渐进符号来表示这个表达式即得到算法的时间复杂度。

  • 【例1.6】给出以下算法的时间复杂度。

    void func(int n)
{   int i=1,k=100;
    while (i<=n)
    {  k++;
       i+=2;
    }
}

    - 解：基本语句是whilewhile循环内的语句，设执行的次数为m，i从1开始递增m，i从1开始递增，最后取值为1+2m1+2m，有： i=1+2m≤ni=1+2m≤n

     $f(n)=m≤\frac{(n-1)}{2}=O(n)$。
该算法的时间复杂度为$O(n)$。

递归算法的时间复杂度分析

递归算法是采用一种分而治之的方法，把一个“大问题”分解为若干个相似的“小问题”来求解。 　　关键是根据递归过程建立递推关系式，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式即得到算法的时间复杂度。

  • 【例1.7】有以下递归算法：

    void mergesort(int a[],int i,int j)
{   int m;
    if (i!=j)
    {	 m=(i+j)/2;
        mergesort(a,i,m);
        mergesort(a,m+1,j);
        merge(a,i,j,m);
    }
}

    ​ mergesort()用于数组a[0…n-1]（设n=2kn=2^k，这里的k为正整数）的归并排序，调用该算法的方式为： ​ mergesort(a，0，n-1)； ​ 另外merge(a，i，j，m)用于两个有序子序列a[i…j]和a[j+1…m]的有序合并，是非递归函数，它的时间复杂度为O(n)（这里n=j-i+1）。分析上述调用的时间复杂度。

    解：设调用mergesort(a，0，n-1)的执行时间为T(n)，由其执行过程得到以下求执行时间的递归关系（递推关系式）：

    T(n)=O(1)当n=1T(n)=2T(n/2)+O(n)当n>1\begin{aligned} &T(n)=O(1) 当n=1\\ &T(n)=2T(n/2)+O(n) 当n>1 \end{aligned}

    其中，O(n)为merge()所需的时间，设为cn（c为正常量）。因此：

    T(n)=2T(n2)+cn=2[2T(n22)+cn2]+cn=22T(n22)+2cn=23T(n23)+3cn=…=2kT(n2k)+kcn=nO(1)+cnlog2n=n+cnlog2n//这里假设n=2k，则k=log⁡2n=O(nlog⁡2n)\begin{aligned} T(n) &= 2T(\frac{n}{2})+cn=2[2T(\frac{n}{2^2})+\frac{cn}{2}]+cn=2^2T(\frac{n}{2^2})+2cn\\ &= 2^3T(\frac{n}{2^3})+3cn\\ &= …\\ &= 2^kT(\frac{n}{2^k})+kcn\\ &= nO(1)+cnlog_2n=n+cnlog_2n //这里假设n=2^k，则k=\log_2n\\ &= \textcolor{red}{O(n\log_2n)} \\ \end{aligned}

  • 【例1.8】求解梵塔问题的递归算法如下，分析其时间复杂度。

    void Hanoi(int n,char x,char y,char z)
{  if (n==1)
      printf("将盘片%d从%c搬到%c\n",n,x,z);
   else
   {   Hanoi(n-1,x,z,y);
       printf("将盘片%d从%c搬到%c\n",n,x,z);
    Hanoi(n-1,y,x,z);
   }
}

    解：设调用Hanoi(n，x，y，z)的执行时间为T(n)，由其执行过程得到以下求执行时间的递归关系（递推关系式）：

    T(n)=O(1)当n=1T(n)=2T(n−1)+1当n>1\begin{aligned} &T(n)=O(1) 当n=1\\ &T(n)=2T(n-1)+1 当n>1 \end{aligned}
    T(n)=2[2T(n−2)+1]+1=22T(n−2)+1+21=23T(n−3)+1+21+22=…=2n−1T(1)+1+21+22+…+2n−2=2n−1=O(2n)\begin{aligned} T(n) &= 2[2T(n-2)+1]+1=2^2T(n-2)+1+2^1\\ &= 2^3T(n-3)+1+2^1+2^2\\ &= …\\ &= 2^{n-1}T(1)+1+2^1+2^2+…+2^{n-2}\\ &= 2^n-1 = O(2^n)\\ \end{aligned}

算法空间复杂度分析

一个算法的存储量包括形参所占空间和临时变量所占空间。在进行存储空间分析时，只考察临时变量所占空间。

  • 例如，以下算法中临时空间为变量i、maxi占用的空间。所以，空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作： S(n)=O(g(n))、Ω(g(n))或Θ(g(n)) 其中渐进符号的含义与时间复杂度中的含义相同。

    int max(int a[]，int n)
{   int i，maxi=0;
    for (i=1;i<n;i++)
    if (a[i]>a[maxi])
         maxi=i;
    return a[maxi];
}

    函数体内分配的变量空间为临时空间，不计形参占用的空间，这里的仅计i、maxi变量的空间，其空间复杂度为O(1)。

为什么算法占用的空间只考虑临时空间，而不必考虑形参的空间呢？这是因为形参的空间会在调用该算法的算法中考虑，例如，以下maxfun算法调用max算法：

void maxfun()
{   int b[]={1,2,3,4,5},n=5;
　　printf("Max=%d\n",max(b,n));
}

maxfun算法中为b数组分配了相应的内存空间，其空间复杂度为O(n)，如果在max算法中再考虑形参a的空间，这样重复计算了占用的空间。

int max(int a[]，int n)
{   int i，maxi=0;
    for (i=1;i<n;i++)
    if (a[i]>a[maxi])
         maxi=i;
    return a[maxi];
}

算法空间复杂度的分析方法与前面介绍的时间复杂度分析方法相似。

【例1.9】分析例1.6算法的空间复杂度。

void func(int n)
{   int i=1,k=100;
    while (i<=n)
    {	  k++;
      i+=2;
    }
}

解：该算法是一个非递归算法，其中只临时分配了i、k两个变量的空间，它与问题规模n无关，所以其空间复杂度均为O(1)，即该算法为原地工作算法。

【例1.10】有如下递归算法，分析调用maxelem(a，0，n-1)的空间复杂度。

int maxelem(int a[],int i,int j)
{   int mid=(i+j)/2,max1,max2;
    if (i<j)
    {	max1=maxelem(a,i,mid);
    max2=maxelem(a,mid+1,j);
    return (max1>max2)?max1:max2;
    }
    else return a[i];
}

解：执行该递归算法需要多次调用自身，每次调用只临时分配3个整型变量的空间（O(1)）。设调用maxelem(a,0,n-1)的空间为S(n)，有：

S(n)=O(1)当n=1S(n)=2S(n/2)+O(1)当n>1\begin{aligned} &S(n)=O(1) 当n=1\\ &S(n)=2S(n/2)+O(1) 当n>1\\ \end{aligned}
则：S(n)=2S(n2)+1=2[2S(n22)+1]+1=22S(n22)+1+21=23(n23)+1+21+22=...=2kS(n2k)+1+21+22+....+2k−1(设n=2k,即k=log⁡2n)=n∗1+2k−1=2n−1=O(n)\begin{aligned} 则：S(n)&= 2S(\frac{n}{2})+1=2[2S(\frac{n}{2^2})+1]+1=2^2S(\frac{n}{2^2})+1+2^1\\ &=2^3(\frac{n}{2^3})+1+2^1+2^2\\ &=...\\ &=2^kS(\frac{n}{2^k})+1+2^1+2^2+....+2^{k-1}(设n=2^k,即k=\log_2n)\\ &=n*1+2^k-1=2n-1=\textcolor{red}{O(n)} \end{aligned}

文章声明： 非特殊说明，本文版权归 SUN个人博客 所有，转载请注明出处

本文标题： 第一课 算法设计

本文地址：

点此返回目录： 回到顶端

全部评论

点击排行

最新文章

  1. 第三课 递归算法设计技术
  2. 第二课 STL
  3. 第一课 算法设计
Copyright © 2022-2099 Power by SUN的博客 ICP备案号：XXXXXXXXXX