- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
这是因为：考察 lim (㏒ 2n+√n+㏒㏒ n)/√n, 用洛必达法则，分子分 n→∞
母同时求导，得
lim （2 ㏒ n/n + n-1/2/2 + 1/n ㏒ n）/( n-1/2/2), 分子分母同时乘 n,得 n→∞
lim （2 ㏒ n + n1/2/2 + 1/㏒ n）/( n1/2/2).再用洛必达法则，得 n→∞
lim （2/n + n-1/2/4 - ㏒ n-2/n）/( n-1/2/4), 分子分母同时乘 n,得 n→∞
lim （2 + n1/2/4 - ㏒ n-2）/ n1/2/4. 当 n 无限增大时㏒ n-2/ n1/2/4=０, n→∞
忽略不计,因此 lim (2 + n1/2/4 - ㏒ n-2)/ n1/2/4=1>0, n→∞
根据定义 1.4 可知, 原式=Θ(√n).
(d) n!/ 2n + n n = Θ(n n )
1 3 4 5 10 11 12 15
2 6 7 8 9 13 14 16
1 5 11 12
3 4 10 15 2 7 9 16 6 8 13 14
11 12 1 5 15 3 4 10 2 7 9 16 8 14 6 13
1.15 用Θ表示函数。
(b)
（c）㏒ 2n+Fra Baidu bibliotekn+㏒㏒ n
(c) 解：log²n+ n +loglogn=Ө(log²n)
1.15 练习
1.1（a）
1)A[1…60] = 11 12 13 … 68 69 70 A[(1+60)/2]=A[30]=40 由于 33<40，舍弃 A[30…60];
2)A[1…29] =
11 12 13 … 37 38 39
A[(1+29)/2]=A[15]=25
由于 33>25，舍弃 A[1…15];
3) A[16…29]=
26 27 28 … 37 38 39
A[(16+29)/2]=A[22]=32
由于 33>32，舍弃 A[16…22];
4) A[23…29] =
33 34 35 36 37 38 39
A[(23+29)/2]=A[26]=36
由于 33<36，舍弃 A[26…29];
5) A[23…25] = 33 34 35
A[(23+25)/2]=A[24]=34; 由于 33<34，舍弃 A[24, 25];
6) A[23] = 33
由于 33=33，搜索完毕。 综上，搜索 33 共执行了 6 次比较。 同理可得（b）搜索 7 共执行了 5 次比较。
（c）搜索 70 共执行了 6 次比较。 （d）搜索 77 共执行了 6 次比较。 1.10 对 11 12 1 5 15 3 4 10 7 2 16 9 8 14 13 6 用 bottomupsort 算法，按非降序排列。 解：用图示，如下进行。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
