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

网易云课堂上该课程的网站为/special/opencourse/algorithms.html。

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

目录

1. 前言

2. 插入排序（insertion sorting）

3. 分析的种类

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

5. 归并排序（merge sorting）

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

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]/wangxiaoan1234/article/details/76030263#theta%E8%AE%B0%E5%8F%B7