算法设计与分析（超详解！） 第一节 算法概述

1.算法的定义

算法的非形式化定义：算法是规则的有限集合，是为解决特定问题而规定的一系列操作。

可以理解为：算法（algorithm）是指在解决问题时，按照某种机械的步骤一定可以得到问题的结果（有的问题有解，有的没有）的处理过程。算法就是解决这个问题的方法和步骤的描述。

2.算法的特征

有限性：一个算法必须保证执行有限步骤之后结束，即算法的每个步骤都能在有限的时间内完成。即算法的每个步骤都能在有限的时间内完成。

确定性：算法的每一步骤必须有确切的定义，不能有歧义。对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者和阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

可行性：算法原则上能精确的运行，在现有条件下是可以实现的。算法中描述的操作都可以通过已经实现的基本操作运算有限次地实现。

输入：一个算法有0个或者多个输入，以刻画运算对象初始状态。

输出：一个算法有一个或者多个输出，以反映对输入数据加工后的结果。由于算法需要给出解决问题的结果，没有输出结果的算法是毫无意义的。

注：

1.前三个特征较为集中的表现处理步骤，后两个特征则涉及输出与输出接口问题

2.可以依据特征判定算法的合理性

3.算法与程序的区别

程序是算法用某种程序设计语言的具体实现。

算法描述了问题的处理方式或者步骤，程序则采用具体的语言规则实现算法的功能，算法要依靠程序完成功能，程序是算法的灵魂。算法可以用语言、文字、框图来描写，也可以用计算机、纸笔人工进行模拟。程序不一定满足有穷性，可以直接在机器环境下运行。（操作系统）

3.算法的描述方法

1.自然语言

自然语言比较符合人类的阅读习惯，是一种容易理解的方式。不过，这种方式的缺点是无法很准确的描述循环、选择等结构。在使用自然语言描述算法的过程中，要求算法语言简练、层次清楚。因此，要注意语言和标点符号的使用。初次之外，还要在每个步骤前加上数字的标号。

2.框图（流程图）

流程图是描述代码的一种很好的工具，利用流程图，可以很好的表现出秩序执行过程中的三种基本结构组成—顺序结构、选择结构、循环结构等。需要注意的是，在使用流程图时，规定需要使用一些基本图形。 

① 起止框：表示算法的开始与结束。

② 判断框：对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。

③ 输入输出框：表示算法的输入与输出操作。

④ 连接点：用于将画在不同地方的流程线连接起来，同时表示算法的执行顺序。

结构：

（a）顺序结构  在执行完A框操作后，紧接着执行B框操作

（b）选择结构 此结构中必包含一个判断框。根据条件p是否成立来选择执行A框或B框

（c）循环结构(while,直到型)

3.N-S图

N-S图又称N-S结构化流程图、盒图，它将全部算法写在一个矩形框内，在该框内可包含它的从属框。也就是说，由一些基本框可以组成一个大的矩形框，即N-S图。

① 一个结构化的算法是由一些基本结构顺序组成的；

② 在基本结构之间不存在向前或者向后的跳转，流程的转移只存在于一个基本结构内部（如循环结构中的流程跳转）；

③ 一个非结构化算法有时可以等价为一个结构化算法，且功能不变。

4.高级语言（严格的机器语言）

高级语言就是用计算机程序设计语言直接表达算法，是可以在计算机上直接运行的源程序。高级语言描述算法具有严谨、准确的特点，但是用于描述算法，也有语言细节过多的缺点

5.类语言（伪代码）

伪代码是用介于自然语言与计算机语言之间的文字和符号来描述算法。它无固定的、严格的语法规则，书写格式自由，且易于修改，只要表达清楚意思即可。 伪代码主要是用来表示代码之间的逻辑关系，并不能交由计算机执行。因此，主要使用对象是设计师和程序员，是用来表达在编码前对算法执行过程中的一些想法的工具。

4.求解问题的一般步骤

5.算法分析准则

1.正确性

算法的正确性最为重要。一个正确的算法应当对所有合法的输人数据都能得到应该得到的结果。对于那些简单的算法,可以通过调试验证其正确与否。要精心挑选那些具有“代表性的”,甚至有点“刁钻”的数据进行调试,以保证算法对“所有”的数据都是正确的。一般来说,调试并不能保证算法对所有的数据都正确,只能保证对部分数据正确,调试只能验证算法有错,不能验证算法无错。要保证算法的正确性,通常要用数学归纳法证明。

算法的正确性是指假设给定有意义的输入,算法经有限时间计算,可产生正确答案先建立精确命题,证明给出某些输人后,算法将产生结果;然后证明这个命题。一个算法的正确性有两方面的含义:解决问题的方法选取是正确的,也就是数学上的正确性;实现这个方法的一系列指令是正确的。在算法分析中我们更看重的是前者。

正确性的四个层次：

1.程序不包含语法错误

2.程序对几组输入数据满足规格要求结果

3.对典型的、苛刻的、带有刁难性的几 组输入有正确的结果

4.对一切合法的输入都能产生满足规格 要求的结果

2.可读性

算法重要的作用之一就是便于阅读与交流，可读性有助于对算法的理解、调试和修改

3.健壮性

算法的健壮性是指算法在处理各种不同的输入数据时的性能和稳定性。一个算法越健壮，就越能够适应输入数据的变化并保持较高的性能。 为了评估算法的健壮性，通常需要对算法进行测试，并观察它在处理不同类型的输入数据时的表现。一个算法可能会在处理某些类型的数据时表现良好，但在处理其他类型的数据时表现不佳。因此，算法的健壮性通常是相对的，取决于算法需要处理的特定类型的数据。 对于某些应用，算法的健壮性是非常重要的，因为它决定了算法的可靠性和可用性。例如，在医疗领域，算法的健壮性可能决定了算法是否能够准确地诊断疾病，从而直接影响患者的健康。因此，在设计和使用算法时，健壮性是一个非常重要的考虑因素。

