数据导论() 视频内容笔记

导论

1.预备知识(require) 需要懂得离散数学(discrete mathematics )和概率论(probability)的基础知识 2.算法分析(analysis of Algorithms), 算法设计(Design of Algorithms ),前者是理论研究(study)，关于计算机性能(computer performance )和资源利用的研究

比性能(performance)更加重要的是什么?
为什么要学习和研究性能？性能如同是货币，可能你更加需要水，房子，食物，但是你必须要拥有货币才可以买到它们～，这是在说明研究性能的重要性
举例说明，Java 比C 的编译速度慢三倍左右，但是人们认为是值得的，因为 Java 自身带有很多优秀的机制，比如，面向对象，比如异常检测
排序问题 ,其中包含了很多算法，比如: 输入 a1~aN，输出从小到大排列的数据，其中有一个算法叫做插入排序(insertion sort ),可以使用伪代码(pseudocode )的形式表现
```
----> 构建数据A = [ ] 
----> for j=2 to A.length
-------->key = A[j]
-------->i = j-1
-------->while i >0 and A[i] >key
------------>A[i+1] = A[i]
------------>i = i-1
-------->A[i+1] = key
```
分析 插入排序(insertion sort )的时间问题 (running Time ),影响因素有很多: 7.1. 输入，插入排序最坏的情况是所有数据都是逆序排列 7.2 . 输入规模(input size )，数量级别很大的，就会需要很长时间，我们将数据参数化(parameterize), 我们会把运行时间看作是排序数据规模的函数(talk about time as a function of the size of things that we are sorting) 7.3 .运行事件的上线时间，是一种对于用户的承诺 7.4 最坏情况分析(worst-case analysis),是我们通常最关注的，通常使用T(n) = n 时规模下的最长运行时间，表示一个程序在最坏情况下需要的时间 7.5 .平均时间(Average Case ): T(n) = 所有规模n 之下所有可能输入的期望时间(Expected Time), 期望时间需要使用到加权平均的概念，也就是时间* 对应时间出现的概率，每次概率出现的时间是需要做出假设的（assumption）,一个有关输入的统计分布假设,(make a assumption of the statistical distribution of inputs ) ，如果没有这样的假设，所有的输入是没有任何意义的，最常见的假设就是等概率出现 , 7.4 最好情况分析(Best-Case): 是一种假象(bogus)，没有实际的效果，因为任何慢序排列的最好情况都是可以实现好的结果的
插入排序(insertion sort )的最坏情况情况(worst-time): 8.1 渐进分析(asymptotic analysis ) = 算法的大局观( Big Idea) ：表示忽略硬件时间而是关时间的增长(growth)， 8.2 θ theta 符号表示的含义 = 一个公式，省去它的低阶项，并且忽略其安眠的常数因子 , 3n³+ 9n²+ 2n¹+8967 =θ(n³),如果随着n的数量不断的变大 n-->∞,最终会有一个θ(n²)的算法超过 θ(n³)的算法，前者的算法就会更加快，这就是渐进分析的魅力，θ 表示的复杂度的意思吧，越大级别的表示越复杂，复杂度越低的速度会越快！n³ 和 n² 会有一个交合点(n₀),从这个点以后n³ 复杂度会永远比n²多，但是这个交合点(n₀)可能会很大，所以我们更加关注低速算法
插入排序(insertion sort )的最坏情况情况(worst-time) = 逆向排序 9.1 内存引用计数= 访问变量的次数，当我们循环变量的时候变量j 从 2---->n ,也就是2----n 的相加，但是对于每一个j 取值，需要操作次θ(j) = j*? ,表示每次都是乘以一个固定的值，所以公式如下,里面包含了级数运算(Arithemtic series):
$T(n) = \prod_{j=2}^{n}\Theta (j)=\theta (n^{2})$
9.2 相对于巨大的n，插入排序运算会很慢，所以需要一个新的排序
归并排序(Merge sort ), 9.1 如果n=1 ,截止，如果n!=1,分别对[1,n/2]和[n/2,n]分别进行排序, 3.把排好序的两个表进行那个归并(merge),比如[20,13,7,2],[12,11,9,1],取最小元素(总是会出现在表头或者是表尾)，进行逐一比较，time = θ(n),第一步需要的时间θ(1),第二步需要的时间2T(n/2),第三步需要的时间θ(n) 9.2 使用递归树方法处理递归式子，把T(n)用T(n/2)进行表示，解释其中的时间成本 T(n) = cn +T(n/2)+T(n/2) 参考一参考二

Deft-pawN / sam-for-test

数据导论() 视频内容笔记 #24

导论

MIT算法导论-第二讲-渐进符号，递归及解法

Deft-pawN / sam-for-test

数据 导论() 视频 内容笔记 #24

导论

MIT算法导论-第二讲-渐进符号，递归及解法

数据导论() 视频内容笔记 #24