第一课 分析算法+插入排序

1、关注性能performance
什么比性能更重要？
安全性，简洁，可维护性，软件健壮性，功能性，模块化，用户友好
为什么学？
算法能将不可行变可行；是一种描述程序的语言（性能一定程度上相当于货币）

2、排序问题
插入排序（伪代码pseudocode）
input：A[1….n]
for j ←2 to n：
do key←A[j]
i ←j-1
where i >0 and A[i]>key:
do A[i+1]←A[i]
i = i-1
A[i+1]←key
运行时间的影响因素
输入的排序情况
输入规模
运行上界（对用户的承诺）
评判标准
最坏情况：T(n)=max time
平均情况：T(n)=average time
最好情况：假象bogus
运行时间的影响
计算机
相对速度（不同算法在同一电脑）
绝对速度（同一算法在不同电脑）
大局观BIG IDEA：渐进分析
1、忽略依赖机器的常量
2、不检查实际运行时间，关注运行时间的增长
渐进符号：
θ舍弃低阶项，忽略常数项
tips：如果你想成为一个程序员，只要两年中每天坚持编程就能成为程序员；如果想成为世界级程序员，你既可以十年如一日地坚持每天编程，也可以两年每天编程，然后上一门算法课。
归并排序merge sort

第二课

时间复杂度的推导公式

第三课 分治法

分治法
分divide：大问题分成小题
治conquer：递归解决小问题
合并：
归并排序