算法设计分析基础

 当实际问题转化成计算机可解模型时，需要对具体问题进行分析，确定目标近似或精确解，选择采用相应的数据结构，设计相应的处理算法来，最终将可实现的算法用程序进行实现。而对于设计的算法需要进行正确性证明，效能评估，必要时根据实际情况进行时空的转换，以达到满足需求的目的。简单梳理下效率评估及算法证明的方式方法。常常一个好的算法需要反复努力修正，而不同的算法对于处理不同数据量的同一问题时可以效率、复杂度也不相同。 一、算法的复杂度 算法的复杂度包括时间、空间两类，有时需要考虑最坏情况、平摊情况等等。其表示方式O、theta、omega等： --O表示上限接近某函数的常数倍；与小o差别，大O只考虑上限，小o表示逼近？ --omega表示下界为某函数的常数倍； --theta表示上下界都为某函数的常数倍； 基本渐进效率的类型：常量、对数、线性、n-log-n、平方、立方、指数、阶乘 二、证明方法 1、直接证明 2、间接证明：使用其逆否命题来证明 3、反正法:假设结论错误 4、反例证明法 5、数学归纳法 三、鸽巢原理 如果把n球放置在m各盒子中，那么：存在一个盒子必定至少装ceil(n/m)个球；存在一个盒子必定至多装floor(n/m)个球； 四、算法的分类 算法的分类总结往往可以根据算法类型来确定其在各种问题中的应用，或是根据不同的问题分类，看看每类问题可以采用哪种方式来解决。 1、常见的需要解决的问题类型 排序、查找、串处理、图问题、组合问题、几何问题、数值问题 2、按照递归性：可分为递归性问题、非递归性问题 3、按照复杂性及处理能力分 4、按照处理思想分：蛮力法、分治法、减治法、变治法、贪婪法、动态规划、回溯法、分支界限 --蛮力法：选择/冒泡排序、顺序查找、蛮力字符串查找、穷举法；直接根据问题的描述和所涉及的定义； --分治法：合并排序、折半查找、快速排序、二叉树遍历 --减治法：可以是减去一个常量、减常因子或是可变规模的问题：插入排序、拓扑排序、深度/广度优先查找；减去一个常量，常数因子或者减去规模可变； --变治法：通过实例简化、改变表现或问题化简得方式处理问题；预排序：如检验数字的唯一性，只需要将数字排序，判断是否存在连续两个数字的相同即可；高斯消去法解线性方程；平衡查找树... ...线性规划用来解决决策最优化问题； --贪婪法：Huffman、prim、kruskal、Dijkstra(求单起点到终点的最短路径) --动态规划：一种使多阶段决策过程最优的方法，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解；floyd算法(计算每个定点到其他定点的最短距离)； (困难问题解法：) --回溯法：穷举法的更聪明的变种，主要思想：每次构造一个分量，评估这个分量的构造解，如果不满足条件，则对另外的分量进行评估。过程可以构造状态空间树：n皇后的问题... ... --分支界限法：分支界限法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树，它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索； --随机算法：接收输入的同时，为了随机选择的目的，还接收一串随机比特流，在运行过程中使用此流；如随即排序(随机比较参数值）; --近似算法：获取近似最优解得合理的解，贪心启示法，近似法/贪婪法比较难以证明正确性； --迭代改进：从最简单的解开始(往往是贪心算法)，然后对这个解在各个阶段进行改进，从而找到最优解。 五、时空权衡转换 1、计数排序：计算比自身大小的数值个数形成index排序，实际中数据量不同占用空间不同； 2、散列法：采用散列函数的搜索时间优化； 3、B树：B索引树的块查找 4、串匹配增强技术，优化方法； 六、P、NP和NP完全问题 大O能在多项式时间内求解的问题成为易解的，否则成为难解的； P问题：用确定的算法在多项式内时间内能够判定的问题，也叫多项式类型； NP问题：一类可以用不确定多项式算法求解的问题，称为不确定多项式类； NP完全问题：一个判定问题为NP完全问题条件：属于NP类型；NP中的任何问题都可以在多项式时间内简化此问题； co-NP问题：问题的补类是完全问题的问题； NPI类：如果问题和它的补类都是NP完全的； 关于单项式与多项式： 单项式的定义：数字与字母的积的代数式叫做单项式，单独的一个数或一个字母也叫单项式； 多项式:若干个单项式的和组成的式叫做多项式，多项式中每个单项式叫做多项式的项,这些单项式中的最高次数,就是这个多项式的次数.不含字母的项叫做常数项