算法和算法分析 时间复杂度和空间复杂度的分析

Myth丶恋晨 2023-10-14 18:00 180阅读 0赞

文章目录

  • 算法与程序
    • **程序=数据结构+算法**
    • 算法和算法分析
      • 算法特性
        • 有穷性
        • 确定性
        • 可行性
        • 输入
        • 输出
      • 算法设计的要求
      • 算法时间效率的度量
    • 时间复杂度
      • 定理1.1
      • 分析算法时间复杂度的基本方法
      • 复杂算法的处理
    • 空间复杂度

算法与程序

  • 算法是解决问题的一种方法或一个过程,考虑如何将输入转化成输出,一个问题可以有多个算法
  • 程序是用某种程序设计语言对算法的具体实现

程序=数据结构+算法

  • 数据结构通过算法实现操作
  • 算法根据数据结构设计程序

算法和算法分析

算法特性

一个算法必须具备以下五个重要特征

有穷性

一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成

确定性

算法的每一条指令必须有确切的含义,没有二义性,在任何条件下,只有唯一的一条执行路径,即对于相同的输入只能得到相同的输出

可行性

算法是可执行的,算法描述的操作可以通过已经实现的基本操作执行有限次来实现

输入

一个算法有零个或多个输入

输出

一个算法有一个或多个输出

算法设计的要求

  • 正确性(Correctness)

    • 不含语法错误
    • 能得到满足要求的结果
    • 对于精心选择的,典型,苛刻且带有刁难性的输入能得到满足要求的结果
    • 一切合法的输入数据都能得出满足要求的结果

  • 可读性(Readability)

    • 首先为了人的阅读和交流,其次才是计算机执行
    • 晦涩难读的算法容易调试

  • 健壮性(Robustness)

    • 输入非法数据时算法做出相应的处理,而不是出错
    • 处理错误方法,不应该中断程序执行,而是返回一个表示错误或错误性质的值,以便在更高的抽象层次上处理

  • 高效性(Efficiency)

    • 要求花费尽量少的时间和尽量低的存储要求

当算法满足前三的要求时,主要考虑算法的效率,通过算法的效率高低来评判不同算法的优劣程度

算法效率以以下两个方面来考虑

  1. 时间效率:指的是算法所耗费的时间

  2. 空间效率:指的是算法执行过程中耗费的存储空间

    • 时间效率和空间效率有时候是矛盾的

算法时间效率的度量

  • 使用在计算机上执行所消耗的时间来度量

  • 两种度量方法

    • 事后统计

      • 将算法实现,测算其时间和空间开销
      • 缺点:花费时间和精力,结果依赖于计算机的软硬件等环境因素

    • 事前分析(推荐使用这个)

      • 对算法所消耗资源的一种估算方法

      (事前分析)算法运行时间=一个简单操作所需要的时间*简单操作次数

      *(事前分析)算法运行时间=∑每条语句的执行次数(又称语句频度)该语句执行一次所需要的时间

      注意:每条语句执行所需时间由计算机软硬件条件影响的,与算法无关

      所以,我们可以假设执行每条语句所需的时间均为单位时间

例如

  1. for(i=1;i<=n;i++){
  2.                                     //n+1次
  3.     for(j=1;j<=n;j++){
  4.                                 //n*(n+1)次
  5.         c[i][j]=0;                                //n*n次
  6.         for(k=0;k<n;k++){
  7.                             //n*n*(n+1)次
  8.             c[i][j]=c[i][j]+a[i][k]*b[k][j];    //n*n*n次
  9.         }
  10.     }
  11. }

我们把算法所消耗的时间定义为该算法中每条语句的频度之和则上述算法的时间消耗T(n)为

T(n)=2n^3 + 3n^2 + 2n+1一个关于n的函数

  • 为了方便比较不同算法时间效率,我们仅比较它们的数量级

例如:两个不同的算法,时间消耗分别是

T(n)=10n^2 与 T(n)=5n^3;

时间复杂度

  • 若有某个辅助函数f(n),使得当n趋近于无穷大是,T(n)/f(n)的极限值为不等于零的常数,则称为f(n)是T(n)的同数量级函数,记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号),简称时间复杂度

T(n)=2n^3 + 3n^2+2n+1

其中当n->∞时,T(n)/n3->2,这表示n充分大时,T(n)与n3是同阶或同数量级,引入”O”记号,则T(n)可以记作

T(n)=O(n^3)

这就是求矩阵相城问题的算法的渐进时间复杂度

一般情况下,不必计算所有操作的执行次数,而只考虑算法中基本操作执行的次 数, 它是问题规模n的某个函数,用T(n)表示

