Day1_算法分析方法

1. 课堂笔记：
   • 程序执行效率影响因子：
     • 输入：评估时使用最坏情况输入
     • 输入大小：考虑n渐进∞
     • 机器执行效率: 忽略
   • 两种排序算法比较
     • 插入排序n²
     • 归并排序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）