算法概述
算法四个性质:输入、输出、确定性、有限性
算法的时间复杂性T、空间复杂性S
其中I是问题的规模为n的实例,p(I)是实 例I出现的概率。可操作性最好且最有实际价值的是最坏情况下的时间复杂性,
时间复杂度排序:
渐近分析:渐近上界记号O – 给出函数f****的一个上限
O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n³ n0有:0 £ f(n) £ cg(n) }
例:考察f(n) = 3n+2
当n>=2时,3n+2 <= 3n+n = 4n,所以f(n) = O(n),f(n)是一个线性变化的函数。类似地,100n+6 = O(n)。
特别的,当f(n)是一个常数c时,如f(n)=9,可记为f(n) = O(1)
渐进上界就是最差情况下的算法复杂度,下界十最好的情况下的复杂度,非紧上界是确定一个较为模糊的上界,即不会超过这个增长规模,非紧下界同理。
紧渐进界是指函数的上界和下界同时存在,且它们之间存在一个常数因子。在算法分析中,我们常常用渐进符号来表示算法的时间复杂度。当算法的时间复杂度存在上界和下界,并且它们具有相同的增长趋势时,我们可以说该算法具有紧渐进界。
递归与分治
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
最优子结构:该问题可以分解为若干个规模较小的相同问题
该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题(这条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好)。
人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。
void LCSLength(int m,int n,char *x,char *y,int **c,int **b)
{
int i,j;
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]=2;}
else { c[i][j]=c[i][j-1]; b[i][j]=3; }
}
}