算法中基本语句重复执行次数是问题规模n的某个函数f(n),算法的时间量度记作:T(n) = O(f(n)

它表示随着n的增大,算法执行的时间的增长率和f(n)的增长率相同,称为渐进时间复杂度

算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))

  • 基本语句.

    • 算法中重复执行次数和算法的执行时间成正比的语句
    • 对算法运行时间的贡献最大
    • 执行次数最多

  • 问题规模n

    n越大算法执行时间越长

    • 排序:n为记录数
    • 矩阵:n为矩阵的阶数
    • 多项式:n为多项式的项数
    • 集合:n为元素个数
    • 树:n为树的结点个数
    • 图:n为图的顶点数或边数

定理1.1

若f(n)=a_n*n ^ m +a_(n-1)*n(m-1)+…+a_1*n+a_0是m次多项式,则**T(n)=O(nm).**

分析算法时间复杂度的基本方法

  1. 找出语句频度最大的那条语句作为基本语句
  2. 计算基本语句的频度得到问题规模n的某个函数f(n)

  3. 取其数量级用符号”O“表示

    eg
    x=0;y=0;
    for(int k=0;k<n;k++){

    1.     //n+1
    2. x++;                //n

    }
    for(int i=0;i<n;i++){

    1.     //n+1
    2. for(int j=0;j<n;j++){
    3. //n*(n+1) 频度最大
    4.     y++;            //n*n
    5. }

    }

f(n)=n(n+1) T(n)=O(n^2)*

时间复杂度是由嵌套最深层语句的频度决定的

  1. for(i=1;i<=n;i++){
  2.                                     //n+1次
  3.     for(j=1;j<=n;j++){
  4.                                 //n*(n+1)次
  5.         c[i][j]=0;                                //n*n次
  6.         for(k=0;k<n;k++){
  7.                             //n*n*(n+1)次
  8.             c[i][j]=c[i][j]+a[i][k]*b[k][j];    //n*n*n次
  9.         }
  10.     }
  11. }

算法中的基本操作语句为 第五行

在这里插入图片描述

  1. for(i=1;i<=n;i++){
  3.     for(j=1;j<=i;j++){
  5.         for(k=1;k<=j;k++){
  7.             x=x+1;
  8.         }
  9.     }
  10. }

在这里插入图片描述

  1. i=1;
  2. while(i<=n)
  3.     i=i*2;

在这里插入图片描述

在这里插入图片描述

请注意:有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同

  1. 例如
  2.     for(i=0;i<n;i++)
  3.         if(a[i]==e)return i+1;//找到,返回第几个元素
  4.     return 0;
  5. 最好情况 : 1次;
  6. 最坏情况 : n次;
  7. 平均时间复杂度为:O(n)
  • 最坏时间复杂度:指在最坏情况下,算法的时间复杂度.
  • 平均时间复杂度:指在所有可能输入实例在等概率出现的情况下,算法的期望运行时间

  • 最好时间复杂度:指在最好情况下,算法的时间复杂度

    • 一般总是考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长

复杂算法的处理

  • 对于复杂算法,可以分成容易估算的部分,然后利用大O加法法则和乘法法则,计算算法的时间复杂度:

    a)加法规则

    T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

    b)乘法规则

    *T(n)=T1(n)T2(n)= *O(f(n))O(g(n))= *O(f(n)g(n))

空间复杂度

  • 空间复杂度: 算法所需存储空间的度量

    记作: S(n)=O(f(n))

    其中n为问题的规模(或大小)

    • 算法要占据的空间

      • 算法本身要占据空间,输入/输出,指令,常数,变量等
      • 算法要使用的辅助空间

    算法1

    1. for(i=0;i<n/2;i++){
    3.     t=a[i];//调用了一个空间
    4.     a[i]=a[n-i-1];
    5.     a[n-i-1]=t;
    6. }

    //S(n)=O(1);

    算法2

    1. for(i=0;i<n;i++){
    3.     b[i]=a[n-i-1];//调用了n个空间
    4. }
    5. for(i=0;i<n;i++){
    7.     a[i]=b[i];
    8. }

    //S(n)=O(n)

常数,变量等
- 算法要使用的辅助空间

  1. 算法1
  2.     for(i=0;i<n/2;i++){
  4.         t=a[i];//调用了一个空间
  5.         a[i]=a[n-i-1];
  6.         a[n-i-1]=t;
  7.     }
  8. //S(n)=O(1);    
  10. 算法2
  11.     for(i=0;i<n;i++){
  13.         b[i]=a[n-i-1];//调用了n个空间
  14.     }
  15.     for(i=0;i<n;i++){
  17.         a[i]=b[i];
  18.     }
  19. //S(n)=O(n)

抽象数据类型 = 数据的逻辑结构 + 抽象运算 (运算的功能描述)

发表评论

表情：
评论列表 （有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

    相关 算法的时间复杂度和空间复杂度

    通常，对于一个给定的算法，我们要做 两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础

    以你之姓@以你之姓@/ 0 赞/ 127 阅读