期末考试复习成绩构成往年题型最耗时间的题型第一次习题课θ、Ω、O求解时间复杂度递归树求解主定理第一次上机第二次习题课习题（第一次习题课遗留）第一次上机补充问题（往年题）第二次上机第二次上机补充题（考试重点）第三次习题课第三次上机补充题第四次习题课代码提交格式第四次上机

期末考试复习

！！各次上机的补充题有极大作用！！

成绩构成

  • 上机+作业+考勤：30%
  • 笔试考试：70%

往年题型

！！近几年增加了对代码的考查，以验证上机是否是自主完成！！
  1. 判断题（往年8个）
      2. 范围广
  1. 递归树求解递推式
    1. 画树（树根画对，树高画左侧，开销画右侧，叶子节点开销都画成T(1)）
    2. 根据所画树，计算递推式（要用到等比等差公式）
    3. 证明递推式（有时会考，解决不了时记得减去一个低价项）
  1. 求解递推式（不限方法，直接写正确答案给满分，但是错了就没过程分，建议保留过程）
    1. 替换法（建议使用）
    2. 主定理法（建议使用，有可能满足的是主定理的推论）
    3. 递归树法（不建议使用）
  1. 排序
    1. 时间复杂度（三种情况）
    2. 空间复杂度
    3. 稳定性
    4. 适用条件
  1. 多种题型不定
    1. 计算题
        • 例：矩阵链乘
        • 可能比较难，若计算量较大，建议最后做
    2. 问答题（解答题）
        • 例：几类算法的相关问题，如思路、步骤等
        • 分治、DP、贪心、回溯。。。
    3. 算法设计题
        • 可参考第二次上机最后一题（往年原题）
        • 写递推式和思路，不要写Code
        • 不要写太多话，老师会找不到重点
        • 不建议写伪代码
        • 丢分点：
          • 把算法设计当成计算题，只是算出了题目的答案
          • 分析清楚再写
    4. 综合题（近几年新题）
      1. 可能几个算法结合起来考
      2. 可能一类算法出好几问

最耗时间的题型

  • 第二题：递归树求解递推式
  • 第五题：计算题

第一次习题课

θ、Ω、O

  • θ：渐近紧致界
  • Ω：渐近下界
  • O：渐近上界
  • O考得比较多

求解时间复杂度

递归树求解

  • 左边要画树高
  • 右边写每一层开销
  • 写叶子层开销
  • 根据题目要求：
      • 若要求写了紧致界：那叶子的开销T(1)可以写为θ(1)
  • 例
      • notion image
    • 解法1
        • notion image
    • 解法2
        • notion image
    • 证明
        • notion image
        notion image

主定理

  • 例
      • notion image
  • 往年原题
      • notion image

第一次上机

notion image
notion image
notion image
notion image
 

第二次习题课

习题（第一次习题课遗留）

  • 第一题
      • notion image
  • 第二题
      • notion image
      notion image

第一次上机补充问题（往年题）

  1. 归并排序在最坏、最好、平均情况下的时间复杂度分别是多少？
  1. 归并排序的空间复杂度是O(1)吗？
  1. 优先队列，ExtractMaxElement方法的时间复杂度是多少？（写上界）
  1. 堆排序在最坏、最好、平均情况下的时间复杂度分别是多少？
  1. 堆排序的空间复杂度是O(1)吗？
  1. 堆排序的使用情况是什么？（至少写2个）
  1. 确保一个堆是大顶堆的算法MaxHeapify的时间复杂度是__？构建大顶堆的算法BuildMaxHeap的时间复杂度是__?
      2. O(lgn)、O(n)
  1. 快速排序在最坏、最好、平均情况下的时间复杂度分别是多少？
      2. O(n*lgn)、O(n*lgn)、O(n^2)
  1. 归并排序的稳定性
      2. 稳定
  1. 堆排序的稳定性
      2. 不稳定
  1. 快速排序的稳定性
      2. 不稳定
  1. 直接插入排序的稳定性
      2. 稳定
  1. 计数排序的稳定性
      2. 稳定
  1. 如果待排序的n个元素具有相同的值，那么快速排序总共需要比较多少次？
      2. n*(n-1)/2
  1. 快速排序出现最坏情况的两种实例
      2. 所有元素都相等、升序（降序）

第二次上机

  1. 矩阵链乘
      2. notion image
      • 上机书上有算法
      • 笔试运算量大
  1. Longest Common Subsequence（最长公共子序列）
      2. notion image
  1. Longest Common Substring（最长公共子串）
      2. notion image
  1. 最大子数
      2. notion image
  1. 最短路径
      2. notion image
      • 若要求以DP求解，则不能用迪杰斯特拉算法

第二次上机补充题（考试重点）

  1. 矩阵连乘的最优次序（以第二次上机第一题为例）
      2. ((A1(A2A3))A4)
      (((A1A2)A3)A4)
      (A1(A2(A3(A4A5))))
      (A1(((A2A3)A4)A5))
  1. 矩阵连乘的递推式
      2. 看书
  1. Ai...j,被完全加括号的开销，等于计算矩阵Ai...k与计算矩阵Ak+1...j的开销之和吗？
      2. 不等，还有合并相乘的开销
  1. 矩阵链乘主算法的时间复杂度是多少？有多少个子问题？
      2. O(n^3)、子问题数等于m数组上三角大小
  1. 矩阵链乘中m数组的作用
      2. 计算Ai..j所需最小乘法次数
  1. 矩阵链乘中s数组的作用
      2. Ai..j的最优分裂位置
  1. LCS算法的递推式
      2. 看书
  1. 若两个序列的长度分别是m和n，则算法LCS Length（主算法）的时间复杂度是多少（上界表示）？子问题个数是多少（紧致界）？
      2. O(m*n)、O(m*n)
  1. OutputLCS的算法的时间复杂度是多少？
      2. O(m+n)
  1. MaxSum算法的递推式
      2. 看书

第三次习题课

第三次上机补充题

  1. 写出分数背包、0-1背包分别属于哪一类算法（贪心、DP）
  1. 分别写出用分数背包、0-1背包解决上机第一题的总和是多少？（163、155）
  1. 若得到分数背包的最优解，需要满足什么条件？（Vi/Wi 降序排列）
  1. 写出0-1背包问题的算法的递推表达式（书上有）
  1. 0-1背包主算法的时间复杂度（O(nw)，输出算法的时间复杂度是O(n)）
  1. 写出A到各个点的最短路径（上机第三题，单元点最短路径问题）
  1. 解决上机第三题采用哪个算法？为什么？(贝尔曼-福德算法，可以检测是否存在负权值的回路)
  1. 简述第7题算法的核心思想以及时间复杂度（O(VE)）
  1. 写出弗洛伊德-Warshall算法的递推表达式D((k),ij)（书上有）
  1. （Johnson）算法在边少的情况下，效率是高还是低？（效率高）

第四次习题课

代码提交格式

  • 只交源代码，不要交可执行文件等
      • notion image
  • 四份实验报告双面打印，装订成一份。不要附加源码。

第四次上机

  • 回溯法考试考的不多，但建议理解记忆框架的核心代码