【数据结构与算法】算法和算法分析

一.算法

1.定义

对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。

Step 1:...
Step 2:...
Step 3:...
....

2.描述

• 自然语言：英文，中文

  缺点：麻烦，冗长。

  

• 流程图：传统流程图，NS流程图

  缺点：传统，复杂，占篇幅

  

• 伪代码，类语言：类C语言

  优点：简洁，更适合描述结构化程序

  

• 程序代码：C语言程序，JAVA语言程序…

二.算法与程序

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

三.算法特性

1.一个算法必须具备一下五个重要特性：

• 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
• 确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
• 可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
• 输入：一个算法有零个或多个输入。
• 输出：一个算法有一个或多个输出。

2.算法设计的要求

• 正确性（Correctness）

  算法满足问题要求，能正确和解决问题，算法转化为程序后要注意：

  1.程序中不含语法错误

  2.程序中对于几组输入数据能够得出满足要求的结果

  3.程序对于精心挑选的，典型，苛刻且带有刁难性的几组输入数据能够得出满足要求的结果

  程序对于一切合法的输入数据都能满足要求的结果。通常这一层意义上的正确性作为衡量一个算法是否合格的标准。

• 可读性（Readability）

  1.算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该易于人的理解

  2.另一方面，晦涩难懂的算法易于隐藏较多错误而难以调试。

• 健壮性（Robustness）（鲁棒性）

  1.指当输入非法数据时，算法恰当做出的反应或进行相应处理，而不是产生莫名其妙的输出结果。

  2.处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

• 高效性（Efficiency）

  要求花费尽量少的时间和尽量低的存储要求。从以下两个方面来考虑：

  • 时间效率：指的是算法所耗费的时间
  • 空间效率：指的是算法执行过程中所耗费的存储空间

一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。对于同一个问题，可有不同的算法，那么，如何评价这些算法的效率高低呢？

然而，时间效率和空间效率有时候是矛盾的

有时候要节约时间却耗费了很多空间，有时候要节约空间却耗费了很多时间。通常以要解决的实际问题的需要来综合平衡，有所侧重，结合计算机的性能，以及我们要处理的问题的数据量的大小来综合平衡考虑对算法的要求。

以下，我们从时间效率和空间效率两个方面来说明

四.算法效率的度量

4.1算法时间

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量，算法时间的度量有事后统计和事前统计两种方法，事后度量先实现算法再测试时间，要花费较多的时间和精力，所以优先选择事前分析法。

事前分析法

• 对算法所消耗资源的一种估算方法。
• 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值，比较，移动等）所需的时间与算法中进行简单操作次数乘积。

算法运行时间=一个简单操作所需时间×简单操作次数

• 也即算法中每条语句的执行时间之和

算法运行时间=∑语句频度（每条语句的执行次数）×该语句执行一次所需时间

• 每条语句执行一次所需的时间，一般是随机器而异的。取决于机器的指令性能，速度以及编译的代码质量。是由机器本身软硬件环境决定的，它与算法无关。既然在一个机器中所有算法执行一条语句的单位时间都是一样的，所以我们可以假设执行每条语句所需时间均为单位时间。此时对算法的运行时间的讨论就可以转化为讨论该算法中所有语句的执行次数，即上述式子就可以约去“该语句执行一次所需时间”，直接比较语句频度之和了。
• 这就可以独立于不同机器的软硬件环境来分析算法的时间性能了。

实例：用循环变量控制执行次数

//两个n×n矩阵相乘的算法可以描述为：
for(i=1;i<=n;i++)                  //执行n+1次（条件不执行，跳出循环）
    for(j=1;j<=n;j++){             //作为最外层for的循环体执行n次，同时这个for循环体本身执行n+1次，共执行n(n+1)次
        c[i][j]=0;                 //第二层for循环的循环体，执行n×n次
        for(k=0;k<n;k++)           //第三层for循环同理，执行n*n*(n+1)次
            c[i][j]=c[i][j]+a[i][k]*b[i][j];//n*n*n次
    }

最后对每条语句的执行次数进行求和运算，即求出该算法中每条语句的频度之和，则上述算法的时间消耗

T(n)=2n³⁺³ⁿ2+2n+1（这是一个关于n的函数）

那么，对于所有程序都要这样一步步算岂不是很麻烦吗？

算法时间复杂度的渐进表示法

• 为了便于比较不同算法的时间效率，我们仅比较他们的数量级（找到对时间贡献最大的语句，在计算数量级时忽略所有的低次幂项和最高次幂系数，只计算最高次项的数量级）
• 若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度。它表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐进时间复杂度。

例如，对于求解矩阵相乘问题，算法耗费时间：T(n)=2n³⁺³ⁿ2+2n+1

n→∞时,T(n)/n^{3->2，这表示n充分大时，T(n)与n}3是同阶或数量级，引入大“O”记号，则T(n)可以记作：T(n)=O(n^3),意思是说这里所求的渐进时间复杂度和n^3同阶，这就是求解矩阵相乘问题的渐进时间复杂度。

一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T(n)表示。定义：算法中基本语句重复执行的次数是问题规模n的某个函数f(n)

• 基本语句是指：算法中，重复执行次数和算法的执行时间成正比的语句，对算法运行时间的贡献最大的语句，执行次数最多的语句，由此可见，时间复杂度是由嵌套最深层语句的频度决定的。

• 语句频度：一个算法中基本语句的执行次数称为语句频度或时间频度，记为T(n)。

• 问题规模n：是描述数据量的一个变量，n越大，算法的执行时间越长

  f(n) n越大算法的执行时间越长

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

• 常见的时间复杂度量级

  • 常数阶：O(1)
  • 对数阶：O(logN)
  • 线性阶：O(n)
  • 线性对数阶：O(nlogN)
  • 平方阶：O()
  • 立方阶：O()
  • k次方阶：O()
  • 指数阶：O()

  从上至下依次的时间复杂度越来越大，执行的效率越来越低

• 其他：

  • 多项式复杂度：O()
  • 阶乘复杂度：O(n!) O()<O(n!)<O()
  • 在无序数列中查找某个数（顺序查找）：O(n)
  • 平面上有n个点，求出任意两点间的距离：O()
  • 插入排序、选择排序、冒泡排序：O()
  • 快速排序：O(n*log(n))
  • 二分查找：O(log(n))

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

1.找出语句频度最大的那条语句作为基本语句

2.计算基本语句的频度得到问题规模n的某个函数f(n)

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

4.2算法空间

一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。用S(n)来定义。计算公式S(n)=O(f(n)).其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

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