算法

算法和算法分析

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

一个算法具有下列5个重要特性：

• 有穷性：一个算法必须总是（对任何合法的输入值）在执行有限步之后结束，且每一步都可在有限时间内完成。有穷的概念不是纯数学的，而是在实际上是合理的，可接受的。
• 确定性：算法中每一条指令必须有确切的含义，不会产生二义性。
• 可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
• 输入性：一个算法有零个或多个输入。
• 输出性：一个算法有一个或多个输出。

算法设计的要求

算法设计应满足以下几条目标：

• 正确性：算法应当满足具体问题的需求，这是最重要也是最基本的标准。

“正确”一词的含义，大体可分为以下4个层次:

a.程序不含语法错误;
b.程序对于几组输入数据能够得出满足规格说明要求的结果;
c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;
d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果

• 可读性：算法主要是为了人的阅读与交流，其次才是机器执行。
  可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的。

• 健壮性：当输入数据非法时， 算法也能适当地做出反应或进行处理， 而不会产生莫明其妙的输出结果。

• 高效率与低存储量需求
  通俗地说，效率指的是算法执行的时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率髙。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关

算法效率的度量

计算机资源主要包括计算时间和内存空间。

• 算法分析是分析算法占用计算机资源的情况。所以算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。

• 算法分析的目的不是分析算法是否正确或是否容易阅读，主要是考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。

有两种衡量算法效率的方法：

1. 事后统计的方法
2. 事前分析估算的方法

事后统计法存在的缺点：

一是必须先运行依据算法编制的程序;
二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。

因此人们常常采用另一种事前分析估算的方法:

事前分析估算的方法

一个用髙级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

① 依据的算法选用何种策略；
② 问题的规模，例如求100以内还是1000以内的素数；
③ 书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低；
④ 编译程序所产生的机器代码的质量；
⑤ 机器执行指令的速度。

这表明使用绝对的时间单位衡量算法的效率是不合适的。

撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模(通常用整数量n表示），或者说，它是问题规模的函数。

时间复杂度

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

算法的执行时间主要与问题规模n有关。

例如，整数n的大小、数组的元素个数、矩阵的阶数等都可作为问题规模。

所谓一个语句的频度，即指该语句在算法中被重复执行的次数。
算法中所有语句的频度之和记做f(n)，它是问题规模n的函数。
当问题规模n趋向无穷大时，f(n)的数量级(Order)称为渐进时间复杂度，简称为时间复杂度，记作T(n)=O(f(n))。

算法的时间量度记作：T(n)=O(f(n))
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度（asymptotic time complexity)，简称时间复杂度。

定理：

一个没有循环的算法中基本运算次数与问题规模n无 关，记作O(1)，也称作常量阶
一个只有单循环的算法中基本运算次数与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。
常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等等。

• 不同数量级对应的值存在着如下关系：

空间复杂度

一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间，如形参所占空间和局部变量所占空间等。

对算法进行存储空间分析时，只考察局部变量所占空间。

算法的临时空间一般也作为问题规模n的函数，以数量级形式给出，记作：S(n) = O(g(n))，其中“O”的含义与时间复杂度中的含义相同。

若算法所需临时空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作。

若所需临时空间依赖于特定的输入，则通常按最坏情况来考虑。

总结

“好”算法的标准

解决一个问题的方法可能有很多，但能称得上算法的，首先它必须能彻底解决这个问题（称为准确性），且根据其编写出的程序在任何情况下都不能崩溃（称为健壮性）。

注意，程序和算法是完全不同的概念。算法是解决某个问题的想法、思路；而程序是在根据算法编写出来的真正可以运行的代码。例如，要依次输出一维数组中的数据元素的值，首先想到的是使用循环结构，在这个算法的基础上，我们才开始编写程序。

在满足准确性和健壮性的基础上，还有一个重要的筛选条件，即通过算法所编写出的程序的运行效率。程序的运行效率具体可以从 2 个方面衡量，分别为：

• 程序的运行时间。
• 程序运行所需内存空间的大小。

根据算法编写出的程序，运行时间更短，运行期间占用的内存更少，该算法的运行效率就更高，算法也就更好。

时间复杂度

判断一个算法所编程序运行时间的多少，并不是将程序编写出来，通过在计算机上运行所消耗的时间来度量。原因很简单，一方面，解决一个问题的算法可能有很多种，一一实现的工作量无疑是巨大的，得不偿失；另一方面，不同计算机的软、硬件环境不同，即便使用同一台计算机，不同时间段其系统环境也不相同，程序的运行时间很可能会受影响，严重时甚至会导致误判。

表示一个算法所编程序运行时间的多少，用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。

也许很多读者对于“使用无限大的思想”简化频度表达式，并不是很清楚。没关系，这里给大家总结一下，在数据结构中，频度表达式可以这样简化：

• 去掉频度表达式中，所有的加法常数式子。例如 \(2n^{2}+2n+1\)简化为\(2n^{2}+2n\)；
• 如果表达式有多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。例如 \(2n^{2}+2*n\)简化为 \(2n^{2}\)；
• 如果最高项存在系数，且不为 \(1\)，直接去掉系数。例如 \(2n^{2}\) 系数为 \(2\)，直接简化为 \(n^{2}\) ；

事实上，对于一个算法（或者一段程序）来说，其最简频度往往就是最深层次的循环结构中某一条语句的执行次数。例如 2n+1 最简为 n，实际上就是 a++ 语句的执行次数；同样 2n2+2n+1 简化为 n2，实际上就是最内层循环中 num++ 语句的执行次数。

空间复杂度

要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：

• 程序代码本身所占用的存储空间；
• 程序中如果需要输入输出数据，也会占用一定的存储空间；
• 程序在运行过程中，可能还需要临时申请更多的存储空间。

所以，如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 \(O(1)\)；反之，如果有关，则需要进一步判断它们之间的关系：

• 如果随着输入值 \(n\) 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 \(O(n)\) 表示;
• 如果随着输入值 \(n\) 的增大，程序申请的临时空间成 \(n^{2}\) 关系增长，则程序的空间复杂度用 \(O(n^{2})\) 表示；
• 如果随着输入值 \(n\) 的增大，程序申请的临时空间成 \(n^{3}\) 关系增长，则程序的空间复杂度用 \(O(n^{3})\) 表示；
• 等等。