算法4（Algorithms4）- Part 1 算法分析（Analysis Of Algorithms）

注：由于簡書不支持Latex語法，建議閱讀此篇文章 。

本文分為5節(jié)，分別是：

1. 介紹（introduction）： 介紹算法分析的必要性和重要性
2. 觀察（observations）： 通過分析一個經(jīng)典問題 3 - SUM問題，逐漸引出算法分析的方法論
3. 數(shù)學模型（mathematical models）： 如何具體分析比較算法的優(yōu)劣呢？我們需要對算法的運行時間進行分析并建立數(shù)學模型
4. 增長級（order-of-growth classifications）： 對算法運行時間進行分類
5. 內(nèi)存（memory）： 算法使用了多大的內(nèi)存？

本文貫穿始終的是3 - SUM 算法，其中也提到了二分查找（binary search）算法。

1. 介紹

1.1 人物介紹

在算法開發(fā)過程中，有這么幾個角色

• 程序員（Programmer） ： 需要開發(fā)出能解決問題的算法
• 用戶（Client） ： 想要高效的解決問題
• 理論家（Theoretician） ： 想要搞清算法的原理
• *學生（Student） ： 可能要扮演上述任一個角色

1.2 運行時間

1.3 為什么要分析算法？

• 可以對已知算法的性能進行預測
• 可以比較多個算法的優(yōu)劣
• 可以對已知算法提供性能保證
• 可以理解基本的算法相關理論

本課會涉及前三點，后面的兩點則是算法理論研究相關的方向。

基于實用性的原因：避免性能上的bug。
用戶可能因為程序員不了解性能特性而獲得很差性能的代碼。

1.4 一些成功的算法

1. 離散傅里葉變換（Discrete Fourier transform）

• 將N個圖樣的波形分解成周期分量
• 應用 ： DVD， JPEG， MRI（Magnetic Resonance Imaging， 核磁共振成像）， 天體物理學...
• 暴力破解 ： N ^ 2步
• FFT 算法 ： N * log N 步， 使新技術成為可能

2. N體模擬（N - body simulation）

• 模擬N個物體間的引力相互作用
• 暴力破解 ： N ^ 2
• Barnes-Hut算法（Barnes-Hut algorithm） ： N * log N 步， 使新研究成為可能

1.5 我們面臨的挑戰(zhàn)

問題 ： 我的算法能夠解決大量的輸入數(shù)據(jù)嗎？

• 算法可能很慢
• 算法使用內(nèi)存可能超標

如何對算法進行分析呢？

高德納（Donald Knuth）在20世紀70年代提出： 使用 科學的方法（scientific methods） 來分析算法性能。

1. 應用于算法分析的科學方法

我們需要一個體系，滿足以下兩個條件：

• 可以預測算法的性能
• 能比較不同算法的優(yōu)劣

2. 科學的方法

• 觀察（Observe） ： 觀察自然界的特性
• 假設（Hypothesize） ： 假設一個和觀察結(jié)果一致的模型
• 預測（Predict） ： 根據(jù)假設進行預測未發(fā)生的情況
• 驗證（Verify） ： 進行更多的觀察，以此驗證我們的預測
• 確認（Validate） ： 不斷重復上述過程，直到觀察和假設能完全一致

3. 需要遵守的原則

• 實驗必須可重復（reproducible）
• 假設必須可被明確檢驗對或者不對（falsifiable）

2. 觀察

我們來看一個例子：3 - SUM問題。

2.1 3 - SUM問題

給出N個不同的整數(shù)，隨機挑三個數(shù)構成一個組合，使這個組合中的三數(shù)之和為0， 這樣的組合一共有多少個？

2.2 暴力破解

最容易想到的解法就是使用暴力算法，三個循環(huán)，遍歷獲取。代碼如下：

如何判定這個實現(xiàn)好不好呢？我們需要計算它的運行時間。

1. 運行時間

如何獲得運行時間呢？

• 使用秒表手動計時
• 使用algs.jar中的Stopwatch類。

使用方法如下：

2. 數(shù)據(jù)分析

按照數(shù)據(jù)量從小到大排列，運行得出的時間：

