chapter02
复制本地路径 | 在线编辑
1. 平均时间复杂度和分摊复杂度之间的区别，是否有蕴含关系?
2. 数组Copy的一个Trick，什么时候从前往后，什么时候从后往前?
3. 数组expand扩张算法的时间复杂度分析
4. 数组shrink缩减算法的时间复杂度分析
5. 分摊复杂度习题：二进制变量反转次数估计
6. 数组permute置乱算法的3个证明
6.1 正确性证明，可以生成所有排列
6.2 各元素处于任一位置为1/n
6.3 各排列的产生概率为1/n!
7. 说明permute不可以采用C语言的rand来实现全排列，以及为什么?
8. 无序数组的find算法：研究最好情况的复杂度
9. 无需数组的insert算法：时间复杂度分析
10. 无序数组的remove算法：采用什么样的顺序来移动各个元素
11. 无序数组的deduplicate算法
11.1 为什么要删除的是当前元素而不是前缀里面的那个雷同者
11.2 分析其复杂度为O(n^2)
11.3 改进步骤1，复杂度仍是O(n^2)，指出改进究竟改进在哪
11.4 改进步骤2，复杂度变为O(nlogn)
11.5 证明最低复杂度即为O(nlogn)
13. C++如何通过函数对象和函数进行传值?
15. CBA算法例题：对4个数字进行排序
15.1 证明最坏次数不少于5次
15.2 设计一种CBA，最坏次数至多5次
37. CBA算法例题：对三个元素进行比较
37.1 证明最坏次数不多于3次
37.2 证明最坏次数不少于3次
39. CBA算法例题：已经对10个数排好序，现在又来2个，最坏至少几次?
38. CBA算法推广：代数判定树，利用这种树要注意每个节点复杂度不一定是常数
16. 二分查找版本C的分析：说明mi不会超出[lo,hi)
18. 二分查找和斐波那契查找的分析
18.1 成功查找长度分析
18.2 失败查找长度分析(习题第20题)
18.2 失败查找长度和成功查找长度的关系
18.3 证明斐波那契查找是这种查找方式最好的实现
21. 指数查找，即找出A[k]<= x <= A[min(n-1,k^2)]，复杂度O(loglogk)
22. 马鞍查找，复杂度O(r+s+logn)，以及其什么时候不适用了
23. 测试鸡蛋硬度，1个，2个，d个
25. 起泡排序的改进
25.1 A[0,sqrt(n)]是无序的，改进措施
25.2 A[n-sqrt(n),n]是无序的，改进措施
25.1 A[m,m+sqrt(n)]是无序的，改进措施
26. 归并排序的研究
26.1 根据递推公式求出复杂度
26.2 改进步骤1：如何在子序列有序的情况下及时停止
26.3 改进步骤2：如何减少new和delete辅助空间的次数
26.4 改进步骤3：如何在第一个子序列已经全部放入大序列时进行停止
26.5 瞎改：什么时候会瞎改造成稳定性破坏
34. Bitmap的研究
34.1 普通版本下，如何进行set,clear,test，关键是如何利用位运算
34.2 改进版本，可以取消init操作，此时如何实现set,clear,test
34.3 改进版本和普通版本的区别(主要在于空间上面的不同)
36. 利用Bitmap快速找到某个范围内的所有素数
40. 算法题：n个数字找出最大和次大，一般的比较次数为(n-1)+(n-2)，进行改进，并分析比较次数上限
41. 证明题训练：矩阵M，先对列进行排序，然后对行进行排序，证明此时各个列仍然有序