1题 从 find 和sreach操作看出 有序无序列表对查找操作来说并无太大区别,都是蛮力搜索。 重点: 循秩访问与循位置访问的区别
2.题 3题 特殊情况考虑 对空列表插入,以及列表删除为空列表 重点: 程序的鲁棒性
4 题 对 deduplicate操作的考察 4.1 证明其不变形 ( + 单调性 == 正确性 ) 4.2 证明其复杂度下界与上界 4.3 优化算法 4.4 归约
5题 考察对遍历函数的编写
6题 扩展题,在实际运用中的观测得出的自适应式列表, 可参考 伸展树 (方法, 每当被访问到当前元素 就将其放到列表的首部)
7题 阅读 STL代码 解析源码题 ( 学渣留下了当初不学无术的泪。。。。。。 )
8题10题 11题 12题 排序算法之 插入排序 8题 实现 8.1 编写代码,并分析 8.2 判断算法的稳定性 10题 平均分析 (大前提 列表中 n 个元素 独立均匀的随机分布) 10.1 比较操作的平均情况分析 10.2 移动操作的平均情况分析 10.3 最好情况出现的概率分析 11题 输入敏感性判断 11.1在数据具有特殊性的情况下,插入排序的时间复杂度变化 11.2接着上题的讨论,当 k 为常数时,分析出插入排序的下界居然是 O(N) (波动太大) 11.3逆序对 的引入,及其与插入和比较操作之间的关系 (影响插入排序的注意因素) 11.4证明出插入排序真正的时间复杂度为 O(N + I) 12题 通过实例来验证插入排序复杂度O( N + I)的正确性
9题 13题 14题 15题 排序算法之 选择排序 9题 实现 9.1 编写代码,并分析 9.2 判断算法的稳定性 13题 针对列表而言, 需要进行动态内存分配,造成某些操作的效率降低 (不同操作之间 单位时间的差异性) 13.1 对其进行改进 13.2 实践去检验 14题 算法优化问题 14.1 针对一实例进行讨论可优化的情况出现的次数,感性的认识 知识点:循环节的引入 14.2 理想严谨的去证明 在符合独立均匀分布的情况下,“优化情况”出现的概率 重点: 所谓的优化,一定要有理有据 15题 稳定性的讨论 深入了解稳定性的概念
16题 17题 排序算法之 归并排序 16题 分析归并的拆分 (重点啊 !! 考过啊!!) 16.1 将拆分从倍数改成常数 算法时间复杂度将上升至 O(N ^ 2) 16.2 极端情况下 C = 1, 算法退化至插入排序 ! (极限法思考问题一直是个很好的方法,更加突出问题的本质,摒弃不重要的细节) (扩展: 若是改成其他的倍数比例划分呢? 甚至是更多段数呢) 17题 稳定性分析
(注意 插入排序, 选择排序 和归并排序, 列表的实现方式与向量的不同之处和相同之处)
18题 倒置函数的实现 三种实现方式 注意: 第二个代码用到了 (NULL)
19题 约瑟夫问题 19.1实现 19.2计算复杂度分析