首页 > 代码库 > Day1_算法分析方法

Day1_算法分析方法

  1. 课堂笔记:
    • 程序执行效率影响因子:
      • 输入:评估时使用最坏情况输入
      • 输入大小:考虑n渐进∞
      • 机器执行效率: 忽略
    • 两种排序算法比较
      • 插入排序n2
      • 归并排序nlgn
    • 递归
    • 技能1:评估多项式的时间级数θ
    • 技能2:构建算法的循环不定式,并证明其正确性
  2. 引申思考
    • 归并排序通过哪个关键步骤/方法使效率高于插入排序
  3. 编程训练
    • 归并排(与逆序数有关,poj2299)
    • 查找两个排序数组的中位数(leetcode)
  4. 习题(正确性证明):
    • 阅读课程handout1&2(http://www.cs.dartmouth.edu/~cs31/homework/BSiterative.pdf  ... BSrecursive.pdf)
    • 按照以上证明方法练习课本思考题2-1 ~ 2-4
    • 完成homework1(http://www.cs.dartmouth.edu/~cs31/homework/hw1.pdf)

Day1_算法分析方法