北航计算机研究生课程算法设计与分析homework1教学提纲.pdf

此文档仅供收集于网络如有侵权请联系网站删除 一已知下列递推式 C(n) = 1 若 n =1 = 2C n/2 + n 1 若 n 2 请由定理 1 导出 C(n) 的非递归表达式并指出其渐进复杂性 k 定理 1设 a,c 为非负整数b,d,x 为非负常数并对于某个非负整数 k, 令 n=c , 则以下递推式 f(n) =d 若 n=1 =af(n/c)+bn x 若 n>=2 的解是 f(n)