作业-算法11-14s答设计目是为了花费更少代价来得到某一问题解以位二

n位二X*Y为例。当以传统的方法求乘积时，YX所有位，易知其时间复杂度为O(n2。当使用Divide-and-Conquer方法之后，mn。m%nnm，rn，再进行①操作。int(m,n)whileifreturn（1）初始：r=∞，m，n是待求最大公约数的原始正整数；循环：进行一次模运算，r≠0数，那么循环体的倒数第二次执行得到的r值为1，那么接下来的最后一r0，随机循环终止。假设用辗转相除法求自然数a和b（a> b> 0）的最大公约数需要N步，那么满足这一条件的a和b的最小值是分别是斐波那契数FN+2和FN+1。[94]这可以用数学归纳法证明。[95]假设N= 1，b整除a，满足这一条件的a和b最小是b= 1、a= 2，正是F2和F3。现在假设这一规律对M−1有效。一个需要M步的算法的第一步是a= q0b+ r0，第二步是b=q1r0 算法是递归的，它需要M−1步才能算出(b, r0)，其中b和r0的最小 FM。所以a的最小值是当q0 1的时候，此时a= b+ +FM F。 φ倍。[97]因为如果算法需要N步，那么b一定大于或等于F，也就是一定大于或等于φN−1，其中φ是黄金分割比因为b≥ φN−1，所以N− logb。因为log10φ> 1/5，(N−1)/5 log10φlogφb=log10bφN≤ b在十进制下的位数。①while“j>0A[j]>key”j是递减的，i>n循环：设A[1,2,…,i-1]来自输入且是有序。进入内部while循环，循环变量j由i-1开始递减向前查看已经有序的数组A[1,2,…,i-1]以寻找一个合适的位置将keyA[1,2,…,i]。A[1,2,…,n]。①情况：数组A初始时数组元素是按照由大到小有序排比较次数：n23 ②A比较次数n(n12n③

比较次数：n1(22h(n)=θ(f(n)),k(n)=θ(g(n))h(nk(nθ(f(n∃c1c2>0，n0，对∀n>n0，c1f(n)≤h(n)≤c2∃c3c4>0，n1，对∀nn1，c3g(n)≤k(n)≤c4g(n)可得到，c1f(n)+c3g(n)≤h(n)+k(n)≤c2f(n)+c4g(n)c5=min{c1,c3},c6=max{c2,c4},n2=max{n0,n1},>再由定义可知，h(nk(nθ(f(n)θ(g(n))

∃c1>0，n1，对∀n>即，∃(1/c1)>0，n1，对∀n>∃c2>0，n2，对∀n>即，∃(1/c2)>0，n2，对∀n>综上，f(n)=O(g(n))

klimk

1lnnlim(logn)k必达lim(

)klim(kln2)k

11k

所以：logkn

n!

n

n()log(n()

n() ( 22n(nnelimlog(n!)

lim nnlog

1lim lim(log(2)2 1)

log(n!)(nlog①由条件易知Hr(n)②nkHr(n)kk数列可函数化为f(x)n1n

f(x)dx

n1rnk2k n

n1 1 rn 由于r

01r r1

1n

1 r

rk则1kk

r1

(n)

r左右两边都是常数，所以可得Hr(n)=n2log(n+k)-log(n)≥1k的值最2.log(n1)lognlogn1log(11 0log(11)nlog(n)=a，alog(n+1)的结果一定在(a,a+1)内log(n+1)=a，alog(n)的结果一定在(a-1,a)内log(n)log(n+1)n，n+1是连续的正整数，那么两个a b1 aab1a(b

a b1 aab1a(b

2 (n1ilogn)

nlog=2lognT(1)nlog2nlog4 nlognn(12 log2n[logn(logn1)2]nlog2nnlognn O(nlog2a5，b3，fnnnlogbanlog35n146f(n)f(n)多项式小于nlogba，由Master定理知T(n)(n146a4，b2，fnnnlogbanlog24n2f(n)f(n)多项式小于nlogba，由Master定理知T(n)(n2

1a2，b2，fnn2nlogbanlog22nff(n)多项式大于nlogba，由Master定理知T(n)log4353

5log4 3( 3T(n)()inn

log4

1 4n() 45log 4

4no(n2

34a2，b2，fnnlogbanlog22n

ff