首页 > 代码库 > 常见算法问题的分类
常见算法问题的分类
一.递归算法
递归算法:是一个直接或间接调用自身的过程,但每次调用问题的规模都会减少,最终得以问题解决的过程。
递归算法的思想来源于分治法。
分治法:把一个难以解决的大问题分为若干规模较小的相同问题,以便各个击破,分而治之。
常见的递归算法,如:
int fun(int n) { if(n==0||n==1) return 1; else return n*fun(n-1); }
二.排序算法
可以参考之前的博客:
http://blog.csdn.net/qzp1991/article/details/42002063
三.动态规划
常见的问题有,矩阵相乘的序问题,最优二叉树的构建问题。
四.字符串匹配问题
二种算法
KMP算法:http://blog.csdn.net/qzp1991/article/details/42660437
BM算法:http://blog.csdn.net/qzp1991/article/details/42663969
五.NP问题
它是一种问题可以在多项式时间内得以解决,这类问题至今尚未研究出合理的快速算法。
如
背包问题:给出N个尺寸的物品S1,S2...Sn和容量为C的背包,能否找到n个物品使其尽量填满背包。
装箱问题:设无数只箱子,每只箱子的容量为1,有n个物品,每个物品的体积为s1,s2...sn(sn<1),求容纳这些物品的最小箱子数(优化问题)或者给定正整数k,能否把这些物品放入这k个箱子中(决策问题)。
哈密顿路:一个无向图中,哈密顿路是一个简单路径,他包含所有的结点,并且经过每个结点有且只有一次。
常见算法问题的分类
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。