使用標準坐標，將其坐標描點，用平滑曲線連接，如圖所示。

使用純對數(shù)坐標（Log-log圖）。

通過對對數(shù)坐標的圖進行觀察，我們發(fā)現(xiàn)這條線近似直線。設其斜率為b，常數(shù)項為c。
得出方程：

    lg(T (N)) = b lg N + c

解得常數(shù)項為：

    b = 2.999
    c = -33.2103

得出結(jié)論：

    T (N) = a * N ^ b，其中 a = 2 c

假設 ： 運行時間計算公式為（單位為s）：

    T(N) = 1.006 * 10 ^ 10 * N ^ 2.999 

3. 預測和驗證

根據(jù)上面假設的公式進行預測：

• N = 8000時， 時間為51s
• N = 16000時， 時間為408.1s

驗證：

證實了假設是對的！

我們通過進一步觀察發(fā)現(xiàn)，每當數(shù)據(jù)量翻倍時，其運行時間也呈規(guī)律性的變化。

每次運行時間與上次運行時間的比率ratio，其對2取對數(shù)，即 lg ratio 趨近于3。
根據(jù)這點，更進一步假設 ：

    T(N) = a * N ^ b, 其中 b = lg ratio

現(xiàn)在假設 b = 3， 從而求出a的值。

最終得出

    T(N) = 0.998 × 10 ^ –10 × N ^ 3

事實上，這個公式和根據(jù)線性回歸（linear regression）計算得出的公式相當相近了。

4. 在實踐中影響算法表現(xiàn)的因素

不受外部系統(tǒng)影響的部分

• 算法
• 輸入數(shù)據(jù)

受外部系統(tǒng)影響的部分

• 硬件（Hardware） ： CPU， 內(nèi)存， 緩存，...
• 軟件（Software） ： 編譯器， 解釋器， 垃圾回收（GC），...
• 系統(tǒng)（System） ： 操作系統(tǒng)（OS）， 網(wǎng)絡， 其它應用，...

通過這節(jié)我們對3-SUM算法的暴力實現(xiàn)算法進行了分析，得出了一些簡單的結(jié)論。能夠根據(jù)公式，輸入一定數(shù)量的數(shù)據(jù)，得出運行時間。

如何對其它更廣泛的算法進行計算呢？我們需要對算法內(nèi)部的代碼進行更細致的分析。

3. 數(shù)學模型

3.1 運行時間的數(shù)學模型

給定一個算法，其總的運行時間T = 算法中每個具體操作耗費的時間T_i * 該操作出現(xiàn)的次數(shù) n_i 之和。

我們需要知道以下幾點：

• 需要對程序進行分析，以確認操作的次數(shù)
• 耗費時間取決于硬件和編譯器
• 操作的次數(shù)取決于算法和輸入的數(shù)據(jù)

大體上說， 精確的數(shù)學模型是十分有價值的。

1. 基本操作的時間

以上是常見數(shù)學計算的耗時。

以上是計算機語言中常見操作的耗時，c_i表示常數(shù)時間， N表示輸入的數(shù)據(jù)量。

新手錯誤 ： 濫用字符串連接（string concatenation），因為這和輸入數(shù)據(jù)量成正比，我們應該追求更高效的做法。

接下來，我們看幾個由3-SUM簡化出的問題，逐步分析。

2. 例子： 1 - SUM問題

問題： 當輸入的數(shù)據(jù)有N個時，需要操作多少步？

圖中給出了各種必要的操作及其次數(shù)。

3. 例子： 2 - SUM問題

問題： 當輸入的數(shù)據(jù)有N個時，需要操作多少步？

圖中給出了各種必要的操作及其次數(shù)。
相比1 - SUM中的操作，2 - SUM中操作次數(shù)計算開始變得繁瑣和難以計算。

3.2 簡化計算

1. 耗費模型的簡化

“ It is convenient to have a measure of the amount of work involved
in a computing process, even though it be a very crude one. We may
count up the number of times that various elementary operations are
applied in the whole process and then given them various weights.
We might, for instance, count the number of additions, subtractions,
multiplications, divisions, recording of numbers, and extractions
of figures from tables. In the case of computing with matrices most
of the work consists of multiplications and writing down numbers,
and we shall therefore only attempt to count the number of
multiplications and recordings. ” — Alan Turing

