针对机器：空间复杂性和时间复杂性；
 
针对程序员：算法表达和实现的简单性；
 
针对问题：算法对问题及问题输入规模的普适性；

“算法设计与分析”
 
1、 什么是算法？算法有哪些基本特征？请指出算法同程序的相同点与不同点。（课件之“绪论”，教材之“绪论”，page:1）
 
答：算法是解决问题的方法或过程，是满足以下四个性质的指令序列
 
    1）输入：有0个以上的输入 
 
2）输出：至少有1个输出
 
3）确定性：指令清晰、无歧义
 
4）有限性：指令执行次数有限，时间有限
 
算法和程序的相同点：两者都具有输入、输出和确定性的特征
 
不同点：程序是算法用某种程序语言的具体实现，程序不满足算法具有的有限性性质
 
2、 请描述算法设计的一般过程。（课件之“绪论”）
 
答：算法设计的一般过程是
 
1）提出问题
 
2）确定数学模型
 
3）明确目的、条件和约束关系
 
4）设计求解步骤
 
5）结果评估与分析
 
如果在第5步的分析中对算法时间、空间复杂度或结果不满意，可以返回第1步或第4步进一步迭代，直至找到满意的算法。
 

 
 
3、 什么是算法复杂性？它主要有哪两个方面构成？（课件之“绪论”）
 
答：算法复杂性是算法运行时所需要的计算机资源的量，它包括两个方面：时间复杂性（需要时间资源的量）和空间复杂性（需要空间资源的量）。
 
4、 时间复杂性分析主要分哪三种情况，哪种情况的可操作性最好，最具有实际价值？（课件之“绪论”）
 
答：时间复杂性分为3种情况，最好情况、平均情况、最坏情况，可操作性最好，最具有实际价值的是最坏情况下的时间复杂性
 
5、 如果算法A由三个步骤组成，其中第一步的时间复杂性为O(n2)，第二步的时间复杂性为O(nlogn)，第三步的时间复杂性为O(n)，请问算法A的时间复杂性是多少？（教材之“绪论”，page:15）
 
答：O(n2)
 
6、 请问二分搜索算法、快速排序算法、线性时间选择算法和最近点对问题的时间复杂性各为多少？（教材之“递归与分治”，page:27,37,39,43）
 
答：二分搜索算法：最坏情况O(logn)、
 
快速排序算法:最坏情况O(n2)，最好情况和平均情况均为O(nlogn)
 
线性时间选择算法:最坏情况O(n)
 
最近点对问题:时间复杂性O(nlogn)
 
7、 分治算法和动态规划算法都是通过对问题进行分解，通过对子问题的求解然后进行解重构，从而实现对原问题的求解。请指出这两种算法在对问题进行分解时各自所遵循的原则。（课件之“递归与分治”，课件之“动态规划”）
 
答：分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题（不包含公共的子问题）。
 
动态规划对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互关联的与原问题类似的子问题（包含公共的子问题），采用记录表的方法来保存所有已解决问题的答案，而在需要的时候再找出已求得的答案，避免大量的重复计算。
 
8、 动态规划算法的本质是什么，请简要阐述。（课件之“动态规划”）
 
答：动态规划的实质是分治思想和解决冗余，动态规划算法是将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
 
9、 如果一个问题可以利用动态规划算法求解，那么该问题应满足什么条件？（教材之“动态规划”，page:67）
 
答：该问题具有最优子结构性质（一个问题的最优解包含其子问题的最优解）和子问题重叠性质（每次递归产生的子问题不总是新问题，有些子问题被反复计算多次）
 
10、动态规划算法的基本思想是什么？请简述动态规划算法主要设计步骤。（教材之“动态规划”，page:61）
 
答：动态规划算法的基本思想是将待求解问题分解成若干个相互关联的与原问题类似的子问题，求解这些子问题，并保存子问题的答案，避免重复计算，然后从这些子问题的解得到原问题的解。
 
动态规划算法主要设计步骤：
 
1）找出最优解的性质，并刻画其结构特征；
 
2）递归地定义最优值；
 
3）以自底向上的方式计算出最优值；
 
4）根据计算最优值时得到的信息，构造最优解；
 
11、什么是备忘录方法？它同动态规划法相比主要不同点是什么？请指出动态规划法和备忘录方法各自的适用范围。（课件之“动态规划”）
 
答：备忘录方法是动态规划算法的变形，它通过分治思想对原问题进行分解，以存储子问题的解的方式解决冗余计算，并采用自顶向下的递归方式获取问题的最终解。
 
