算法设计与分析：回顾

算法设计与分析什么是算法—定义输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。算法是解决问题的方法或过程，严格地讲是满足下述性质的指令序列。“Algorithms:acommonlanguagefornature,human,andcomputer.”

—AviWigderson什么是算法—

计数判断一个byte里面有多少个bit的值为1？intCal(intiValue){while(iValue!=0){iReminder=iValue%2;if(iReminder==1)iCount++;iValue=iValue/2;

}returniCount;}如果这个子函数需要调用很多次，内存空间足够，怎样提高性能？如果既想省时间，又想省空间，怎样改进？intiTables[256]={…};iCount=iTables[iValue];HashMapMaps;If(Maps.containsKey(Value)){Count=Maps.get(Value)}else{Maps.put(Value,newInteger(Cal(iValue)))}什么是算法—最大和连续子数列问题描述:

给定一个整数数列{A1,A2,…,An}，求Ai+Ai+1+…+Aj-1+Aj的最大值，并确定对应的子序列。如果所有的整数都是负数，那么最大连续子数列和为0。例如:{1,

-3,4,5}的最大子数列为{4,5}，因为4+5最大；{3,4,-5,8,-4}的最大子数列为{3,4,-5,8}，因为3+4-5+8最大为10；{4,3,-1,2}的最大子数列为{4,3,-1,2}，因为4+3-1+2最大为8。课程内容算法复杂性枚举策略递归与分治动态规划贪心算法搜索技术时间复杂度分析

枚举算法确定枚举对象

枚举对象也可以理解为是问题解的表达形式，一般需要用若干参数来描述参数之间需要相互独立，而且参数数目越少，问题解的搜索空间的维度也相应地小；每个参数的取值范围越小，问题解的搜索空间也越小。逐一列举可能解根据枚举对象的参数构造循环，一一列举其表达式的每一种取值情况逐一验证可能解根据问题解的要求，一一验证枚举对象表达式的每一个取值，如果满足条件，则采纳它，否则，抛弃之大道至简百钱百鸡、二分枚举分治策略分治法所能解决的问题特征：该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的divide-and-conquer(P){

if(|P|<=n0)adhoc(P);

//解决小规模的问题

dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题

for

(i=1;i<=k;i++)

yi=divide-and-conquer(Pi);//递归的解各子问题

returnmerge(y1,...,yk);

//将各子问题的解合并为原问题的解}治众如治寡，分数是也！合并排序、快速排序、二分查找动态规划分析最优解的性质，并刻划其最优子结构特征确定状态表示S(x1,x2,…)和状态转移方程，递归地定义最优值确定状态转移顺序，以自底向上的方式计算出最优值根据计算最优值时得到的信息，构造最优解前事不忘，后事之师矩阵连乘、多段图最短路径、最长公共子序列算法篇－贪心算法活动安排问题、哈夫曼编码，最小生成树贪心算法的三个逻辑步骤：分解

将原问题求解过程划分为连续的若干个决策阶段决策

在每一个阶段依据贪心策略进行局部贪心决策，并缩小待求解问题的规模合并

将各个阶段的局部解合并为原问题的一个全局可行解贪心算法也是一种基于子问题思想的策略。贪心算法是一个分阶段决策过程，在每个局部阶段，贪心法都做出一个当前最优的局部决策，并期望通过每次所做的局部最优决策产生一个全局最优解。盲人爬山算法篇－搜索策略搜索算法的两个逻辑步骤：定义问题的解空间搜索解空间，并在搜索过程中用剪枝策略避免无效搜索搜索算法是一种通用的问题求解方法：首先把问题表示转换为一个状态空间图，然后设计特定的图遍历方法在状态空间中搜索问题的解

基于枚举策略的搜索深度优先搜索广度优先搜索

优化+枚举的搜索回溯算法=深度优先搜索+剪枝策略分支限界算法=广度优先搜索+剪枝策略

启发式搜索，启发式搜索是一种基于规则的优化搜索算法优化枚举，提前判定人生如算法有人善“分治”再多再大的难题也如庖丁解牛