這是艾倫 圖靈（Alan Turing）說過的一段話，大意是：
“測量計算過程中涉及的工作量是很方便的，盡管可能結(jié)果很粗糙。我們可以計算在整個過程中各種基本操作應用的次數(shù)，然后賦予它們各種權重。
例如，我們可以計算加法、減法、乘法、除法、記錄數(shù)字和從表中提取數(shù)據(jù)的次數(shù)。在矩陣中計算的情況下，操作主要是由乘法和記錄數(shù)字組成，因此我們只嘗試計算乘法和記錄的次數(shù)?！?/p>

其中最后一句話提到“只嘗試計算乘法和記錄的次數(shù)”，這為簡化算法耗費時間的計算提供了思路。

例如剛才2-SUM問題中，我們只對關鍵操作的時間進行記錄，而忽略其它操作的時間。

我們只記錄訪問數(shù)組的時間，其次數(shù)N (N - 1)。

2. 波浪線表示法

• 當輸出個數(shù)為N時，估計函數(shù)的運行時間
• 忽略低階項
  • 當N很大時，低階項微不足道
  • 當N較小時，我們無需在意

對于第三項來說，當N = 1000時， ? N^2 + ? N大概是500000（十萬量級）， 而? N^3為166000000（億量級），相比來說，忽略低階項完全是說通的。

以下是2-SUM各項操作波浪線表示法得出的等價：

3. 例子： 2 - SUM問題

根據(jù)上面的方法進行簡化，計算出時間。

得出結(jié)論：2-SUM問題的算法時間復雜度為 ~ N^2。

4. 例子： 3 - SUM問題

根據(jù)上面的方法進行簡化，計算出時間。

得出結(jié)論：3-SUM問題的算法時間復雜度為 ~ {1/2} N^3。

5. 估計離散求和

問題：如何對離散值求和？

• 學習離散數(shù)學
• 使用微積分

理論中，精確的數(shù)學模型十分重要。
現(xiàn)實中，

• 方程可能很復雜
• 可能需要高等數(shù)學的知識
• 具體的數(shù)學模型還是留給專家吧！

我們需要的是一個大概的模型，例如：T(N) ~ c N^3

4. 增長級數(shù)分類（order-of-growth classifications）

4.1 常見的增長級數(shù)分類

常見的函數(shù)：1， log_2 N， N，N log_2 N， N^2, N^3 和 2^N
這些函數(shù)已經(jīng)能足以描述常見算法的增長級數(shù)。（系數(shù)在此不做考慮）

下圖是以上函數(shù)對應的常見算法。

實踐中的增長級數(shù)

極限： 為了能摩爾定律（Moore's law）保持同步，我們需要線性（linear）或者線性對數(shù)級別（linearithmic）的算法。

4.2 二分查找

1. 目標

給定一個有序數(shù)組和其中的一個數(shù)，在數(shù)組中找到這個數(shù)的下標。

2. 二分查找

將此數(shù)和數(shù)組下標中點的數(shù)比較

• 給定的數(shù)太小，查找左邊
• 給定的數(shù)太大，查找右邊
• 相等的話，找到了

3. Java實現(xiàn)

這個問題的實現(xiàn)簡單嗎？
事實上

• 第一個二分查找算法于1946年發(fā)表；第一個沒有bug的二分查找于1962年發(fā)表
• Java中的Arrays.binarySearch()實現(xiàn)在2006年被發(fā)現(xiàn)有bug

提這些只是為了說明，正確的二分查找并沒有想象中的簡單..

如果key在數(shù)組a[]中，那么必有 a[lo] <= key <= a[hi]。

4. 數(shù)學分析

命題： 在長度為N的有序數(shù)組中進行二分查找，最多比較1 + lg N次。
證明：設T(N)為在長度為N的有序數(shù)組中進行二分查找時比較的次數(shù)。
易得T(1) = 1
N > 1時， T(N) = T(N / 2) + 1 （其中的1次是在和中點的數(shù)進行比較，T(N / 2)是之后左半部分或者右半部分進行比較）。
證明過程：

    T (N) ≤ T (N / 2) + 1               // 小于等于是可能第一次比較就等于
        ≤ T (N / 4) + 1 + 1
        ≤ T (N / 8) + 1 + 1 + 1
        . . .
        ≤ T (N / N) + 1 + 1 + … + 1     // 停止， 此時T(1) = 1
        = 1 + lg N

