Question

算法的一些习题，求高手帮忙解决下。可以告诉我？

一 完成下列关于复杂度的问题
（1）使用定义证明：证明2n=o(n2)
（2）使用master定理求解T(n) = 9T(n/3) +n

二 请举例说明分治算法、动态规划算法、贪心选择算法、回溯算法和分支限界算法在
实际应用中的特点和求解的适用条件。 请详细描述

三 解释LCS问题中 c[i][j]的递归关系的含义：
c[i][j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的长度，
计算c[i][j]可递归地表述如下：
（1）c[i][j]=0 如果i=0或j=0；
（2）c[i][j]= c[i-1][j-1]+1 如果i，j>0，且a[i-1]=b[j-1]；
（3）c[i][j]=max（c[i][j-1]，c[i-1][j]） 如果i，j

Answer 1

如果k不等于i，则交换a[i]和a[k]的值
Temp=a[i]; /把a[i]的值放到一个临时变量里
A[i]=a[k]; //a[k]的值给a[i]
A[k]=temp; //temp的值，也就是原来的a[i]给a[k]

K=i; //原来k等于i
For(j=i+1;j<8;j++)
If(a[k]>a[j])k=j;//在比较之后如果有小于a[k]=a[i]的a[j]那么k=j了，就不等于i了 捣坐聂旧例