算法设计与分析

概述

算法是解决问题方法的精确描述;但是并不是所有问题都有算法，有些问题经研究可行，则相应的有算法，但这并不是说问题就有结果，上述中的“可行”，是指对算法的研究可行

待解问题的描述

待解问题的描述应精确、简练、清楚、使用形式化模型刻画问题是最恰当的。例如，使用数学模型刻画问题是最简明、严格的，一旦问题形式化了，就可依据严格的模型对问题求解

算法设计

算法设计的任务是对各类具体问题设计良好的的算法以及研究设计算法的规律和方法，常用的算法有穷举搜索法、递归法、回溯法、贪心法、分治法等

算法分析

算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度度，探讨某种具体算法适用于哪类问题或某类问题宜采用那种算法。

算法设计原则

设计的真谛，就是在一些互相冲突的需求和越少条件之间寻找平衡点，什么是一个良好的算法，这个问题可以从许多方面来阐述，不管是那种情况，都无法放之四海而皆准，但总有一些原则是在不断的探索中被发现并潜移默化的影响着我们的思维。算法的设计应当遵循一下一些原则

正确性

算法的正确性是指对于一个问题，之所以将其放在第一位是因为如果一个算法自身存在缺陷，或者不适合于问题的求解，那么该算法将不会解决问题。

确定性

算法的确定性是指算法的每个步骤必须含义明确，对每种可能的情况，算法都能给出确定的操作。即采用同一种算法，在同样的条件下无论计算多少次，始终能够得到确定的结果

清晰行

一个良好的算法必须思路清晰，结构合理。算法的设计要模块化，模块化是指将一个大的算法分解成若干小而简单的部分---模块。每个模块可以独立的编写、测试，最后组装完成整个算法。模块化的目的是使算法的结构清晰，容易阅读、容易理解、容易测试、容易修改。模块的分割原则是要符合抽象原则，即指每个模块都要有明确的抽象意义。例如，在面向对象方法中，建立一个类的主要依据是该类描述的抽象数据类型

算法复杂性的度量

算法复杂性的包括算法的时间复杂性和空间复杂性。为了说明复杂性的概念。先介绍问题规模的概念，用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的尺度，称为问题的规模。例如，行列式的规模可以用其阶数n来表示，图问题的规模可以用其边数或者定点数来表示等。

利用某算法来处理一个问题规模为n的输入所需要的的时间称为该算法的时间复杂度，它显示是n的函数记为 $Tn$

类似的可以定义算法的空间复杂性 $Sn$

时间复杂性

阶的增长

显而易见，说一个算法A对于输入x，要用y秒运行是没有意义的，这是因为影响实际时间的因素不仅有相应的算法，还有其他诸多因素，例如，算法在什么机器上和怎样执行的，用的是哪一种编程语言，甚至于编译程序或者程序员的能力都有影响。因此只要的出确切实际的近似数就可以了，但是最重要的是，在评估一个算法效率的时候，我们需要的是确切时间还是近似时间，事实上，我们甚至不需要近似时间，这是由许多因素造成的，首先，在分析算法运行时间时，我们通常会将算法和解决同一个问题甚至是不同问题的算法相比较，这样，估计时间是相对的而不是绝对的，其次，我们希望一个算法不仅是独立于机器的，而且他能够用各种语言来表示，甚至是人类语言，再者，它还应该是技术独立的，也就是说，无论科技如何进步，我们对算法运行时间的测量始终成立，第四，我们主要不是关心小规模输入量的情况，最关心的是在大的输入实例时算法的运行情况

事实上，在算法的某个“合理”实现中的计算运算次数，是比它所需要的的多了一些，作为上面第四种因素的推论，我们可以前进一大步，要精确计算所有的运算次数，如果不是不可能的话，也是非常麻烦的，由于我们只对大的输入时的运行时间感兴趣，可以讨论运行时间的增长率或者增长的阶，例如，如果可以寻找到某个常量c > 0, 当给算法A以大小为n的输入时，算法的运行时间至多为 $cn^2$ ,随着n越来越大，c将主键不起作用，进一步吧这个函数和另一个求解同一个问题的算法B的不同阶函数 $dn^3$ 作比较，很明显，该常量并不会有太大的作用。同样的道理使用与函数 $fn=n^2logn+10n^2+n$ 中的低阶项，我们观察到，当n的值越大，低阶项 $10n^2$ 和n的影响就越小，因此，可以说算法A和B的运行时间分别是“ $n^2$ 阶”和“ $n^3$ 阶”的或者属于“ $n^2$ 阶”和“ $n^3$ 阶”，类似的我们可以说上面的函数 $fn$ 是 $n^2logn$ 阶的

一旦去除了表示算法运行时间的函数中的低阶项和首项常数，就成是在度量算法的渐近运行时间，与此相同，在算法分析的术语中，可以用更为技术性的术语“时间复杂性”来表示这一渐近时间

对任何计算步骤，他的代价总是以一个时间常量为上界，而不管输入数据或者执行的算法，我们称该计算步骤为“元运算”。例如，取2个整数相加的运算，不管使用何种算法，我们都规定他的运算对象的大小是固定的，这一运算的运行时间是常数，而且由于显示是处理渐近的运行时间，我们可以任意选择正整数k为计算模型的“字长”

空间复杂性

我们把算法使用的空间定义成：为了求解问题的实例而执行的计算步骤所需要的的内存空间数目，他不包括分配用来存储输入的空间；换句话说，仅仅是算法需要的工作空间

算法的评价

如何估计算法运行时间

计算迭代次数
计算基本运算的频度