网易公开课-MIT麻省理工学院《算法导论》学习笔记（1）

本文为麻省理工学院《算法导论》课程第一讲的学习笔记。

网易云课堂上该课程的网站为http://open.163.com/special/opencourse/algorithms.html
<http://open.163.com/special/opencourse/algorithms.html>。

第一部分算法分析（Analysis of Algorithm）

目录

1. 前言
<https://blog.csdn.net/m0_37622530/article/details/80671477#1.%20%E5%89%8D%E8%A8%80>

2. 插入排序（insertion sorting）
<https://blog.csdn.net/m0_37622530/article/details/80671477#2.%20%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%EF%BC%88insertion%20sorting%EF%BC%89>

3. 分析的种类
<https://blog.csdn.net/m0_37622530/article/details/80671477#3.%20%E5%88%86%E6%9E%90%E7%9A%84%E7%A7%8D%E7%B1%BB%C2%A0>

4. 插入排序的最差情况是什么？
<https://blog.csdn.net/m0_37622530/article/details/80671477#4.%20%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%9A%84%E6%9C%80%E5%B7%AE%E6%83%85%E5%86%B5%E6%98%AF%E4%BB%80%E4%B9%88%EF%BC%9F>

5. 归并排序（merge sorting）
<https://blog.csdn.net/m0_37622530/article/details/80671477#5.%20%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%EF%BC%88merge%20sorting%EF%BC%89>

6. 递归树（Recurrence Tree）--解决递归问题的方法
<https://blog.csdn.net/m0_37622530/article/details/80671477#6.%20%E9%80%92%E5%BD%92%E6%A0%91%EF%BC%88Recurrence%20Tree%EF%BC%89--%E8%A7%A3%E5%86%B3%E9%80%92%E5%BD%92%E9%97%AE%E9%A2%98%E7%9A%84%E6%96%B9%E6%B3%95>

1. 前言

A course about performance（可行vs不可行）--关于算法与性能的课程。

性能就像获得其他方面提高（准确性、稳定性、用户友好性等）的”货币“。

2. 插入排序（insertion sorting）

排序问题：输入为一个序列{a1, a2, ... ,an}，输出一个重新排列后的序列{a1', a2', ... ,
an'}，使其满足某种排列要求。者皆可以插入排序为例进行讲解，后续还会涉及更多排序问题。

插入排序

设置两个循环。外循环j取由1到n，内循环i取由j-1到1；外循环用于依次判断当前的键值key，内循环用于寻找当前key应该插入的位置。【在每一次循环中，已经被排列好的部分（j项之前）保持不变。】

如下图例子（图片来自于百度百科词条“直接插入排序”）：

影响插入排序运行时间的因素：

1）输入序列【比如已经拍好的序列运算量最小；逆序排列是最差的情况，需要做最多的运算。】

2）输入序列的大小【越大，越慢】：需要将输入序列的大小参数化（parameterize）。

3. 分析的种类

1）最差的情况：定义T(n)为对于输入大小为n时，运行时间的上限（maximum time，对用户的一种保证）。

2）平均情况：定义T(n)为对于输入大小为n时，运行时间的平均值（expected
value，是对于不同n值所对应情况的加权平均，此处需要对不同n值出现的概率做出假设--need assumption for the
distribution of input size）。

3）最好的情况--一种“假象”（运行时间的上限才是对用户的保证，而下限不是）

4. 插入排序的最差情况是什么？

衡量的时候我们也需要考虑到计算机--有时我们选择观察相对速度（同一台计算机），这很好理解；有时我们又会观察绝对速度（不同计算机），比如我们想知道某个算法是不是在所有计算机上都有好的表现？

一个非常重要的想法：渐进分析（Asymptotic Analysis）

1）忽略掉那些依赖于计算机的常量

2）不去观测实际运行时间T(n)，而是观测运行时间的增长

举个例子：在插入排序中，我们假设每一步运算所耗费的运行时间是一个常数，这就是一种渐进分析。

因此对于插入排序的最差运行时间T(n)，我们可以表示为：

其中，theta是一种渐进分析记号，其定义如下[引用1]：

5. 归并排序（merge sorting）

其基本原理如下（图片来自课程视频）：

第3步合并（merge）所需的时间=θ(n)。

总的运行时间为（图片来自课程视频）：

对于n>1的情况，涉及到了递归（recurrence），如何求解将会在下一部分继续讨论。

6. 递归树（Recurrence Tree）--解决递归问题的方法

T(n)=T(n/2)+c*n，其中c是一个常数。可以表示为以下的树形结构：

最终（上图最右）树的高度是lg(n)；叶子（θ(1)）的数量为n。

所有叶子的求和为θ(n)；除最后一层外，每一层的求和是cn；所以总的和为T(n)=cn*lg(n)+θ(n)=θ(nlg(n))。

因此合并排序的最差运行速度比插入排序的θ(n^2)要快。

引用：

[1]
https://blog.csdn.net/wangxiaoan1234/article/details/76030263#theta%E8%AE%B0%E5%8F%B7

<https://blog.csdn.net/wangxiaoan1234/article/details/76030263#theta%E8%AE%B0%E5%8F%B7>

热门工具换一换

网易公开课-MIT麻省理工学院《算法导论》 学习笔记（1）