該文章為清華大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計MOOC課程讀書筆記.
1. Big O notation
1.1 O, Ω , Θ
當(dāng)n足夠大時力穗，一定存在一個常識c，使得c·f(n)肯定能大于T(n)气嫁，即能夠成為它的上界当窗。
T(n)是用算法規(guī)模來表示的對應(yīng)計算機基本操作的數(shù)量
同理得到下界
還有確界
1.2 對比
2. 算法分析
算法分析的兩大內(nèi)容就是：正確性 + 復(fù)雜度
你這個算法對不對？算出結(jié)果需要多少時間寸宵？多少空間崖面？
2.1 級數(shù)
兩大最重要的級數(shù)：算術(shù)級數(shù) + 幾何級數(shù)
-
算術(shù)級數(shù) O(n^2)
算術(shù)級數(shù)
arithmetic progression is a sequence of numbers such that the difference between the consecutive terms is constant.
-
幾何級數(shù) O(2^n)
幾何級數(shù)
geometric progression is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio.
-
調(diào)和級數(shù) O(logn)
調(diào)和級數(shù) 對數(shù)級數(shù) O(nlogn)
-
冪方級數(shù) O(n^k)
冪方級數(shù) 收斂級數(shù) O(1)
2.2 循環(huán)
-
算術(shù)級數(shù) Arithmetic progression
算術(shù)級數(shù) 幾何級數(shù) Geometric progression
2.3 封底估算 Back-Of-The-Envelope Calculation
A back-of-the-envelope calculation is a rough calculation. 一種非精確卻又能抓住本質(zhì)的估算。
3. 迭代與遞歸
3.1 減治 Decrease and Conquer
將問題分解為：平凡問題 + 子問題
平凡問題：可以非常容易地得到解
子問題：結(jié)構(gòu)上類似梯影，只是規(guī)模小了的原問題
3.2 分治 Divide and Conquer
將問題分解為兩個(或者多個)子問題
3.3 對遞歸的分析
遞歸跟蹤 Recursion Trace
形象地列出每個遞歸實例巫员，并根據(jù)每個遞歸實例的耗時來計算總耗時遞歸方程 Recurrence
利用遞歸方程來推導(dǎo)出時間復(fù)雜度
4. 動態(tài)規(guī)劃
4.1 Memoization
利用一個table來存儲計算結(jié)果，每計算一個遞歸實例時先查表看看是否已經(jīng)計算過
4.2 Dynamic Programming
-
Fibonacci
Fib的遞歸 VS 迭代動規(guī) Longest Common Subsequence(LCS)
解：右下
計算的方向：右下到左上
重復(fù)計算：紫色的遞歸實例會被它下面的實例以及右邊的實例調(diào)用甲棍，即被重復(fù)性地調(diào)用简识。
計算方向：左上到右下
無重復(fù)計算：每個計算單元由已計算好的左上或左或上的單元來求出。
