关键词：
课程链接：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.
只要你严格而精确，可以略去任意细节
网易公开课_算法导论_笔记a
http://open.163.com/special/opencourse/algorithms.html 个人理解 渐进分析istoignoremachine-dependentconstantsand,insteadoftheactualrunningtime lookatthegrowthoftherunningtime （以下=表近似、a=b=c、a与 查看详情
mit-6.006算法导论（2011秋）
L01AlgorithmicThinking，PeakFinding算法定义：高效处理大量数据的程序在学本课之前最好先学习6.042，本课进阶为6.046本门课的8个主要章节：算法思想、排序与树、哈希、超精度数的表示、图、路径寻优、动态编程、其他一维波峰寻找... 查看详情
mit线性代数公开课学习笔记第16~20课
十六、投影矩阵和最小二乘给出\(n\)组\(m-1\)个自变量的数据点(用\(n\timesm\)大小的矩阵\(A\)表示，其中第一列均为1，代表常数项)，以及它们的真实取值(用n维列向量\(b\)表示)，现在需要用一个\(m-1\)元未知数的线性方程来拟合这组... 查看详情
好书一起读(85)：算法笔记
...，读它就挺好。后一本我是边看麻省理工的《算法导论》公开课边读的，力不从心，因为我数学基础不好（详下），如果不看数学证明，其内容跟前一本就差不多了，数学基础比较好、对算法感兴趣的朋友，可以尝试之。强烈建... 查看详情
机器学习公开课笔记第五周之优化机器学习算法
一，提高机器学习算法准确度的方法当我们的机器学习算法不能准确预测我们测试数据时，我们可以尝试通过以下方法提高我们机器学习的算法准确度1)，获得更多的训练样例2)，减少特征数3)，增加特征数4)，增加多项式特征5)... 查看详情
吴恩达_mit_machinelearning公开课ch02(待补)(代码片段)
回顾回归我们在ch01使用gradientdescent[梯度下降]，实现了linearregression[回归]问题。简单地来说，我们在读入数据后提取出X[Varibale,factorsetc]作为我们的变量，或者说就是影响一个问题的一系列因素和Y[标签]问题的解。我... 查看详情
吴恩达_mit_machinelearning公开课ch03(代码片段)
回顾逻辑回归逻辑回归常用于分类问题。里面常用到的一系列公式函数不能忘记。比如：交叉熵损失函数用于度量当前拟合系数theta的损失值、Sigmoid激活函数，用于将值压缩至(0，1)区间内作为概率处理、为损失函数... 查看详情
吴恩达_mit_machinelearning公开课ch03(代码片段)
回顾逻辑回归逻辑回归常用于分类问题。里面常用到的一系列公式函数不能忘记。比如：交叉熵损失函数用于度量当前拟合系数theta的损失值、Sigmoid激活函数，用于将值压缩至(0，1)区间内作为概率处理、为损失函数... 查看详情
吴恩达_mit_machinelearning公开课ch01(代码片段)
之前一直和Tensorflow、PyToch一些框架进行纠缠。现在显然幡然醒悟，这样是不对的，我们不是去学怎么搭别人的顺风车，我们要做的是自己造轮子造车。任何课程评价都可以说是对这一门五星级课程的亵渎了。概念讲... 查看详情
吴恩达_mit_machinelearning公开课ch05(代码片段)
回顾神经网络ch04我们实现了属于自己的神经网络。一个完整的神经网络需要一个模型表示，比如网络层数及每一层的神经元个数。除此之外我们要保证网络的流动性，即实现前向传播和反向传播。前向传播是比较简单的&... 查看详情
吴恩达_mit_machinelearning公开课ch05(代码片段)
回顾神经网络ch04我们实现了属于自己的神经网络。一个完整的神经网络需要一个模型表示，比如网络层数及每一层的神经元个数。除此之外我们要保证网络的流动性，即实现前向传播和反向传播。前向传播是比较简单的&... 查看详情
吴恩达_mit_machinelearning公开课ch04(代码片段)
前章回顾在ch03中我们做了一个有趣的任务，就是做一个手写数字的分类。我们的数字包含了0~9共10类，于是我们的第一思路是训练出10个二元线性分类器。我们用一个大矩阵来存储每个线性分类器拟合出来的Theta，大... 查看详情
吴恩达_mit_machinelearning公开课ch04(代码片段)
前章回顾在ch03中我们做了一个有趣的任务，就是做一个手写数字的分类。我们的数字包含了0~9共10类，于是我们的第一思路是训练出10个二元线性分类器。我们用一个大矩阵来存储每个线性分类器拟合出来的Theta，大... 查看详情
mit计算机教育中缺失的一课笔记：命令行环境
_写在前面：本篇内容来自于MIT推出的课程：计算机教育中缺失的一课，这门课程介绍了命令行、强大的文本编辑器的使用、使用版本控制系统提供的多种特性等等。中文课程主页。本篇内容为第五节：命令行环境。本节的主要... 查看详情
机器学习公开课笔记第一周
一，机器学习是什么？ "AcomputerprogramissaidtolearnfromexperienceEwithrespecttosomeclassoftasksTandperformancemeasureP,ifitsperformanceattasksinT,asmeasuredbyP,improveswithexperienceE."Example:playingcheckers. 查看详情
局部加权回归欠拟合过拟合-andrewng机器学习公开课笔记1.3
本文主要解说局部加权(线性)回归。在解说局部加权线性回归之前，先解说两个概念：欠拟合、过拟合。由此引出局部加权线性回归算法。 欠拟合、过拟合 例如以下图中三个拟合模型。第一个是一个线性模型。... 查看详情
2017，不能再咸鱼了
...来把类型和程序设计语言这本书看了学一下MIT的PL方向的公开课学英语找一家优秀的实习不能咸鱼了不能咸鱼了不能咸鱼了 查看详情
《算法导论》读书笔记
本章是本书的开篇，介绍了什么是算法，为什么要学习算法，算法在计算机中的地位及作用。 算法（algorithm）简单来说就是定义良好的计算机过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。即算法... 查看详情