算法基础（第5版）——1.6　习题

1.1节 1. 编写一个算法，在一个包含n个数字的列表（数组）中找出最大数。 2. 编写一个算法，在一个包含n个数字的列表中找出最小数。 3. 有一个包含n个元素的集合，其元素存储在一个列表中。编写一个算法，以该列表为输入，输出该集合的所有三元素子集。 4. 编写一个“插入排序”算法（插入排序在7.2节讨论），使用二分查找法找出下一个插入位置。 5. 编写一个算法，计算两个整数的最大公约数。 6. 编写一个算法，在一个包含n个数字的列表中找出最大数和最小数。尝试找出一种方法，对数组项进行的比较次数不超过1.5n次。 7. 编写一个算法，确定一个准完全二叉树是否是一个堆。 1.2节 8. 当需要查找操作时，在什么情况下不适合采用顺序查找（算法1.1）？ 9. 给出一个实际例子，你不会在其中应用交换排序（算法1.3）来完成排序任务。 1.3节 10. 为习题1到习题7中的算法定义基本运算，并研究这些算法的性能。若某一给定算法存在所有情况时间复杂度，则计算该复杂度。若不存在，则计算最差情况时间复杂度。 11. 为基本“插入排序”和习题4中给出的版本（它使用了二分查找）确定最差情况、平均情况和最佳情况时间复杂度。 12. 编写一个Θ(n)算法，对n个互不相同的整数排序，这些整数的大小范围为1至kn（含），其中k是一个正整数常量。（提示：使用一个包含kn个元素的数组。） 13. 算法A执行10n2次基本运算，而算法B执行300 lnn次基本运算，从哪个n值开始，算法B开始呈现其较佳性能？ 14. 对于一个输入规模为n的问题，有Alg1和Alg2两种算法。Alg1的运行需要n2微秒，Alg2的运行需要100nlogn微秒。Alg1的实现需要占用4小时的程序员时间，占用2分钟的CPU时间。而Alg2则需要15小时的程序员时间，6分钟的CPU时间。如果程序员的报酬标准是20美元/小时，CPU为50美元/分钟，要使用Alg2解决一个规模为500的问题实例，必须应用多少次后才能证明其开发成本的正当性。 1.4节 15. 直接证明：f(n)=n2+3n3 Θ(n3)。即，使用O和Ω的定义来证明f(n)同时属于O(n3)和Ω(n3)。 16. 利用O和Ω的定义证明：6n2+20n O(n3)，但6n2+20n Ω(n3)。 17. 利用1.4.2节给出的阶的性质，证明：5n5+4n4+6n3+2n2+n+7 Θ(n5)。 18. 设 ，其中ak>0。利用1.4.2节给出的阶的性质，证明p(n) Θ(nk)。 19. 函数f(x)=3n2+10nlogn+1000n+4logn+9999，属于下面哪个复杂度类别： (a) θ(lgn) (b) θ(n2logn) (c) θ(n) (d) θ(nlgn) (e) θ(n2) (f) 都不是 20. 函数f(x)=(logn)2+2n+4n+logn+50属于下面哪个复杂度类别： (a) θ(lgn) (b) θ((logn)2) (c) θ(n) (d) θ(nlgn) (e) θ(n(lgn)2) (f) 都不是 21. 函数f(x)=n+n2+2n+n4属于下面哪个复杂度类别： (a) θ(n) (b) θ(n2) (c) θ(n3) (d) θ(nlgn) (e) θ(n4) (f) 都不是 22. 按复杂度类别为以下函数分组： nlnn (lgn)2 5n2+7n n5/2 n! 2n! 4n nn nn+ln n 5lgn lg(n!) (lgn)! en 8n+12 10n+n20 23. 证明1.4.2节“阶的性质”中的性质1、2、6、7。 24. 讨论渐近比较（O、Ω、Θ、o）的反射性、对称性和传递性。 25. 假定有一台计算机，需要1分钟的时间解决一个规模n=1000的问题实例。假定又购买了一台新计算机，其速度是原计算机的1000倍。假定所用算法具有下面的时间复杂度T(n)，在1分钟内可以解决何种规模的实例？ (a) T(n) = n (b) T(n) = n3 (c) T(n) = 10n 26. 推导定理1.3的证明过程。 27. 证明以下陈述的正确性。 (a) lgn O(n) (b) n O(nlgn) (c) nlgn O(n2) (d) 2n Ω(5lnn) (e) lg3n o(n0.5) 补充习题 28. 目前，使用算法A可以在1分钟中解决规模为30的问题实例，此算法属于Θ(2n)算法。而我们很快就得在1分钟内解决两倍规模的问题实例。你认为购买一台更快（也更贵）的计算机是否会有帮助。 29. 考虑以下算法： for (i = 1; i <= 1.5n; i++) cout << i; for (i = n; i >= 1; i--) cout << i; (a) 当n=2，n=4，n=6时的输出结果是什么？ (b) 时间复杂度T(n)是什么？可以假定规模n可被2整除。 30. 考虑以下算法： j = 1; while (j <= n/2) { i = 1; while (i <= j) { cout << j << i; i++; } j++; } (a) 当n=6，n=8，n=10时的输出结果是什么？ (b) 时间复杂度T(n)是什么？可以假定规模n可被2整除。 31. 考虑以下算法： for (i = 2; i <= n; i++) { for (j = 0; j <= n) { cout << i << j; j = j + ⌊n/4⌋; } } (a) 当n=4，n=16，n=32时的输出结果是什么？ (b) 时间复杂度T(n)是什么？可以假定规模n可被4整除。 32. 下面嵌套循环的时间复杂度T(n)是什么？为简单起见，可以假定n是2的幂。也就是说，存在某一正整数k，使得n= 2k。 for (i = 1; i <= n; i++){ j = n; while (j >= 1){ < While循环体> // 需要 (1) j = ⌊j/2⌋; } } 33. 为以下问题给出一种算法，并确定其时间复杂度。给定一个由n个不同正整数组成的列表，将该列表分为两个大小均为n/2的子列表，使两个子列表中的整数和之差最大。可以假定n是2的倍数。 34. 下面嵌套循环的时间复杂度是什么？为简单起见，可以假定n是2的幂。也就是说，对于某一正整数k，有n=2k。 i = n; while (i >= 1){ j = i; while (j <= n){ <while循环体> // 需要 (1) j = 2 * j; } i = ⌊i/2⌋; } 35. 考虑以下算法： int add_them (int n, int A[]) { index i, j, k; j = 0; for (i = 1; i <= n; i++) j = j+A[i]; k = 1; for (i =1; i <= n; i++) k = k + k; return j + k; } (a) 若n=5，且数组A包含2、5、3、7、8，输出为多少？ (b) 该算法的时间复杂度T(n)为多少？ (c) 尝试提高该算法的效率。 36. 考虑以下算法： int any_equal (int n, int A[][]) { index i, j, k, m; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) for (k =1; k <= n; k++) for (m = 1; m <= n; m++) if (A[i][j]==A[k][m] && !(i==k && j==m)) return 1; return 0; } (a) 该算法的最佳情况时间复杂度为多少（假定n>1）? (b) 该算法的最差情况时间复杂度为多少？ (c) 尝试提高该算法的效率。 (d) 若该算法返回0，数组A的哪种性质得以保持？ (e) 若该算法返回1，数组A的哪种性质得以保持？ 37. 给定一个Θ(lgn)算法，计算当xn除以p时的余数。为简单起见，可以假设n是2的幂。也就是说，对于某一正整数k，有n=2k。 38. 用日常语言解释，以下集合中有哪些函数。 (a) (b) (c) 39. 证明函数f(n)=|n2sin n|既不属于O(n)，也不属于Ω(n)。 40. 假定f(n)和g(n)是渐近正函数，论证以下表述的正确性。 (a) f(n)+g(n) O(max (f(n)), g(n)) (b) f2(n) Ω(f(n)) (c) f(n)+o(f(n)) Θ(f(n))，其中o(f(n))表示任意属于o(f(n))的函数g(n) 41. 给出下面问题的一个算法。给定一个由n个不同正整数组成的列表，将该列表分为两个大小均为n/2的子列表，使两个子列表中的整数和之差最小。计算该算法的时间复杂度。可以假定n是2的倍数。 42. 算法1.7（斐波那契序列的第n项，迭代）关于n显然是线性的，但它是一种线性时间算法吗？1.3.1节将输入规模定义为输入的大小。在第n个斐波那契项的例子中，n是输入，可以将用于对n编码的比特数用作输入规模。利用这一度量，64的规模为lg64=6，1024的规模为lg1024=10。证明，算法1.7根据输入规模属于指数时间算法。进一步证明，任何计算第n个斐波那契项的算法都必然是一种指数时间算法，因为输出的大小是输入规模的指数。（关于输入规模的相关讨论，请参阅9.2节。） 43. 确定算法1.6（斐波那契序列的第n项，递归）关于其输入规模的时间复杂度（见习题34）。 44. 能否验证习题1~7所得算法的正确性？