MIT公开课:算法导论 笔记(一)

课程链接:http://open.163.com/special/opencourse/algorithms.html

第一课:算法分析基础

1.介绍插入排序与归并排序,计算并比较最坏运行时间

2.算法分析重点与渐近分析方法

以下为个人笔记,根据字幕整理


第一课 算法分析
总结 解决问题的方法和方式
算法:关于计算机程序性能和资源利用的研究

算法:性能、速度

在程序设计方面,什么比性能更重要呢?
  正确性,可维护,健壮性
  模块化,安全,用户友好

为什么关注性能?
1.直接决定方法可行不可行
  算法能将不可行变为可行
2.算法是一种描述程序行为的语言
  思考程序的最简洁方式

性能是支付其他东西的“货币”
安全 用户友好 健壮性
    |         | |           |
           性能
衡量代价的一般标准

为什么关注速度?
追求速度是人的天性

、、、、、、、、、、、、、、

排序算法

排序问题的一般描述
输入:序列 a1, a2, a3, ..., an
按需求重新排序
输出:序列 b1, b2, b3, ..., bn

1.插入排序

伪代码描述:
理解算法要描述的意思,简洁
使用缩进表示嵌套

按照升序排列

for j<- 2 to n
  do key<- A[j] //从数组A中取值
  i<- j-1
  while i>0 and A[i]> key //前向查找较大值
    do A[i+1]<- A[i]
    i<- i-1 //i递减至0
  A[i+1]<- key

实例 8 2 4 9 3 6
一次 2 8 4 9 3 6
二次 2 4 8 9 3 6
三次 2 4 8 9 3 6
四次 2 3 4 8 9 6
五次 2 3 4 6 8 9

最坏情况分析
最大占首位,最小占末位

操作数计数:内存引用计数
T(n) = sum _{2->n}( theta(j) )
算术级数 theta(n^2)

小规模n 快速
大规模n 慢
、、、、、、、、、、、、、、、、、、、、、、、、、、

程序分析:
1.运行时间
输入是否有序
输入规模
运行时间上界:对用户的承诺

最关注:
最坏情况分析
T(n) 输入规模为n时的运行时间上界
平均情况分析
T(n) 输入规模为n时,运行时间的期望值

算法的大局观
1.算法涉及诸多领域
2.解决复杂问题

渐近分析
1.忽略依赖于机器的常量
2.关注运行时间的增长,而不是运行时间

相对速度 绝对速度

渐近符号
theta符号函数
theta(n) = 3n^2 + 9n^2 + 5n
去掉常数项、低阶项

数学的严谨,工程的直觉
在两者间找到一种平衡,较好的算法

低速算法
当输入规模在合理范围时,运行速度较快

、、、、、、、、、、、、、、、、、、、、、、、、、、、

归并排序
if n==1 done
else recursively sort
  A[1 ... celi(n/2) ] //ceil向上取整
  A[ celi(n/2)+1 ... n ]
last merge 2 sub sorted list

归并子程序

两个子排序结果:
list[1] 20 13 7 2
list[1] 12 11 9 1

遍历与归并时间
T(n)

递归式
n=1 T(n)=theta(1)
n>1 T(n)=2T(n/2)+theta(n)
-----------------------
如何求解递归式?
-----------------------
递归树
T(n)
T(n/2) T(n/2)
T(n/4) ... T(n/4)
... ...
T(1)  ... ... T(1)

计算量
C(n)
C(n/2) C(n/2)
C(n/4) C(n/4)
... ...
C(1)  ... ... C(1)

高度 log(n)
叶节点数目 n
计算量

cn*log(n) + theta(n)
=theta(n*log(n))

as long as you are rigorous and precise,
you can be as sloppy as you want.
只要你严格而精确,可以略去任意细节

上一篇:机器学习实战(Machine Learning in Action)学习笔记————02.k-邻近算法(KNN)


下一篇:acwing 算法面试、笔试题公开课整理记录