4.高效率和低存储

1.时间复杂度

算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作：T(n)=O(f(n))，称作算法的渐近时间复杂度（Asymptotic Time complexity），简称时间复杂度。

一般地，常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。 表示时间复杂度的阶有： O(1)：常量时间阶 O(n)：线性时间阶 O(logn)：对数时间阶 O(n*logn)：线性对数时间阶 O (n^k)：k≥2，k次方时间阶。

2.空间复杂度

空间复杂度（Space complexity）：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S(n) = O(f(n))，其中：n为问题的规模或大小。

存储空间一般包括三个方面： 输入数据所占用的存储空间； 指令常数变量所占用的存储空间； 辅助（存储）空间。

6.常用术语

1.计量单位

2.阶乘函数

3.排列组合

4.布尔变量

bool是布尔型变量，也就是逻辑型变量的定义符，类似于float,double等，只不过float定义浮点型，double定义双精度浮点型。 在objective-c中提供了相似的类型BOOL，它具有YES值和NO值。

  布尔型变量的值只有 真 （true) 和假 （false）。

布尔型变量可用于逻辑表达式，也就是“或”“与”“非”之类的逻辑运算和大于小于之类的关系运算，逻辑表达式运算结果为真或为假。

bool可用于定义函数类型为布尔型，函数里可以有 return TRUE; return FALSE 之类的语句。

布尔型运算结果常用于条件语句。

5.上下取整

6.取模操作

取模操作是一种常见的数学运算，也称为求余运算。它用于计算一个数除以另一个数后的余数。在大多数编程语言中，取模操作使用符号 “%” 表示。

取模操作的基本语法是：a % b，其中 a 和 b 是两个整数。它的计算规则是：将 a 除以 b，得到的商去掉小数部分，然后将剩下的余数作为结果返回。

7.算法复杂性分析

复杂性就是算法所需的计算机资源。所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。它是算法效率的度量，是评价算法优劣的重要依据。

复杂性根据算法运行所占计算机中的资源类型可以分为：算法的空间复杂性和算法的时间复杂性。

时间复杂度：时间复杂度分为最好时间复杂度、最坏时间复杂度、平均时间复杂度。 最好时间复杂度就是解决同类问题的最小耗费，证明解决问题的下界。反之则是最坏时间复杂度。平均时间复杂度即为耗费的平均值。

算法复杂性 = 算法所需要的计算机资源

算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。

1.复杂函数      

复杂函数公式为C=F（N，I，A）          

N为问题的规，I指的是输入，A为算法本身。问题规模N：反映问题大小本质定义。

从CPU的角度看，我们程序的每一行都在执行着读数据-运算-写数据的操作。尽管每行代码对应的cpu的执行个数及时间都不一样，但是由于我们现在讨论的没有那么精准，所以假设每行代码执行时间都一样。

复杂度耗费的时间从小到大依次是：

 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^k)

2.算法的时间复杂度

一个算法的执行时间=算法中所有语句执行时间的总和。

每条语句的执行时间=该条语句的执行次数*执行一次所需实际时间。

在非递归算法中时间计算如下：  

1. for/while循环：循环体内计算时间*循环次数  

2. 嵌套循环：循环体内计算时间*所有循环次数  

3.顺序语句：各语句计算时间相加  

4. if-else语句：if语句计算时间和else语句计算时间的较大者

复杂度表示方法只是表示一种变化趋势，通常可忽略掉公式中的常量、低阶、系数，只需记录最大阶的量级即可。

加法法则：总复杂度等于量级最大的那段代码的复杂度

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

这里的O表示法并不表示代码真正的执行时间，而是表示一种代码执行时间随着数据规模增长的变化趋势，也叫渐进时间复杂度（asymptotic time complexity），简称时间复杂度。 由于公式中的常量、系数和低阶并不左右这种对应关系的增长趋势，所以我们只记一个最大量级即可。即T(n) = O(n)。

语句频度：

语句频度指该语句在一个算法中重复执行的次数。一个算法的时间耗费就是该算法中所有语句频度之和

最坏情况复杂度：最坏情况复杂度是指在最不利的输入情况下，算法执行所需的时间或空间资源。它提供了算法在任何输入情况下的上界。

平均情况复杂度：平均情况复杂度是指在所有可能输入情况下，算法执行所需的时间或空间资源的期望值。它考虑了各种输入情况的概率分布。

最好情况复杂度：最好情况复杂度是指在最有利的输入情况下，算法执行所需的时间或空间资源。它提供了算法在任何输入情况下的下界。

Dn表示多规模输入集，P（I）表示概率，f（I）表示操作时间。

渐进分析：

渐进形态：设f和g是定义在N上的函数，则f和g之间的函数阶可用渐近形态进行表示。渐近形态的三个记号：O—>低阶  Ω—>高阶  θ—>等阶

1.低阶O： 若存在一个正常数C，n0，对所有n>n0，都有f(n)≤g(n)，则记作f=O（g），或f的阶不高于g的阶。

2.高阶Ω： 若存在正常数C和    (C≠0)，使得

3.等阶： 若存在正常数C和    (C≠0)，使得f(n)与g(n)同阶。

渐进分析中函数比较：

性质：

1.传递性

2.反身性

3.对称性

4.互对称性

5.算术运算