网易公开课-MIT麻省理工学院《算法导论》 学习笔记（1）
本文為麻省理工學院《算法導論》課程第一講的學習筆記。
網易云課堂上該課程的網站為http://open.163.com/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]?https://blog.csdn.net/wangxiaoan1234/article/details/76030263#theta%E8%AE%B0%E5%8F%B7
總結
以上是生活随笔為你收集整理的网易公开课-MIT麻省理工学院《算法导论》 学习笔记（1）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [思考的乐趣] 有趣的莫比乌斯带
- 下一篇： kitti rotation,label