前言
算法分析是對一個算法需要多少計算時間和存儲空間作定量分析。此文主要介紹如何使用漸近分析記号來表示算法的時間複雜度以及如何對算法效率進行比較。
分析涉及的概念
- 輸入規模度量
- 算法的時間效率和空間效率都用輸入規模的函數進行度量
- 對相同大小的輸入執行個體具有相同的分析結果
- 對于所有的算法，對于規模更大的輸入都需要運作更長的時間
- 經常使用一個輸入規模\(n\)為參數的函數來研究算法效率
- 運作時間的度量機關
- 用算法的基本操作（算法中最重要的操作）的執行次數來度量算法的時間效率
- 基本操作通常是算法最内層循環中最費時的操作
-
算法運作時間的估計
\[T(n) \approx c_{op}C(n)
\]
- \(n\)是算法的輸入規模
- \(c_{op}\)是特定計算機中一個算法基本操作的執行時間
- \(C(n)\)是該算法需要執行的基本操作的次數
- 算法的最優、最差和平均效率
- 最差效率是指輸入規模為\(n\)時，算法在最壞情況下的效率
- 最優效率是指輸入規模為\(n\)時，算法在最優情況下的效率
- 平均效率是指在"典型"或"随機"輸入的情況下，算法具有的行為（效率）
小規模輸入在運作時間上的差别不足以将高效算法和低效算法區分開來。一個需要指數級操作次數的算法隻能用來解決規模非常小的問題。
指數增長是恐怖的，例如\(n^2\)和\(2^n\)，當規模增加一倍，\(n \to 2n\)，那麼對于\(n^2\)來說，運作時間隻是增加4倍，而對于\(2^n\)來說，卻是增加了\(2^n\)倍，這個倍數與n有關。
漸近表達式
常數間的差異較小，在表示算法時間複雜度時我們通過省略常數對表達式的影響，如：\(100n^2\)、\(1.5n^2\)、\(n^2+4\)、\(10n^2-3n+6\)，我們都看成是相等的。
- 漸近表達式的核心内容就是忽略常數。
- 漸近表達式是一個被大家認同的計算機裡表示運作時間和空間的方法。是另一個數學系統，和精确數學、模糊數學以及近似數學都不相同。
漸近分析的符号
算法效率的主要名額是基本操作次數的增長次數。為了對這些增長次數進行比較和歸類，計算機科學家們使用了3種符号：
- \(O\) 上界
- \(\Omega\) 下界
- \(\Theta\) 近似
漸近上界符\(O\)
存在正常數\(c\)和\(n_0\)，使得對所有\(n \ge n_0\) ，有
\[f(n) \le cg(n)
記為\(f(n) \in O(g(n))\)
如，\(n \in O(n^2)\) ，\(100n+5 \in O(n^2)\)，\(n(n-1)/2 \in O(n^2)\)
漸近下界符\(\Omega\)
存在正常數\(c\)和\(n_0\)，使得對所有\(n \ge n_0\)，有
\[f(n) \ge cg(n)
記為\(f(n) \in \Omega(g(n))\)
如，\(n^3 \in \Omega(n^2)\)，\(n(n+1) \in \Omega(n^2)\)，\(4n^2+5 \in \Omega(n^2)\)
漸近近界符\(\Theta\)
存在正常數\(c_1\)，\(c_2\)和\(n_0\)，使得對所有\(n \ge n_0\)，有
\[c_2g(n) \le f(n) \le c_1g(n)
記為\(f(n) \in \Theta(g(n))\)
如，\(n^2+3n+2 \in \Theta(n^2)\)，\(n(n-1)/2 \in \Theta(n^2)\) ，\(4n^2+5 \in \Theta(n^2)\)
漸近符号的有用特性
定理：如果\(t_1(n) \in O(g_1(n))\) 并且\(t_2(n) \in O(g_2(n))\) ，則
\[t_1(n)+t_2(n) \in O(max\{g_1(n), g_2(n)\})
對于符号\(\Theta\)和\(\Omega\)，該定理也成立。該定理表示：當算法由兩個連續執行部分組成時，該算法的整體效率由具有較大增長次數的那部分所決定。
在漸近分析種等号的濫用
我們使用\(f(n)=O(g(n))\)來表示\(f(n)\)是\(O(g(n))\)的一個成員函數，而不用傳統的\(f(n) \in O(g(n))\)來表示，是因為習慣問題。
例如，\(f(n)=5n^3；g(n)=3n^2；f(n)=O(n^3)=g(n)\) 但是\(f(n) \ne g(n)\)
是以，\(f(n)=\Theta(g(n))\)的确切意義是：\(f(n) \in \Theta(g(n))\)。一般情況下，\(\Theta(g(n))\)表示的是\(\Theta(g(n))\)中的某個函數。如，\(2n^2+3n+1=2n^2+\Theta(n)\) 表示\(2n^2+3n+1=2n^2+f(n)\)，其中\(f(n)\)是\(\Theta(n)\)中某個函數。
漸近分析記号的若幹性質
- 傳遞性
- 反身性
-
對稱性
\(f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n))\)
-
互對稱性
\(f(n)=O(g(n)) \Leftrightarrow g(n)=\Omega(f(n))\)
\(f(n)=o(g(n)) \Leftrightarrow g(n)=\omega(f(n))\)
-
算術運算
\(f(n)+g(n)=O(max\{f(n),g(n)\})\)；
\(f(n)+g(n)=O(f(n)+g(n))\)；
\(f(n)*g(n)=O(f(n)*g(n))\)；
\(cf(n)=O(f(n))\)；
\(g(n)=O(f(n)) \Rightarrow g(n)+f(n)=O(f(n))\)；
算法效率的比較
基本的效率類型
常數\(C\) < 對數\(logn\) < \(log^2n\) < 線性\(n\) < \(nlogn\) < 平方\(n^2\) < 立方\(n^3\) < 指數\(2^n\) < 階乘\(n!\) < \(n^n\)
最常用的關系式
- 多項式：\(a_0 + a_1n + a_2n^2+...+a_dn^d = \Theta(n^d)\) ，其中 \(a_d > 0\)
- 對數：\(log_an=\Theta(log_bn)\)，其中\(a，b>0\)為常數。（我們不區分底數是2還是10）
- 對數：對任意\(a,b>0,(logn)^a=O(n^b)\) （需要注意，b可以是小數）
- 指數：對任意\(r>1\)和\(d>0\)，\(n^d=O(r^n)\)
基本效率類型舉例
-
線性時間 \(O(n)\)
運作時間隻是輸入大小的一個常數倍數。
如，求n個數中最大數問題；合并兩個有序的序列；
-
\(O(nlog(n))\)時間
\(O(nlog(n))\)時間多出現在分治算法中。如合并排序、堆排序都将産生\(O(nlog(n))\)時間。
-
平方時間 \((O^2)\)
如，列舉所有元素對；求平面上n個點中最近的兩個點之間的距離。
- 多項式時間 \(O(n^k)\)
-
指數時間
最大獨立集問題：給出一個圖，求最大的一個點集使得其中任何兩個點都不存在一條邊。窮舉搜尋産生運作時間\(O(n^22^n)\)的算法。
漸近增長率比較的三種方法
-
定義法
找到正常數\(c\)和\(n_0\)使得對所有\(n\ge n_0\)，有\(f(n) \le cg(n)\)，則\(f(n)=O(g(n))\)
-
極限法，若
\[\lim\limits_{n \to \infty }{\frac{f(n)}{g(n)}=0}
則，\(f(n)=O(g(n))\).
- 前兩種情況意味着 \(t(n) \in O(g(n))\)
- 後兩種情況意味着 \(t(n) \in \Omega(g(n))\)
- 第二種情況意味着 \(t(n) \in \Theta(g(n))\)
-
取對數法
對于比較難比較的兩個數，我們可以先對它們同時取對數後進行比較。但是要注意，取完對數後的常數是不能忽略的。
小結
開學三個月後，終于有時間寫部落格了~😂 （祭出這段時間的算法筆記）
每天進步一點點，不要停止前進的腳步~