首页 > 代码库 > 常见算法问题的分类

常见算法问题的分类

一.递归算法

递归算法:是一个直接或间接调用自身的过程,但每次调用问题的规模都会减少,最终得以问题解决的过程。

递归算法的思想来源于分治法。

分治法:把一个难以解决的大问题分为若干规模较小的相同问题,以便各个击破,分而治之。

常见的递归算法,如:

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个箱子中(决策问题)。

哈密顿路:一个无向图中,哈密顿路是一个简单路径,他包含所有的结点,并且经过每个结点有且只有一次。

常见算法问题的分类