常见算法问题的分类
浏览数：16 /
时间：2015年06月08日
一.递归算法
递归算法：是一个直接或间接调用自身的过程，但每次调用问题的规模都会减少，最终得以问题解决的过程。
递归算法的思想来源于分治法。
分治法：把一个难以解决的大问题分为若干规模较小的相同问题，以便各个击破，分而治之。
常见的递归算法，如：
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个箱子中(决策问题)。
哈密顿路：一个无向图中，哈密顿路是一个简单路径，他包含所有的结点，并且经过每个结点有且只有一次。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