与动态规划算法的不同之处是动态规划算法的递归方式是自底向上递归求解，而备忘录方法的递归方式是自顶向下递归求解。
 
当一个问题的所有子问题都至少要解一次时，使用动态规划算法。
 
当子问题空间中的部分子问题不需要求解时，使用备忘录方法。
 
12、贪心算法的设计思想是什么，有什么特点？如果一个问题用贪心算法可以获得全局最优解，那么该问题的求解应满足哪些条件？（课件之“贪心算法”，教材之“贪心策略”,page110）
 
答：贪心算法的设计思想是在对问题求解时，总是做出在当前看来是最好的选择。
 
它的特点是1）不是从整体考虑——得到的解可能不是全局最优 2）简单，直接，易理解，效率高。
 
如使用贪心算法求解问题获得全局最优解，则问题应满足
 
1）贪心选择性质（与动态规划的主要区别）
 
所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到
 
2）最优子结构性质（动态规划算法和贪心算法的共同点）
 
一个问题的最优解包含其子问题的最优解时。
 
13、请简要描述回溯法的实现过程。用回溯法求解0/1背包问题、TSP问题、N皇后问题和连续邮资问题时，其各自的解空间树各是什么形式？(课件之“回溯法”，教材之“回溯法”page147）
 
答：实现过程：确定解空间的组织结构，然后从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。
 
在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为扩展结点。否则如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）到最近的活结点处，并使该结点成为当前的扩展结点。
 
回溯法按上述方式递归地在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。
 
0/1背包：n+1层的子集树  TSP问题：(n-1)!个叶节点的排列树
 
N皇后问题：完全n叉树    连续邮资问题：n层树，其中结点的度随着本结点取值范围而变化的树？？
 
14、影响回溯法效率的主要因素有哪些？如何有效地估算回溯法在求解具体实例时产生的中间节点数量？(课件之“回溯法”，教材之“回溯法”page187，188）
 
答：影响回溯法效率的主要因素
 
1）产生x[k]的时间
 
2）满足显约束的x[k]值的个数
 
3）计算约束函数constrain的时间
 
4）计算上界函数bound的时间
 
5）满足约束函数和上界函数约束的所有x[k]的个数
 
采用概率方法可以有效地估算回溯法在求解具体实例时产生的中间节点数量：
 
（即在解空间树上产生一条随机路径，然后沿该路径估算解空间中满足约束条件的节点数m，由于使用静态约束函数，在某些情况下产生的估计较为保守。因此还可以多选取几条不同的路径，分别计算m，然后平均，这样的估算结果会更准确些。）
 
15、请简述分支限界法的算法思想以及两种主要的实现方法。(课件之“分支限界法”，教材之“分支限界法”page195，196）
 
答：分支限界法的算法思想是在问题的解空间树上以广度优先或最小耗费（最大效益）优先方式搜索问题的满足约束条件的一个解或最优解。（搜索策略：每一个活结点只有一次机会成为扩展结点。扩展结点一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中按一定的策略取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。）
 
分支限界法根据从活结点表中选择下一个扩展结点的方式有两种实现方法
 
1）队列式FIFO分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。  
 
2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
 
（最大优先队列：使用最大堆，体现最大效益优先 
 
最小优先队列：使用最小堆，体现最小费用优先）
 
16、请指出回溯法与分支限界法的相同点与不同点。(课件之“分支限界法”）
 
答：相同点：
 
1）两者在进行问题求解前，都需要完成解空间的定义和组织；
 
2）都是通过在解空间树上搜索来寻找问题的解；
 
不同点：
 
1）搜索方式
 
回溯法：深度优先；
 
分支限界法：广度优先；
 
2）搜索策略
 
回溯法：根据剪枝函数，选择下一个扩展接点并按深度优先方式进行搜索；
 
分支限界法：在扩展结点处，先产生其所有的子结点（分支），然后根据限界函数，确定哪些子结点将导致不可行解或非最优解，将这些子结点剔除，用剩下的子结点构造当前的活结点表，然后从该表中取一个结点作为当前扩展结点，并重复上述过程；
 
17、概率算法主要有哪些类型？它们各自的主要特点是什么？如何有效提高概率算法获得正确解的概率或提高算法的求解精度？(课件之“概率算法”，教材之“概率算法”page241）
 
答：1）数值概率算法：常用于数值问题的求解，得到的往往是近似解
 
（1）解的精度随计算时间的增加而提高
 
（2）在许多情况下，计算出问题的精确解是不可能或没必要
 
2）蒙特卡罗算法：用于求解问题的准确解，可以求得问题的一个解，但该解未必正确
 
（1）求得正确解的概率依赖于算法的计算时间
 
多次执行蒙特卡罗算法，可以提高获得正确解的概率
 
（2）无法有效判定所得到的解是否肯定正确。
 
3）拉斯维加斯算法：不会得到不正确的解
 
（1）有时找不到问题的解
 
（2）找到正确解的概率随算法计算时间的增加而提高
 
（3）用同一拉斯维加斯算法反复对问题实例求解足够多次，可使求解失败的概率任意小。
 
4）舍伍德算法：总能求解得到问题的一个解，而且所求得得解总是正确的。
 
将确定性算法引入随机性改造成舍伍德算法，可消除或减少问题对于好坏实例间的差别。
 
 
 
18）对于NP完全问题，我们一般采取的求解策略主要有哪些？(课件之“近似算法”，教材之“近似算法”page326）
 
答：NP完全问题可行的解题策略
 
1）只对问题的特殊实例求解
 
2）用动态规划法或分支限界法求解
 
3）用概率算法求解
 
4）只求近似解
 
5）用启发式方法求解
 
 
 
 

算法速度影响因素的本质
表面上，算法速度的影响因素繁多，但事实上，如果我们穷根究底的话，也会在这个看似繁乱无序的世界里找出一些本质的东西。
先考虑这么一个问题：
如果b地在a地正东方，一个人要从a地去b地，那他可以有什么方法来缩短所花的时间？
第一当然是交通工具。选择汽车和步行自然不可能是相同的效果，这对应与下文的第一部分：函数存储
第二是不走弯路，若他向东南方向走了，那他就在南北方向上有了向南的偏移，之后他就必须向东北方向走来抵消刚才的偏移，这对应与下文的部分：计算冗余。
现在让他的行进速度和其经验相关，比如，翻过第一座山后由于有了经验，今后翻山的速度会有很大的提升，这对应于下文的第二部分：过程存储
 
1 函数存储
计算机能以最快速度实现的操作，我们将称之为基本操作。比如简单的加减、逻辑运算，存储器读取写入，if...then语句等等。
显然，计算机能进行的基本操作越多，算法速度就越容易提升。图灵机可进行的基本操作是很少的，一个简单的加法都要计算上很多步，因此没人会去试图造台图灵机作电脑用^_^。
对输入为有限种可能的情况，我们可以建立一个散列表，将输入直接映射到内存地址上，而存储的内容为相应输入的输出结果，这样便产生了一个运行时间几乎和一次基本操作相当的算法。这样其实就是相当于把所要计算的函数直接存储到了内存里，使计算机又多了一个基本操作。可以看出这样对算法的速度提升会是惊人的（虽然是牺牲空间得到的）。这样方法其实我们在作算术中就应用到了：小学生背乘法表是为了什么？存储一系列函数，等计算更复杂的乘法时便可以将它分解成这些函数，然后快速得到结果。相必没人作乘法是先拆成加法，再一个个加起来吧？
综上所述，当算法中出现对一个函数的频繁调用，而这个函数又是定义域有限且元素不多的，我们就可以把该函数存储到内存里，做成一个基本操作，这样就会对算法效率有质的影响。
 
但基本操作少了也有它的好处，这样各种操作容易各司其职，功能互不交叉，要用操作a完成的功能b肯定不能替代，比如说变量值加1操作和goto语句。这样以来，要实现某个功能时就不需在各个可行的基本操作中进行孰优孰劣选择了。所以想用函数存储优化算法是很困难的，如果有一天计算机可以自己生成算法了，它是基本上不可能掌握上面所说的这种方法的，除非依赖人工智能。它可以轻松掌握的方法或许应该是下面这个：
 
2 过程存储
下文中将出现的“过程”不同于一般编程语言中“过程”的概念，它是指函数的一次特定调用，包括输入值和被调用函数。调用一个过程所返回的值即该输入值经该函数计算后的结果。在一次计算的某个时刻，访问任一个变量都相当于调用了一个过程，那是向前访问过去的计算结果，而调用函数是向后将数据或控制权传给未来的函数；反过来也成立，向过去只可能出现过程调用，而向未来只可能出现函数调用。
 
数据结构对算法速度的影响是和电子计算机提供的两个基本操作相关的，就是内存的读/写。和他们相关的其实还有建立中间变量之类一切和存储/读取相关的操作。
建立合适的数据结构，建立合适的中间变量都有可能大幅度提高算法效率，那它们的本质是什么呢？
一个量的存储便意味着今后可随时以一个单位时间的运算速度调用计算出该量的过程，这样，如果一个过程在一次计算中出现多次，那么将其第一次运行所得结果存储从而替代后来的多次运算无疑是高效的，这正是变量存读问题的关键所在：将计算过的结果存储，之后免除了计算过程，我们暂且称之为过程存储。
显然，过程存储是不同于函数存储的。后者是算法设计时就将函数“存储”了，它是运行中“存储”的；后者是通过增加基本操作来提高速度，而前者只是避免了重复计算，并未增加基本操作。
过程存储和函数存储一样，也是适用于当算法中出现对一个函数的频繁调用，而这个函数又是定义域有限且元素不多的时候。当然，它的效率会稍低。
 
过程存储还有另一个优美的描述，就是跨时间的信息传递。我们不妨把存储和读取的概念从视野中完全抹掉，一个量的存储只是将其传递给了未来的一个或多个函数，而读取只是接受了过去某个过程传来的输入。这样，过程的调用概念就更广了，成为了跨时间的概念。
这样我们不难理解中间变量和数据结构对算法影响的实质了，前者充当了调用过去过程的桥梁，避免了同一过程的重复计算，而后者是前者更复杂的形式，而且与指针关系紧密，所以我们暂且只举例说明。
例:
某算法的输入中包含一字符串s，算法运行中将对s进行大量的查找工作。
如果仅靠以上信息而且不考虑空间复杂度的话，我们知道散列表是存储s的最佳选择。
S中出现的所有字符通过散列函数f映射到不同的内存地址，而内存中的数据则为相应各字母在字符串中的位置。这样要比不改变S的数据结构而每次查找都用遍历S的方法好的多。
我们来分析它和过程存储的关系：建立散列表时，若在内存地址为A（值为f（K））的项中写入了一个数组，它存储了K出现在S中的所有位置。那么，这就相当于向未来的函数提供了这样一个过程的调用：
遍历S，记录所有值等于K的元素在S中的位置并将其放入一个数组中，返回这个数组。
当然，这个调用花费的时间是很短的，而远非遍历一遍S的时间。
 

数据结构和过程存储的关系至此还是不甚清楚，再作进一步的分析。
数据结构就是信息组织在计算机中的形式。这个概念其实也是很模糊的，什么是信息?什么是组织形式？为什么组织形式对算法速度影响如此之大?
信息是可以用函数来表示的。比如，一个字符串可用一个以字符在其中的位置为自变量，字符为函数值的函数，即：
f：位置－－>字符
信息即若干量的值之间的关系。但在实际中将其以某种形式表示出来时，往往只能表示出该关系的一个单向的形式，如上例中的字符串存入一个数组后，该数组就包含了字符串的全部信息，但它却只能提供一个单向的访问，即由位置得到字符，若要由字符得到其对应的地址，哦，sorry，本数组不提供该项服务，请自己您写代码遍历查找。遍历自然意味着低效。
这是和计算机内存的先天不足有关的：它只能由地址找到对应内容，却不能由内容找到对应地址。
为了提高算法速度，当然应尽量避免算法执行过程中出现这样的情况。比如，如果算法只需要由字符得到对应地址，就不能用 位置－－>字符 的形式存储了，要换成 字符－－>位置，这就是散列表了。如果需要，还可以构造 位置<－－>字符 的形式，那样数据结构会更复杂。
可见，信息的组织形式就是在内存中，信息所包含的各量之间的可访问关系。
有一点是不能忽略的，那就是信息最初输入计算机的形式未必就是算法的最适结构，因此需先把这种结构转换成最适合算法的结构，这个转换正是过程存储的过程。
 

3 计算冗余
 
下面我们只考虑数值计算中的情况。
且看这一段代码：
 
a++
a--
 
恐怕天下没比这更弱智的代码了吧？可它确实是代表了一类的影响因素，也就是我们要称之为计算冗余的东西。
看这个函数：
 
f（x）＝5x－3x
 
我们可以马上写出两种计算它的算法，一个按部就班的算（算法a）而另一个直接算2x的值（算法b）。然而二者在运行时间上是有不小差异的，影响二者运行时间的因素，正是计算冗余。
对算法a，如果用一个变量Y来存储结果的话，它是先被循环加x加5次，再被循环减x减3次，中间经过了先增大后减小的过程；而对算法b，却只是个增大的过程。它可以看成是a中增大x和减小x一对操作互相抵消的结果。
显然，计算冗余是由一对效果相反的操作同时出现在算法中造成的不必要的计算。但是否算法只要出现了相反操作就意味着还可以化简呢？显然不是，比如这个函数：
 
g（x，y）＝1+x-y
 
直接计算它的算法我们可以马上写出来，计算中必然会出现相反的操作，但是它已经是最简单的形式了，我们不可能靠抵消相反操作来化简它。
这二者的区别其实在于：前者计算中的一对相反操作（增大x和减小x）所进行的次数（5次和3次）是不决定于输入变量的，是仅靠算法本身就能确定的，它是算法本身所具有的一个属性，故我们可以依据它来进行算法的化简；而对于后者，一对相反操作（加1和减1）的次数（y次和z次）是不决定于算法本身的，它随着输入变量不同的值而改变，因而是不可化简的。
我们可作如下总结：
一个算法中若出现了效果相反的操作且二者的次数都不是由输入变量决定的，那这个算法可以用抵消的方法化简。
虽然是在数值计算的实例中推出来的，可这个思想并不只适用于数值计算，它应该是对任何数据类型都有效的。
 
4 信息利用
先看这个问题：
折半查找的高效来自何处？
显然这里不关过程存储的事，必然是其他因素的缘故。
它的高效是因为利用了输入字串的有序。从信息的角度看，我们编写算法时并非对输入信息是一无所知的，它至少包含这一点，即：字串是有序的，且该序是由小到大（或反之）的。
这就是编程者对信息的利用充分与否的问题了。设计程序前必然会掌握关于该程序的一系列信息，主要包括输入数据的相关信息和功能描述。功能描述决定了程序的功能（或者说它所实现的函数），而数据相关信息则是预先知道的程序输入（函数定义域）信息的特征的描述。
类似的例子在实际应用中是很常见的，比如统计关键词被搜索的频率来调整算法，优先搜索频率高者。

算法设计与分析
 


 
目录
 
算法设计与分析
前言
第一章 算法基础
1.1 算法概述
1.2 算法分析
1.3 算法复杂度
1.4 渐近表示法
   
第二章 分治法
 

 
前言
 
    通过学习掌握算法设计的主要方法，对算法的时、空复杂性有正确分析的能力，能够针对具体的应用问题选择合适的数据结构并设计结构清晰、正确有效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。
 
第一章 算法基础
 
1.1 算法概述
 
1.什么是算法？
     算法(algorithm):算法是对特定问题求解步骤的描述，是指令的有限序列。就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
 2.算法的五个特征
 
输入：算法有零个或多个输入量；
输出：算法至少产生一个输出量；
确定性：算法的每一条指令都有确切的定义，没有二义性；
可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；
有穷性：算法必须执行有限步之后终止。
 
3.问题和问题求解
     问题求解：寻找一种方法来实现目标。
     问题求解过程：人们通过使用问题领域知识来理解和定义问题，并凭借自身的经验和知识求选择和使用适当的问题求解策略、技术和工具，将一个问题描述转换成问题解的过程。
     计算机求解问题的关键之一是寻找一种问题求解策略得到求解问题的算法，从而得到问题的解。
 4.问题求解过程
 
理解问题
设计方案
实现方案
回顾复查
 
1.2 算法分析
 
1.算法问题求解过程
 
 2.算法分类
     精确算法总能保证求得问题的解。
     启发式算法通过使用某种规则、简化或智能猜测来减少问题求解时间。
     对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法。
     如果在算法中需要做出某些随机选择，则称为随机算法。
 3.算法设计
 
计算机的问题求解策略主要指算法设计策略。
如果所求问题符合某种算法设计策略处理问题的特性，就可使用该算法设计策略设计算法、求解问题。
 
4.算法表示
 
算法描述方法
 
自然语言
流程图
伪代码
程序设计语言
使用c/c++语言描述
 
5.算法确认
 
算法确认：确认一个算法是否正确的活动。
算法证明：使用数学方法证明算法的正确性。
程序测试：是指对程序模块或程序总体，输入事先准备好的样本数据（称为测试用例），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求和活动。
 
6.算法分析
 
算法分析：对算法的执行时间和所需空间的估量。（时间复杂度和空间复杂度）
程序的性能测量：使用样本数据，实际测量一个程序所消耗的时间和空间。
 
1.3 算法复杂度
 
1.什么是好的算法
 
    一个好的算法应具备以下4个重要特性：
 
正确性：算法的执行结果应当满足预先规定的功能和性能要求。
简明性：算法要思路清晰、层次分明、容易理解、利于编码和调试。
高效性：算法要有效使用存储空间，并具有高的时间效率。
最优性：算法的执行时间已达到求解该类问题所需时间的下界。
 
    程序健壮性：是指当输入不合法数据时，程序可以做适当处理而不至于引起严重后果。 其含义是：当程序万一遇到意外时，能按某种预定方式作出适当处理。
 
    正确性和健壮性是相互补充的。
 
2.影响程序时间的因素
 
    影响程序运行时间的因素主要有：
 
 
程序所依赖的算法；
 
 
问题规模和输入数据；
 
 
计算机系统性能
 3.算法的时间复杂度
 
 
抽象机模型
     设抽象机提供由m个基本运算组成的运算集O={O1,O2,…,Om}，每个运算都是元运算，（运算亦称演算，数学的基本概念之一，指使的一些计算规则，算术中有加、减、乘、除、乘方、开方六种运算，其中加、减、乘、除是从两个已知数得出第三个数的运算，称为二元运算；乘方、开方是从一个已知数得出另一个数的运算，称为一元运算）。 它们的执行时间是有限常量。设执行第i个运算Oi所需的时间是αi，1≤i≤m。
 一个算法给定一个输入并在抽象机上执行一次，该执行过程表现为执行一个基本运算序列。
 
 
时间复杂度
     算法的时间复杂度是指算法运行所需的时间。
     设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n,I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为βi，1≤i≤m。βi也是n和I的函数，记做βi(n,I)。那么算法A在输入为I时的运行时间是：
 
 
 
最好、最坏和平均时间复杂度：
 
 
最好时间复杂度
 
 
 
最坏时间复杂度
 
 
 
平均时间复杂度（与概率论中的数学期望概念类似，在概率论和统计学中，期望值（或数学期望、或均值，亦简称期望，物理学中称为期待值）是指在一个离散性随机变量试验中每次可能结果的概率乘以其结果的总和。换句话说，期望值是随机试验在同样的机会下重复多次的结果计算出的等同“期望”的平均值。 ）
 
 4.算法分析
 
 
事前分析：在算法实际运行前分析算法的效率。
 
 
事后测试：运行程序来测试一个程序在所输入数据下实际运行的时间。
 
 
程序步：在语法或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。
 
 
实例
 
 5.算法的空间复杂度
 
 
算法的空间复杂度：算法运行所需的存储空间。
 
 
程序运行所需的存储空间包括以下两个部分：
 
 
固定空间需求：这部分空间与所处理数据的大小和个数无关，即与问题实例的特征无关。
 
 
可变空间需求：这部分空间大小与算法在某次执行中处理的特定数据的规模有关。
 
 
1.4 渐近表示法
 
1.大O记号
     定义：设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记做f(n)=O(g(n))，称为大O记号。
     意义：该算法的运行时间 不会超过 g(n)的某个常数倍。 g(n)是该算法运行时间的上界。
 
 
渐进时间复杂度
     使用大O记号及下面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度。
     只要适当选择关键操作，算法的渐近时间复杂度可以由关键操作的执行次数之和来计算。一般地，关键操作的执行次数与问题的规模有关，是n的函数。
 
 
2.Ω 记号
     定义：设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≥cg(n)，则记做f(n)=Ω (g(n))，称为Ω记号。
     意义：该算法至少需要g(n)的某个常数倍大小的时间量。g(n)是该算法运行时间的下界。
 例题1：
 
 例题2：
 
 3.Θ记号
     定义：设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1,c2和n0，使得当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，则记做f(n)=Θ(g(n))，称为Θ记号。
     意义：该算法实际运行时间大约为g(n)的某个常数倍大小的时间量。（有上界也有下界）
 例题1：
 
 4.小o记号
     定义：f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)≠ Ω(g(n))
     意义：该算法的运行时间f(n)的阶比g(n)低。
 
5.算法按时间复杂度分类
 
 
算法按计算时间分类
     渐近时间复杂度有多项式时间限界的算法称做多项式时间算法。
     渐近时间复杂度为指数函数限界的算法称做指数时间算法。
 
 
最常见的多项式时间算法的渐近时间复杂度
     O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n2)＜O(n3)
 
 
最常见的指数时间算法的渐近时间复杂度
      O(2n)＜O(n!)＜O(nn)
 
 
 
第二章 分治法