现在的位置: 首页 > 综合 > 正文

做算法题的几个思路

2018年01月26日 ⁄ 综合 ⁄ 共 1064字 ⁄ 字号 评论关闭

算法题目往往比较复杂,要么让人感到无从下手,要么很难给出一个最优解,但这恰恰是考验一个程序员思维方式的有效手段。看到这类的难题不要慌,《算法设计与分析基础》一书比较全面地总结了做算法题目的一些思路:

(1)蛮力穷举法,可以说可以解决所有的问题,不过对于组合数很大的问题时间性能不是很好甚至不能忍受。例子:全排列的生成、n选m组合的生成(这两个的
蛮力法都可以利用多重嵌套循环形成,层次很壮观),8皇后问题(对应成8数全排列),12城tsp问题(对应成12数排列),a的n次方计算就老老实实连
乘n次a,顺序查找元素等都是蛮力穷举的例子。
(2)分治法,就是把1个大问题分成2个小问题,2个小问题还可以再分,直到问题规模小的可以
简单解决。处理每个小问题,把处理结果汇总处理,最后得到整个大问题的解。一般而言,分治法都要用到递归。例子:算n个数的和,可以算前一半n/2的和,
后一半n/2的和,最后相加即得总和;凸包问题,可以把最左边点和最右边点连线,右上边点集的凸包(叫做上包)和下面点集的凸包(叫做下包),最后把上包
和下包合围起来就是整个凸包。点集的最小点对问题,可以以一条线为界,分成左右两个集合,分别求最小点对,最后在合起来处理。分治法对多个处理器或处理机
的并行计算特别适用。
(3)减治法,就是处理过程中问题规模不断减小的方法。最常见的就是折半查找,每次都把n/2个元素删去;减治法一半分
为减1法,减常数法,减可变规模法。减1法典型的就是插入排序,还有计算a的n次方,可以计算a的n-1次方,再变成计算a的n-2次方等等。想查找二叉
树的查找都利用了减治的思想。
(4)变治法,就是对问题进行变相,变化,利用已有的解决方案来解决生疏的问题,重点在于对原来的生疏问题进行转化,转变,使他变成一个已有好的解法的熟悉问题。
(5)时空权衡,考虑时间和空间的相互转化,有时利用空间换时间,有时利用时间换空间,常用的就是  计数排序(多利用了一个计数数组),散列法,B树。
(6)动态规划,也是时空权衡的一种,把可重复的问题的解保存在一个表里面。例子包括   计算二项式系数,最有二叉查找树,背包问题和记忆功能。
(7)贪婪算法,就是每一步都从可选方案中选择对该步最有利的方案,直到问题解决。贪婪法有可能得不到问题的最优解,不过得到的解一般都很接近问题的最优解。它的优点就是效率高,时间复杂性相对有那些得到最优解的算法快很多。常用的例子:
最小生成树的prim算法,kruskal算法,最短路径的dijkstra算法,解决tsp问题。
(8)回溯法
(9)分支限界法

抱歉!评论已关闭.