4.3 3 - SUM算法的一個N ^ 2 log N 實現(xiàn)

基于排序的算法

• 步驟一： 對N個不同的數(shù)進行排序
• 步驟二： 對于每對a[i]和a[j], 在數(shù)組中二分查找 -(a[i] + a[j])

分析： 增長級為N ^ 2 log N。

• 步驟一： 插入排序（insertion sort） -- N ^ 2
• 步驟二： 二分查找（binary search） -- N ^ 2 log N

4.4 算法比較

假設： 對于3-SUM 問題的兩個實現(xiàn)

• 基于排序的增長級為N ^ 2 log N的算法
• 暴力算法N ^ 3 算法
  前者比后者要快。

事實證明， 增長級更好 => 速度更快

4.5 算法理論中常用的符號表示

其中有三種符號： Theta (N^2)， O (N^2)和Omega (N^2)。

O 是用于描述函數(shù)漸近行為的數(shù)學符號。更確切地說，它是用另一個（通常更簡單的）函數(shù)來描述一個函數(shù)數(shù)量級的漸近上界。

Omega 的定義與O 的定義類似，但主要區(qū)別是，O 表示函數(shù)在增長到一定程度時總小于一個特定函數(shù)的常數(shù)倍，Omega 則表示總大于，來描述一個函數(shù)數(shù)量級的漸近下界。
Theta 是O 和Omega 的結(jié)合，是用來定義一個函數(shù)的數(shù)量級。

常見錯誤時：使用O 表示近似時間模型。

本文使用波浪線~ (tlide notation)用來表示算法的近似時間模型。

5. 內(nèi)存

5.1 基礎

• 比特（Bit）： 0 或 1
• 字節(jié)（Byte）： 8個比特
• 兆（MB， Megabyte）： 10 ^ 6或者2 ^ 20個比特
• 吉（GB， Gigabyte）： 10 ^ 9或者2 ^ 30個比特

64-bit計算機：其中指針長度為8bytes

• 可以為更大的內(nèi)存提供地址
• 指針消耗內(nèi)存更多（一些JVM會“壓縮”對象指針到4字節(jié)以節(jié)省內(nèi)存）

5.2 基本數(shù)據(jù)類型和數(shù)組的內(nèi)存占用

5.3 Java中對象的內(nèi)存占用

• 對象頭（Object overhead）： 16bytes
• 引用（Reference）： 8bytes
• 對齊填充（Padding）： 每個對象使用內(nèi)存均為8bytes的整數(shù)倍

例1： 一個Date對象使用32bytes的內(nèi)存

例2：一個長度為N的String類使用N ~ 2N bytes的內(nèi)存

5.4 總結(jié)

各種數(shù)據(jù)類型的內(nèi)存使用

• 基本數(shù)據(jù)類型（primitive type）： int型 4bytes， double型 8bytes
• 對象引用（object reference）： 8bytes
• 數(shù)組（array）： 24bytes + 每個數(shù)組成員的內(nèi)存 + 8bytes（如果有內(nèi)部類的話， 指向內(nèi)部類的指針）
• 對齊（padding）： 為了讓對象長度為8bytes的整數(shù)倍

淺層次內(nèi)存的計算： 不計算引用對象
深層次內(nèi)存的計算： 如果數(shù)組成員是一個對象引用， 需要將引用的對象內(nèi)存也計算在內(nèi)

舉例： 一個WeightedQuickUnionUF對象，其中數(shù)據(jù)長度為N， 計算其對象大小

其大小為 8 N + 88 ~ 8 N bytes。

參考網(wǎng)址

[1] Algorithms4
[2] 大O符號/大Ω符號/大Θ符號/小o符號/小w符號等各種算法復雜度記法含義
[3] Markdown中插入數(shù)學公式的方法
[4] MathJax basic tutorial and quick reference