摘要：實(shí)際上這個(gè)情形中存在冪定律實(shí)際上絕大多數(shù)的計(jì)算機(jī)算法的運(yùn)行時(shí)間滿足冪定律。基于研究得知，原則上我們能夠獲得算法，程序或者操作的性能的精確數(shù)學(xué)模型。

上一篇：并查集
下一篇：棧和隊(duì)列

在算法性能上我們常常面臨的挑戰(zhàn)是我們的程序能否求解實(shí)際中的大型輸入：
--為什么程序運(yùn)行的慢?
--為什么程序耗盡了內(nèi)存?

沒有理解算法的性能特征會(huì)導(dǎo)致客戶端的性能很差，為了避免這種情況的出線，需要具備算法分析的一些知識(shí)。
此篇主要涉及一些基礎(chǔ)數(shù)學(xué)知識(shí)和科學(xué)方法，以及如何在實(shí)踐應(yīng)用中使用這些方法理解算法的性能。我們的重點(diǎn)放在獲得性能的預(yù)測(cè)上。
主要分為5部分：

觀察特點(diǎn) (observations)

數(shù)學(xué)模型 (mathematical models)

增長階數(shù)分類 (order-of-growth classifications)

算法理論 (theory of algorithms)

內(nèi)存使用 (memory)

注：下文我所的增長量級(jí)和增長階數(shù)是一個(gè)東西其實(shí)...

我們將從多種不同的角色思考這些問題：

程序員：解決一個(gè)問題，讓算法能夠工作，并部署它

用戶：完成某項(xiàng)工作，但不關(guān)心程序做了什么

理論家：想要理解發(fā)生的事情

團(tuán)隊(duì)：可能需要完成以上角色的所有工作

關(guān)于算法分析需要集中考慮的關(guān)鍵是運(yùn)行時(shí)間。運(yùn)行時(shí)間也可以理解為完成一項(xiàng)計(jì)算我們需要進(jìn)行多少次操作。
這里主要關(guān)心：

預(yù)測(cè)算法的性能

比較完成同一任務(wù)不同算法的性能

在最壞情況下算法性能的底線

理解算法如何運(yùn)行的一些理論基礎(chǔ)

算法分析的科學(xué)方法概述：

從自然界中觀察某些特征(程序在計(jì)算機(jī)上的運(yùn)行時(shí)間)

提出假設(shè)模型(與觀察到的現(xiàn)象相一致的模型)

預(yù)測(cè)(利用上邊的假設(shè)做出合理的預(yù)測(cè)，一般用來預(yù)測(cè)更大問題規(guī)模，或者另一臺(tái)計(jì)算機(jī)上的運(yùn)行時(shí)間)

驗(yàn)證(作更多的觀察來驗(yàn)證我們的預(yù)測(cè))

證實(shí)(重復(fù)地驗(yàn)證直到證實(shí)我們的模型和觀察的特征吻合，證實(shí)我們的模型假設(shè)是正確的)

使用科學(xué)方法有一些基本原則：

別人做同樣的實(shí)驗(yàn)也會(huì)得到相同的結(jié)果

假設(shè)必須具備某個(gè)特殊性質(zhì)：可證偽性

(可證偽性：指從一個(gè)理論推導(dǎo)出來的結(jié)論（解釋、預(yù)見）在邏輯上或原則上要有與一個(gè)或一組觀察陳述與之發(fā)生沖突或抵觸的可能。
可證偽，不等于已經(jīng)被證偽;可證偽，不等于是錯(cuò)的。)

第一步是要觀察算法的性能特點(diǎn)，這里就是要觀察程序的運(yùn)行時(shí)間。
給程序計(jì)時(shí)的方法：

看表(你沒看錯(cuò)，簡(jiǎn)單粗暴)

利用API：很多第三方或者Java標(biāo)準(zhǔn)庫中有一個(gè)秒表類，可以計(jì)算用掉的時(shí)間
(如apache commons lang,springframework的工具包都有，這里使用stdlib庫中的Stopwatch API 進(jìn)行時(shí)間監(jiān)控)

我們將使用 3-SUM 問題作為觀察的例子。

三數(shù)之和。如果有N個(gè)不同的整數(shù)，以3個(gè)整數(shù)劃為一組，有多少組整數(shù)只和為0.
如下圖，8ints.txt 有8個(gè)整數(shù)，有四組整數(shù)和為0

目標(biāo)是編寫一個(gè)程序，能對(duì)任意輸入計(jì)算出3-SUM整數(shù)和為0有多少組。

這個(gè)程序?qū)崿F(xiàn)的算法也很簡(jiǎn)單，首先是第一種，“暴力算法”

EN：brute-force algorithm
這里使用第三方API的方法測(cè)量程序運(yùn)行的時(shí)間。

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stopwatch;

    public class ThreeSum {
        public static int count(int[] a) {
            int N = a.length;
            int count = 0;
            //三重的for循環(huán)，檢查每三個(gè)整數(shù)組合
            for (int i = 0; i < N; i++)
                for (int j = i + 1; j < N; j++)
                    for (int k = j + 1; k < N; k++)
                    //為了方便觀察算法的性能問題，這里忽略了整型溢出問題的處理
                        if (a[i] + a[j] + a[k] == 0)
                            count++;
            return count;
        }
        /**
         * 讀入所有整數(shù)，輸出count的值
         * 利用StopWatch執(zhí)行時(shí)間監(jiān)控
         * @param args
         */
        public static void main(String[] args) {
            int[] a = StdIn.readAllInts();
            Stopwatch stopwatch = new Stopwatch();
            StdOut.println(ThreeSum.count(a));
            double time = stopwatch.elapsedTime();
        }
    }

測(cè)試數(shù)據(jù)可以用越來越大的輸入來運(yùn)行。每次將輸入的大小翻倍，程序會(huì)運(yùn)行得更久。通過類似的測(cè)試，有時(shí)能相當(dāng)方便和快速地評(píng)估程序什么時(shí)候結(jié)束。

通過實(shí)證得出的數(shù)據(jù)，可以建立圖像，使觀察更直觀：

標(biāo)準(zhǔn)坐標(biāo) ：Y軸：運(yùn)行時(shí)間；X軸：輸入大小

雙對(duì)數(shù)坐標(biāo)：Y軸：取運(yùn)行時(shí)間的對(duì)數(shù)；X軸：取問題輸入大小的對(duì)數(shù)

(lg以2為底)
使用雙對(duì)數(shù)坐標(biāo)通常情況下是得到一條直線，這條直線的斜率就是問題的關(guān)鍵。
這個(gè)例子(3-SUM 暴力算法)的斜率是3

--通過對(duì)數(shù)坐標(biāo)的方法得出公式：lg(T(N)) = blgN + c (可看做 y = b*x + c，其中 y = lg(T(N))，x = lgN)
--通過圖中兩點(diǎn)可求出b,c值，如果等式兩邊同時(shí)取2的冪，就得到 T(N) = 2^c*N^b, 其中 2^c 為一個(gè)常數(shù)，可記作 a

由此，從這個(gè)模型的觀察中我們就得到了程序的運(yùn)行時(shí)間，通過一些數(shù)學(xué)計(jì)算(在這里是回歸運(yùn)算)，我們就知道得出了運(yùn)行時(shí)間：
T(N) = a*N^b (b為雙對(duì)數(shù)坐標(biāo)中直線的斜率，同時(shí) b 也是這個(gè)算法的增長量級(jí)，第三點(diǎn)會(huì)講到)

假設(shè)
通過上述的數(shù)據(jù)分析，我們得出假設(shè)：
運(yùn)行時(shí)間看起來大約是 1.006 × 10^–10 × N^2.999 (秒)

預(yù)測(cè)
可以運(yùn)用這個(gè)假設(shè)繼續(xù)做預(yù)測(cè)，只要帶入不同的N值，就能計(jì)算出需要的大致時(shí)間。
?51.0 seconds for N = 8,000.
?408.1 seconds for N = 16,000.

驗(yàn)證
通過對(duì)比 程序?qū)嶋H運(yùn)行時(shí)間(下圖) 和 通過我們的假設(shè)模型預(yù)測(cè)的時(shí)間上一步) 可以看出結(jié)果非常相近 (51.0 vs ~51.0/408.1 vs ~410.8)

這個(gè)模型幫助我們?cè)诓恍枰〞r(shí)間運(yùn)行試驗(yàn)的前提下做一些預(yù)測(cè)。實(shí)際上這個(gè)情形中存在冪定律(a*N^b).實(shí)際上絕大多數(shù)的計(jì)算機(jī)算法的運(yùn)行時(shí)間滿足冪定律。

下邊介紹一種求解符合冪定律運(yùn)行時(shí)間中的增長量級(jí)值(b)的方法

計(jì)算b值

這里可以通過 Doubling hypothesis 的方法可以快速地估算出冪定律關(guān)系中的 b 值：
運(yùn)行程序，將每次輸入的大小翻倍(doubling size of the input)，然后計(jì)算出N和2N運(yùn)行時(shí)間的比率。主要看下圖的后幾行運(yùn)算時(shí)間比率，前幾行的輸入值小，以現(xiàn)在的計(jì)算機(jī)運(yùn)算能力處理起來，立方級(jí)別的增量級(jí)運(yùn)算速度快也相差無幾。

ratio ≈ T(2N)/T(N)

至于為什么 0.8/0.1≈7.7 或其他看起來 "運(yùn)算錯(cuò)誤" 類似的情況，是因?yàn)閳D上的運(yùn)行時(shí)間的記錄是簡(jiǎn)化精確到了小數(shù)點(diǎn)后一位，實(shí)際運(yùn)算比率值是使用了實(shí)際運(yùn)行時(shí)間(精確到小數(shù)點(diǎn)后幾位)去計(jì)算的，所以會(huì)出現(xiàn)0.8/0.1≈7.7。

通過不斷地進(jìn)行雙倍輸入實(shí)驗(yàn)，可以看到比率會(huì)收斂到一個(gè)常數(shù)(這里為8)，而實(shí)際上比率的對(duì)數(shù)會(huì)收斂到N的指數(shù)，也就是 b 的值，這里粗暴算法的 b 值就等于3

通過Doubling hypothesis方法我們又能提出假設(shè)：
此算法的運(yùn)行時(shí)間大約是 a*N^b, 其中 b = lg ratio
注意：Doubling hypothesis 不適用于識(shí)別對(duì)數(shù)因子

計(jì)算a值

得出 b 的值后，在某個(gè)大的輸入值上運(yùn)行程序，就能求出 a 值。

由此得出假設(shè)：運(yùn)行時(shí)間 ≈ 0.998 × 10^–10 × N^3 (秒)

我們通過作圖得出的模型( ≈ 1.006 × 10^–10 × N^2.999 )和我們通過Doubling hypothesis方法得出的模型是很接近的。

計(jì)算機(jī)中有很多的因素也會(huì)影響運(yùn)行時(shí)間，但是關(guān)鍵因素一般和計(jì)算機(jī)的型號(hào)無關(guān)。

關(guān)鍵的因素即為你使用的算法和數(shù)據(jù). 決定冪定律中的 b 值

還有很多與系統(tǒng)相關(guān)的因素：

硬件配置：CPU，內(nèi)存，緩存...

軟件環(huán)境：編譯器，解析器，垃圾回收器...

計(jì)算機(jī)的系統(tǒng)：操作系統(tǒng)，網(wǎng)絡(luò)，其它應(yīng)用...

以上所有因素，包括關(guān)鍵因素，都決定了冪定律中的 a 值

現(xiàn)代計(jì)算機(jī)系統(tǒng)中硬件和軟件是非常復(fù)雜的，有時(shí)很難獲得非常精確的測(cè)量，但是另一方面我們不需要像其他科學(xué)中需要犧牲動(dòng)物或者向一顆行星發(fā)射探測(cè)器這些復(fù)雜地方法，我們只需要進(jìn)行大量的實(shí)驗(yàn)，就能理解和得到我們想要知道的影響因子(的值)。

通過觀察發(fā)生了什么能夠讓我們對(duì)性能作出預(yù)測(cè)，但是并不能幫助我們理解算法具體做了什么。通過數(shù)學(xué)模型更有利于我們理解算法的行為。
我們可以通過識(shí)別所有的基本操作計(jì)算出程序的總運(yùn)行時(shí)間。
致敬一下，Don Knuth 在二十世紀(jì)60年代末便提出和推廣了運(yùn)行時(shí)間的數(shù)學(xué)模型：sum(操作的開銷 * 操作執(zhí)行的頻率)

需要分析程序以確執(zhí)行了哪些操作。

計(jì)算機(jī)以及系統(tǒng)的開銷取決于機(jī)器，編譯器。

頻率分析將我們引向數(shù)學(xué)方法，它取決于算法，輸入數(shù)據(jù)。

基于 knuth 研究得知，原則上我們能夠獲得算法，程序或者操作的性能的精確數(shù)學(xué)模型。

基本操作的開銷一般都是一個(gè)取決于計(jì)算機(jī)及系統(tǒng)的常量，如果想要知道這個(gè)常量是多少，可以對(duì)一個(gè)基本操作運(yùn)行成千上萬的實(shí)驗(yàn)的方式算出。比如可以進(jìn)行十億次的加法，然后得出在你運(yùn)行的計(jì)算機(jī)系統(tǒng)上進(jìn)行 a + b 的基本操作花費(fèi)大概 2.1 納秒
為了方便建立數(shù)學(xué)模型，絕大多數(shù)的情況下我們只要 假定它是某個(gè)常數(shù) cn (n:1,2,3...) 就可以。
下圖羅列了一下基本操作和其開銷

關(guān)于N：當(dāng)我們?cè)谔幚硪唤M對(duì)象時(shí)，假設(shè)有N個(gè)對(duì)象，有一些操作需要的時(shí)間和N成正比。比如第六行，分配一個(gè)大小為N的數(shù)組是，需要正比于N的時(shí)間，因?yàn)樵贘ava中默認(rèn)吧數(shù)組中的每個(gè)元素初始化為0.
還有些運(yùn)行時(shí)間去決定系統(tǒng)的實(shí)現(xiàn)，比如連接兩個(gè)字符串需要的運(yùn)行時(shí)間與字符串的長度(N)成正比，連接字符串并不等同于加法運(yùn)算

1-SUM 為例

數(shù)組中有多少個(gè)元素等于0

public class OneSum {
        public static int count(int[] a) {
            int N = a.length;
            int count = 0;
            for (int i = 0; i < N; i++)
                if(a[i] == 0)
                    count++;
            return count;
        }
}

其中幾項(xiàng)操作的頻率取決于N的輸入

2-SUM 為例

數(shù)組中有多少對(duì)元素等于0

public class TwoSum {
    public static int count(int[] a) {
        int N = a.length;
        int count = 0;
        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++)
                if (a[i] + a[j] == 0)
                    count++;
        return count;
    }
}

額外稍微解釋下數(shù)據(jù)怎么算來的，如果已經(jīng)了解可以略過以下細(xì)致的解釋。

j 每次迭代的增量都取決于 i 的值，因?yàn)?j 被初始化為 i + 1
便于理解可以用具體數(shù)值帶入：
假設(shè) N = 5
當(dāng) i == 0 時(shí)，i 遞增到 1，遞增了 1 次；j 從 1 遞增到 5，遞增了4次；i 和 j 一起遞增了 5 次
當(dāng) i == 0 時(shí)，i 進(jìn)行了 1 次 i < N 的比較，j 進(jìn)行了 5 次 j < 5 的比較，i 和 j 一起進(jìn)行了 6 次比較

將具體泛化：
a) < 比較 : 離散求和公式：0 + 1 + 2 +...+ N + (N+1) = ?(N+1)(N+2)

         即當(dāng) i == 0 時(shí)，j < N 的比較會(huì)進(jìn)行 N 次，因此總的來說，i 的第一次迭代中**i和j**一起有 N + 1 次比較操作
         而后 i 遞增，對(duì)于 i == 1 的下一次迭代，j < N 進(jìn)行了 N - 1 次，在i的第二次迭代中，**i和j一起**有N次比較操作
         即 i 每加 1，j 都會(huì)在上一層比較的基礎(chǔ)上少比較一次
         直到 i == N, j 不再進(jìn)行比較操作，i 和 j 一共有 1 次比較操作
         i + j 總共進(jìn)行 < N 比較操作的頻率利用離散求和就是?(N+1)(N+2)

b) == 比較 : 離散求和：0 + 1 + 2 +...+ (N-2) + (N-1) = ? N (N ? 1)

         即當(dāng) i == 0 時(shí)，j 將會(huì)迭代 N-1 (從1到N-1) 次
         而后 i == 1 時(shí)，j 將會(huì)迭代 N-2 (從2到N-1) 次
         當(dāng) i == N 時(shí)，j 將不會(huì)再迭代，即 0 次結(jié)束
         即 i 每加 1，j 都會(huì)在上一層迭代的基礎(chǔ)上少迭代一次
         利用離散求和得出 j 的迭代次數(shù)為 ? N (N ? 1)
         j 的 迭代頻率與進(jìn)行“==”比較的操作頻率是一樣的，所判斷相等的操作頻率就等于? N (N ? 1)

c) 數(shù)組訪問 : 假設(shè)我們假設(shè)編譯器/JVM沒有優(yōu)化數(shù)組訪問的情況下

          每次進(jìn)行相等比較都會(huì)有兩次數(shù)組訪問的操作，所以是? N (N ? 1) * 2 = N (N ? 1)

d) 增量{++} : ? N(N+1) to N^2.，coursera上ppt的? N (N ? 1) to N (N ? 1)是錯(cuò)的
Mathematical Models, slide 28, 30, 32. Number of increments should be ? N(N+1) to N^2.
(參見coursera 課程勘誤表Resources--Errata)

         當(dāng) i == 0 時(shí)，i 先進(jìn)行遞增，j 也遞增了 N-1 次，因此總的來說，i 的第一次迭代中**i和j**一起有 N 個(gè)遞增
         然后i遞增，對(duì)于 i == 1 的下一次迭代，j 將遞增 N-2 次，在i的第二次迭代中，**i和j一起**給出N-1個(gè)增量。
         一直到 i == N，**i和j一共**只有一次遞增 (j 不再遞增)
         同樣利用離散求和：N +（N-1）+ ... + 2 + 1，**i和j一起給出** ?N(N+1)個(gè)增量
         下限 : ? N(N+1)（假設(shè)計(jì)數(shù)完全沒有增加，即count沒有增加，只有上訴 i 和 j 進(jìn)行了增量）。
         上限 : 我們假設(shè)計(jì)數(shù)器count在每次循環(huán)都增加，count++執(zhí)行的次數(shù)與“等于比較”的次數(shù)相同，因此我們得到 ? N(N+1) + ? N(N-1) = N^2

第一種簡(jiǎn)化

原則上我們是可以算出這些精確的次數(shù)，可是這樣太繁瑣。圖靈大佬1947年就提出了，其實(shí)我們測(cè)量計(jì)算過程中的工作量時(shí)不用列出所有細(xì)節(jié)，粗略的估計(jì)同樣有用。其實(shí)我們只需要對(duì)開銷最大的操作計(jì)數(shù)就OK了。所以現(xiàn)在我們也這么干。我們選出開銷最大的基本操作，或者是執(zhí)行次數(shù)最多的、開銷最大的、頻率最高的操作來代表執(zhí)行時(shí)間。

我們假設(shè)運(yùn)行時(shí)間等于 常數(shù)*操作的執(zhí)行時(shí)間，在 2-SUM 例子中，
我們選擇訪問數(shù)組的時(shí)間 (c*N(N ? 1)) 代表這個(gè)以上算法的運(yùn)行時(shí)間。

第二種簡(jiǎn)化

-- 估算輸入大小為 N 的函數(shù)的運(yùn)行時(shí)間（或內(nèi)存）
-- 忽略推導(dǎo)式子中的低階項(xiàng)。使用 tilde notation (~ 號(hào))表示：
a) 當(dāng) N 很大時(shí)，我們只需要關(guān)注高階項(xiàng)的開銷
b) 當(dāng) N 很小時(shí)，雖然低階項(xiàng)不能忽略，但是我們更無需擔(dān)心，因?yàn)樾?N 的運(yùn)行時(shí)間本來就不長，我們更想要對(duì)大 N 估計(jì)運(yùn)算時(shí)間

如圖，當(dāng) N 很大時(shí)，N^3 遠(yuǎn)比后邊的 N 的低階項(xiàng)要大得多，大到基本不用關(guān)注低階項(xiàng)，所以這些式子都近似為 (1/6)N^3

通過圖形可以看出低階項(xiàng)真的沒太多影響

波浪號(hào)的含義：f(n) 近似于 g(n) 意味著 f(n)/g(n)的極限等于 1

簡(jiǎn)化統(tǒng)計(jì)頻率后，我們可以這么樣的表示：
是不是看起來更微妙，更清爽~

結(jié)合兩種簡(jiǎn)化，我們就可以說 2-SUM 需要近似 N^2 次數(shù)組訪問，并暗示了運(yùn)行時(shí)間為 ~c*N^2 (c 為常數(shù))
利用開銷模型和 ~ 嘗試對(duì) 3-SUM 問題進(jìn)行分析

3-SUM 為例

public class ThreeSum {
    public static int count(int[] a) {
        int N = a.length;
        int count = 0;
        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++)
                for (int k = j+1; k < N; k++)
                    if (a[i] + a[j] + a[k] == 0)
                        count++;
        return count;
    }
}

開銷最大的就是這句了：if (a[i] + a[j] + a[k] == 0)，我們可以說 3-SUM 問題需要近似 ~ ? n3 次數(shù)組訪問，并暗示了運(yùn)行時(shí)間 ~? c*n3 (c 為常數(shù))

為了避免部分蒙圈現(xiàn)象，解釋下為什么是1/6 N^3 和 1/2 N^3

a) 1/6 N^3 這個(gè)值還是離散求和得出的，可以參考 2-SUM. 就是又多了一層loop. 建議利用計(jì)算器或者工具去計(jì)算
Maple 或者 Wolfram Alpha

b) 因?yàn)?1/6 N^3 是 equal to compare 的次數(shù)，不是數(shù)組訪問的次數(shù)。
每次在執(zhí)行 equal to compare 都有 3 次數(shù)組訪問，所以是 1/6 N^3 * 3 = 1/2 N^3

精確的模型最好還是讓專家?guī)透愣ǎ?jiǎn)化模型也是有價(jià)值的。有時(shí)會(huì)給出一些數(shù)學(xué)證明，但是有時(shí)候引用專家的研究成果，利用數(shù)學(xué)工具就可以了。簡(jiǎn)化后我們就不用去計(jì)算所有操作的開銷，我們選出開銷最大的操作乘上頻率，得出適合的近似模型來描述運(yùn)行時(shí)間。精確一點(diǎn)的數(shù)學(xué)模型如下：
costs：基本操作的開銷，常量，取決于計(jì)算機(jī)，編譯器
frequencies：操作頻率，取決于算法，輸入大小(即 N 的大小)

以下增長量級(jí)同增長階數(shù)一個(gè)意思。

增長量級(jí)可以看做是函數(shù)類型，如是常量，線性函數(shù)，指數(shù)函數(shù)，平方，立方，冪函數(shù)等。
一般分析算法時(shí)我們不會(huì)遇到太多不同的函數(shù)，這樣我們可以將算法按照性能隨問題的大小變化分類。
一般算法我們都能用這幾個(gè)函數(shù)描述：

當(dāng)我們關(guān)注增長量級(jí)時(shí)，我們會(huì)忽略掉函數(shù)前面的常數(shù)。比如當(dāng)我們說這個(gè)算法的運(yùn)行時(shí)間和 NlogN 成正比，等同于我們假設(shè)運(yùn)行時(shí)間近似 cNlogN (c 為常數(shù)).

上圖為雙對(duì)數(shù)坐標(biāo)圖，從圖中可以看出如果：

增長量級(jí)是對(duì)數(shù)(logarithmic)或者常數(shù)(constant)，無論問題的規(guī)模多大，算法的運(yùn)行速度都很快

增長量級(jí)是線性的(linearithmic/linear), 也就是增長量級(jí)與問題大小N成正比，N增長，運(yùn)行時(shí)間也會(huì)隨問題規(guī)模大小線性增長 (NlogN 就是 linearithmic 類型的增長量級(jí))

以上兩種算法都是我們想要設(shè)計(jì)的算法，它們能夠成比例適應(yīng)問題的規(guī)模。

增長量級(jí)為平方階(quadratic),運(yùn)行時(shí)間遠(yuǎn)快于問題輸入的大小，即 N 的大小。這種算法不適合處理龐大問題的輸入。立方階(cubic)的算法就更糟糕

還有一種指數(shù)階算法(exponential),出來龐大輸入也不會(huì)用到

綜上所訴，我們研究算法是，首先要保證這些算法不是平方或者立方階的。
增長階數(shù)類型實(shí)際上就源于我們寫的代碼中的某些簡(jiǎn)單模式。下圖使用翻倍測(cè)試(參考上邊 Doubling hypothesis 內(nèi)容)得出算法運(yùn)行時(shí)間隨問題大小翻倍后增長的翻倍情況。某些增長量級(jí)對(duì)應(yīng)的代碼模式如下：

如果沒有循環(huán)，增長階數(shù)是常數(shù)(constant)，運(yùn)行時(shí)間的增長是常數(shù)的;

如果有某種循環(huán)：

每次循環(huán)被分為兩半(如二分查找算法 binary search)，增長階數(shù)就是對(duì)數(shù)，運(yùn)行時(shí)間的增長幾乎是常數(shù)的

如果遍歷了輸入中的所有對(duì)象，運(yùn)行時(shí)間是線性的(與 N 成正比)，典型的例子是找一個(gè)數(shù)組里頭的最大值，或是上邊提到的 1-SUM 問題

nlogn 線性對(duì)數(shù)階算法，這種時(shí)間復(fù)雜度源于一種特定的算法設(shè)計(jì)技巧叫分治法,如歸并排序(mergesort)，后續(xù)幾周內(nèi)會(huì)有介紹

算法中有兩層for循環(huán)(如 2-SUM)，算法的運(yùn)行時(shí)間是平方階的，和N^2成正比，當(dāng)輸入翻倍后，運(yùn)行時(shí)間增大4倍

三層loop(如 3-SUM)，運(yùn)行時(shí)間就是立方階的，與N^3成正比，當(dāng)輸入翻倍后，運(yùn)行時(shí)間增大8倍

指數(shù)階算法 2^n, 運(yùn)行時(shí)間是指數(shù)階，這些算法中的涉及到的 N 都不會(huì)非常大

通過上述分析，我們?cè)谠O(shè)計(jì)處理巨大規(guī)模輸入的算法的時(shí)候，一般都盡量把算法設(shè)計(jì)成線性階數(shù)和線性對(duì)數(shù)階數(shù)。

為了展示描述算法性能的數(shù)學(xué)模型的建立過程，下邊以 binary search 二分查找為例

目標(biāo)：給定一個(gè)有序整數(shù)數(shù)組，給定一個(gè)值，判斷這個(gè)值在這個(gè)數(shù)組中是否存在，如果存在，它在什么位置

二分查找：將給定值與位于數(shù)組中間的值進(jìn)行比較

比中間值小，向中間值左邊查找

比中間值大，向中間值右邊查找

相等即找到

如下圖，查找 33，首先和 53比較，33<53, 所以如果33存在，那么就會(huì)在數(shù)組的左半邊，然后遞歸地使用同樣的算法，直到找到，或確認(rèn)要查找的值不在給定數(shù)組中。下圖展示二分查找的過程(使用了3個(gè)指針 lo, hi, mid)

初始化 lo 指針指向 id[0], hi 指針指向 id[n-1], mid 指針指向 id[mid]

33<53, hi指針向左移動(dòng)到mid的前一位

33>53, lo 指針向右移動(dòng)到mid的后一位

33<43, hi 指針移動(dòng)到 43 之前，也就是數(shù)組中 33 的位置，此時(shí)只剩下一個(gè)元素查看，如果等于 33，則返回 index 4, 如果不等于 33，則返回 -1,或者別的形式說明要查找的定值不在數(shù)組中

此算法的不變式：如果數(shù)組 a[] 中存在要尋找的關(guān)鍵字，則它在 lo 和 hi 之間的子數(shù)組中, a[lo] ≤ key ≤ a[hi].

public static int binarySearch(int[] a, int key)
{
    int lo = 0, hi = a.length - 1;
    while (lo <= hi)
    {
    //why not mid = (lo + hi) / 2 ?
    int mid = lo + (hi - lo) / 2;
    //關(guān)鍵值與中間值是三項(xiàng)比較(<,>, ==)
    if (key < a[mid]) hi = mid - 1;
    else if (key > a[mid]) lo = mid + 1;
    else return mid;
    }
    return -1;
}

定理：在大小為 N 的有序數(shù)組中完成一次二分查找最多只需要 1 + lgN 次的比較

定義：定義變量 T(N) 表示對(duì)長度為 N 的有序數(shù)組的子數(shù)組(長度<=N)進(jìn)行二分查找所需要的比較次數(shù)

遞推公式(根據(jù)代碼)：T(n) ≤ T(n / 2) + 1 for n > 1, with T(1) = 1.

程序?qū)栴}一分為二，所以T(n) ≤ T(n / 2) 加上一個(gè)數(shù)值，這個(gè)數(shù)值取決于你怎么對(duì)比較計(jì)數(shù)。這里看做二向比較，分成兩半需要進(jìn)行一次比較，所以只要 N>1, 這個(gè)遞推關(guān)系成立。當(dāng) N 為 1 時(shí)，只比較了 1 次。

裂項(xiàng)求和
我們將遞推關(guān)系帶入下面公式右邊(即 <= 號(hào)右邊)求解，
如果T (n) ≤ T (n / 2) + 1 成立，則 T (n / 2) ≤ T (n / 4) + 1 成立...

這個(gè)證明雖然是證明在 N 是 2 的冪的時(shí)候成立，因?yàn)椴]有在遞推關(guān)系中明確 N 是奇數(shù)的情況，但是如果把奇數(shù)情況考慮進(jìn)來，也能夠證明二分查找的運(yùn)行時(shí)間也總是對(duì)數(shù)階的。

基于這個(gè)事實(shí)，我們能夠?qū)?3-SUM 問題設(shè)計(jì)一個(gè)更快的算法：

(基于增長量級(jí)與二分查找應(yīng)用)

Java 實(shí)現(xiàn)：

import java.util.Arrays;

public class ThreeSumFast {

    // Do not instantiate.
    private ThreeSumFast() { }

    // returns true if the sorted array a[] contains any duplicated integers
    private static boolean containsDuplicates(int[] a) {
        for (int i = 1; i < a.length; i++)
            if (a[i] == a[i-1]) return true;
        return false;
    }

    /**
     * Prints to standard output the (i, j, k) with {@code i < j < k}
     * such that {@code a[i] + a[j] + a[k] == 0}.
     *
     * @param a the array of integers
     * @throws IllegalArgumentException if the array contains duplicate integers
     */
    public static void printAll(int[] a) {
        int n = a.length;
        Arrays.sort(a);
        if (containsDuplicates(a)) throw new IllegalArgumentException("array contains duplicate integers");
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int k = Arrays.binarySearch(a, -(a[i] + a[j]));
                if (k > j) StdOut.println(a[i] + " " + a[j] + " " + a[k]);
            }
        }
    } 

    /**
     * Returns the number of triples (i, j, k) with {@code i < j < k}
     * such that {@code a[i] + a[j] + a[k] == 0}.
     *
     * @param a the array of integers
     * @return the number of triples (i, j, k) with {@code i < j < k}
     * such that {@code a[i] + a[j] + a[k] == 0}
     */
    public static int count(int[] a) {
        int n = a.length;
        Arrays.sort(a);
        if (containsDuplicates(a)) throw new IllegalArgumentException("array contains duplicate integers");
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int k = Arrays.binarySearch(a, -(a[i] + a[j]));
                if (k > j) count++;
            }
        }
        return count;
    } 

    /**
     * Reads in a sequence of distinct integers from a file, specified as a command-line argument;
     * counts the number of triples sum to exactly zero; prints out the time to perform
     * the computation.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args)  { 
        In in = new In(args[0]);
        int[] a = in.readAllInts();
        int count = count(a);
        StdOut.println(count);
    } 
} 

基于搜索的算法：

第一步: 將輸入中的數(shù)進(jìn)行排序(排序算法后邊會(huì)做介紹)

第二步: 查看每對(duì)數(shù)字 a[i] 和 a[j], 對(duì) - (a[i] + a[j]) 進(jìn)行二分查找.

如果找到- (a[i] + a[j])，那么就有 a[i], a[j] 和 - (a[i] + a[j]) 三個(gè)整數(shù)和為 0

運(yùn)行時(shí)間的增長階數(shù): N^2 log N.

第一步: 排序需要正比于 N^2(如果使用插入排序, N^2的數(shù)組訪問還是好理解的，兩層loops).

第二步: 二分查找使用 N^2 log N

主要看這里：

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int k = Arrays.binarySearch(a, -(a[i] + a[j]));
                if (k > j) count++;
            }
        }

    第2步進(jìn)行多次二分搜索。多少次？ N ^ 2次。二分查找需要log(n)時(shí)間 (請(qǐng)參考概述中最后一個(gè)表和回顧二分查找的內(nèi)容)。
    因此，循環(huán)需要（N ^ 2 * log（N））時(shí)間。
    應(yīng)該注意循環(huán)在排序后發(fā)生。不在排序過程中發(fā)生。由于操作一個(gè)接一個(gè)地發(fā)生，我們添加了運(yùn)行時(shí)間。不是成倍增加。

    **總運(yùn)行時(shí)間是這樣的**：
    （N ^ 2）+（N ^ 2 * log（N））

    **由于忽略了較低階項(xiàng)**，因此算法只有最重要的項(xiàng)的增長順序：
    （N ^ 2 * log（N））

通常，更好的增長階數(shù)意味著程序在實(shí)際運(yùn)行中更快。
為了更有說服力，一般情況下不考慮上下限問題，運(yùn)行時(shí)間為最壞情況下的時(shí)間復(fù)雜度 (算法理論內(nèi)容)

增長量級(jí)在實(shí)際運(yùn)用在是非常重要的，它直接反映了算法的效率，近年來人們針對(duì)增長量級(jí)也做了很多研究。

一個(gè)不同的輸入可能會(huì)讓算法的性能發(fā)生巨大變化。我們需要從不同的角度針對(duì)輸入的大小分析算法。運(yùn)行時(shí)間介于最好情況與最壞情況之間。

Best case：最好情況，算法代價(jià)的下限(lower bound on cost), 運(yùn)行時(shí)間總是大于或等于下限。

由“最簡(jiǎn)單”的輸入決定

為所有輸入情況提供目標(biāo) (應(yīng)對(duì)所有輸入，希望運(yùn)行時(shí)間能夠是或者接近最好情況)

Worst case：最糟糕的情況，算法代價(jià)的上限(Upper bound on cost), 運(yùn)行時(shí)間不會(huì)長于上限。

由“最復(fù)雜”的輸入決定

為所有輸入提供擔(dān)保 (最壞的情況的分析結(jié)果為我們提供底線，算法運(yùn)行時(shí)間不會(huì)長于這種情況)

Average case：平均隨機(jī)情況，將輸入認(rèn)為是隨機(jī)的

需要以某種方式對(duì)問題中的隨機(jī)輸入進(jìn)行建模

提供預(yù)測(cè)性能的方法

一般的，即使輸入變化非常大，我們也能夠各種情況進(jìn)行建模和預(yù)測(cè)性能

Ex 1. 如上邊的 3-SUM 問題：
通過“暴力算法”，數(shù)組的訪問次數(shù)為
Best: ~ ? N^3
Average: ~ ? N^3
Worst: ~ ? N^3
其實(shí)各種情況的低階項(xiàng)是不一樣的，但是因?yàn)槲覀兝昧撕?jiǎn)化方法忽略了低階項(xiàng)(回顧數(shù)學(xué)表示的簡(jiǎn)化內(nèi)容)，所以3種情況下的數(shù)組訪問幾乎是一樣的。使用近似表達(dá)時(shí)，算法中唯一的變化就是計(jì)數(shù)器 count 增加的次數(shù)。

Ex 2. 二分查找中的比較次數(shù)
Best: ~ 1 常數(shù)時(shí)間，第一次比較結(jié)束后就找到了關(guān)鍵字
Average: ~ lg N
Worst: ~ lg N

應(yīng)對(duì)不同的輸入，我們有不同的類型分析，但是關(guān)鍵是客戶要解決的實(shí)際問題是什么。為了了解算法的性能，我們也要了解這個(gè)問題。

實(shí)際數(shù)據(jù)可能與輸入模型不匹配怎么辦？

需要了解輸入以有效地處理它

方法1：取決于最壞情況下的性能保證，保證你的算法在最壞情況下運(yùn)行也能很快

示例：使用歸并排序 Mergesort 而不是快速排序 Quicksort

如果不能保證最壞情況，那么就考慮隨機(jī)情況，依靠某種概率條件下成立的保證

方法2：隨機(jī)化，取決于概率保證。

示例：Quicksort

(排序在后幾個(gè)星期有談?wù)摰?

對(duì)于增長量級(jí)的討論引出了對(duì)算法理論的討論

新目標(biāo)

確定問題的“困難性”

例如 3-SUM 有多難？

開發(fā)“最優(yōu)”算法解決問題

方法
用增長量級(jí)對(duì)最壞情況進(jìn)行描述

在分析中試著去掉盡可能多的細(xì)節(jié)，將分析做到只差一個(gè)常數(shù)倍數(shù)的精度，這就是上邊所說到的利用增長量級(jí)分析的方法

通過關(guān)注最壞的情況，完全忽略輸入模型，消除輸入模型的可變性，把重點(diǎn)放在針對(duì)最壞情況的設(shè)計(jì)方法上，這樣就能簡(jiǎn)便地只利用增長階數(shù)來談?wù)撍惴ㄐ阅?/p>

分析的目標(biāo)是找出“最優(yōu)”算法

最優(yōu)算法

對(duì)于任意輸入，我們能將運(yùn)行時(shí)間的浮動(dòng)控制在一個(gè)常數(shù)之內(nèi)。

因?yàn)槭轻槍?duì)最壞情況考慮，所以提出的算法也就證明了除了它以外，沒有其它的算法提供更好的性能保證了，這個(gè)算法就是“最優(yōu)的”

如何使用這三個(gè)符號(hào)對(duì)算法按照性能分類？

目標(biāo)：確定問題的“難度”并開發(fā)“最優(yōu)”算法。

EX. 1-SUM 問題：數(shù)組中是否有0？

上限：O(g(N)) 問題難度的上限取決于某個(gè)特定的算法

EX. 1-SUM的暴力算法：查看每個(gè)數(shù)組元素

暴力算法的運(yùn)行時(shí)間為 Θ(N)

1-SUM 問題未知的最優(yōu)算法的運(yùn)行時(shí)間是 O(N):

這里的 g(N)=N，重復(fù)一次，Θ(N) 表示某個(gè)常數(shù)*N。暴力算法已經(jīng)表明解決 1-SUM 問題需要 Θ(N) 的時(shí)間，那么如果存在最優(yōu)算法，運(yùn)行時(shí)間肯定是 ≤ Θ(N), 根據(jù)上表，≤ Θ(N) 用 O(N) 表示

下限：Ω(h(N)) 證明沒有算法可以做得比 Θ(h(N)) 更好了

Ex. 必須檢查所有N個(gè)數(shù)組里頭的元素（任何未經(jīng)檢查的條目都可能為0）

1-SUM 的未知最優(yōu)算法的運(yùn)行時(shí)間是 Ω(N)

這里 h(N) = N，因?yàn)楸仨殭z查所有項(xiàng)，沒有別的算法可以做到比暴力算法 Θ(N) 更好了，所以 1-SUM 的未知最優(yōu)算法的運(yùn)行時(shí)間是肯定都是 ≥ Θ(N) 的，記作 Ω(N)

最優(yōu)算法：

下限等于上限：g（N）= h（N）= N

Ex. 1-SUM 的暴力算法是最優(yōu)的：其運(yùn)行時(shí)間是 Θ(N)。

對(duì)于簡(jiǎn)單問題，找到最優(yōu)算法還是比較簡(jiǎn)單的，但對(duì)于很復(fù)雜的問題，確定上下限就很困難，確定上下界吻合就更加困難。

目標(biāo)

確定問題的“難度”并開發(fā)“最優(yōu)”算法。

Ex. 3-SUM: 數(shù)組中，三個(gè)數(shù)和為 0 出現(xiàn)多少次

暴力算法分析

上限: 問題難度的上限取決于某個(gè)特定的算法

Ex. 3-SUM 的暴力算法

3-SUM 的最優(yōu)算法的運(yùn)行時(shí)間為 O(N^3)

3-SUM 的的暴力算法需要的運(yùn)行時(shí)間是 Θ(N^3),如果存在某種算法比暴力算法更優(yōu)，那么運(yùn)行時(shí)間肯定 ≤ Θ(N^3), 記作 O(N^3)

但如果我們找到了更好的算法

上限: 一種特定的改進(jìn)算法

Ex. 改進(jìn)的 3-SUM 算法

3-SUM 最優(yōu)算法的運(yùn)行時(shí)間為 O(N^2*logN) {使用了二分查找}

下限: 證明沒有別的算法可以做得更好

Ex. 必須檢查所有N個(gè)條目以解決 3-SUM 問題

求解 3-SUM 的最優(yōu)算法的運(yùn)行時(shí)間為 Ω(N)

可能大家還是對(duì)Omega Ω 符號(hào)有點(diǎn)困惑。 Omega只顯示算法復(fù)雜度的下限。 3-SUM 算法需要檢查來自某個(gè)數(shù)組的所有元素，因此我們可以說，該算法具有 Ω(N) 復(fù)雜度，因?yàn)樗辽賵?zhí)行線性數(shù)量的操作。事實(shí)上，操作總數(shù)是更大的，因此實(shí)際最優(yōu)算法肯定是 ≥ Θ(N) 的，記作 Ω(N)

對(duì)于 3-SUM 問題沒有人知道更高的下界，其實(shí)我們現(xiàn)在就能看出，處理 3-SUM 問題肯定是要用超過 Θ(N) 的時(shí)間的，但是我們卻不能確定多出多少，就是不知道比 Θ(N) 更高的下界是多少。
當(dāng)有人證明更高的下限時(shí)，也是同意沒有算法可以做得比前一個(gè)下限更好的前提下提出新的下界。但是他們會(huì)做出了更強(qiáng)有力的陳述，特別是證明沒有算法可以實(shí)現(xiàn)比他們剛才證明的新下界更好，以此來提高原來的下界，定義一個(gè)新的下界。

新的下限可能僅略高于先前的下限，或者可能顯著更高。提高下界往往都不是很容易。談?wù)撊绾翁岣呦陆邕@也不是本文的重點(diǎn)。

算法理論中的一個(gè)開放問題：
·3-SUM 有最優(yōu)算法嗎？我們不知道
·3-SUM 問題是否存在一個(gè)運(yùn)行時(shí)間小于 O(N^2) 的算法？我們無法確定
·3-SUM 比現(xiàn)行的下界更高的下界是什么，上面已經(jīng)談?wù)撨^了，我們也還不知道
我們不知道求解 3-SUM 問題的難度

遇到新的問題，設(shè)計(jì)出某個(gè)算法，并證明它的下界

如果上界和下界存在間隔，那么尋找新的能夠降低上界的算法，或者是尋找提高下界的方法(但是這個(gè)一般很難)

所以人們更傾向于研究持續(xù)下降上界，也就是設(shè)法提高算法在最壞情況下的運(yùn)行時(shí)間來了解問題的難度，并得到了很多最壞情況下的最優(yōu)算法。

這門課程并不會(huì)把注意點(diǎn)都放在關(guān)注最壞的情況去分析算法性能，而是專注于理解輸入的性質(zhì)(不一定是最糟糕的情況)，并針對(duì)輸入的性質(zhì)尋找最高效的算法

真的要預(yù)測(cè)性能和比較算法時(shí)，我們需要比常數(shù)因子級(jí)別誤差更準(zhǔn)確的分析

值得注意的是：有很多人錯(cuò)把 big-Oh 分析結(jié)果當(dāng)做了運(yùn)行時(shí)間的近似模型，其實(shí) big-Oh 應(yīng)該是這個(gè)問題運(yùn)行時(shí)間的上界，不是運(yùn)行時(shí)間的近似模型。
我們使用 ~ 來表示算法運(yùn)行時(shí)間的近似模型。當(dāng)我們談?wù)摰竭\(yùn)行時(shí)間的上界就使用 big-Oh.

運(yùn)行時(shí)間和程序的內(nèi)存需求都會(huì)對(duì)算法的性能有所影響，下邊是對(duì)內(nèi)存需求的簡(jiǎn)單討論。
從根本上講我們就是想知道程序?qū)W要多少比特(bit)，或者多少字節(jié)(byte)

Bit: 0 or 1
Byte: 8 bites 
Megabyte (MB) 2^20 bytes
Gigabyte (GB) 2^30 bytes.

32-bit machine: 32 位系統(tǒng)，指針是 4 個(gè)字節(jié)，
64-bit machine: 64 位系統(tǒng)，指針是 8 個(gè)字節(jié)，這使得我們能夠?qū)艽蟮膬?nèi)存尋址，但是指針指針也使用了更大的空間。有些 JVM 把指針壓縮到 4 bytes 來節(jié)省開支。    

內(nèi)存使用和機(jī)器還有硬件實(shí)現(xiàn)有很大的關(guān)系，但是一般情況都是如圖所示

Boolean 雖然只用了 1 bit，但系統(tǒng)還是分配了 1 byte 給它
數(shù)組需要額外空間 + 基本類型空間開支(參考左表) * 元素個(gè)數(shù)(N)
二維數(shù)組需要的空間下圖用近似值表示， ~ 2MN 可以理解為 char 基本類型開銷是 2 bytes，char [M] [N] 近似用了 2MN bytes 的內(nèi)存

Object overhead 對(duì)象需要的額外空間. 16 bytes.
Reference 引用. 8 bytes.
Padding 內(nèi)置用來對(duì)齊的空間. 對(duì)齊空間可以是 4 bytes 或者是其它，對(duì)齊空間的分配目的是使得每個(gè)對(duì)象使用的空間都是 8 bytes 的倍數(shù)

下圖是一個(gè)日期對(duì)象的內(nèi)存占用量例子

數(shù)據(jù)類型值的總內(nèi)存使用量：

基本數(shù)據(jù)類型：int 為 4 字節(jié)，double 為 8 字節(jié)，...

對(duì)象引用：8個(gè)字節(jié)，這是指針需要占用的空間

數(shù)組：24 個(gè)字節(jié) + 每一項(xiàng)的內(nèi)存。

對(duì)象：16 個(gè)字節(jié) + 實(shí)例變量的空間 ( + 8個(gè)字節(jié)，如果有內(nèi)部類對(duì)象)

對(duì)齊空間：增加一定量字節(jié)，使得上邊的字節(jié)加上這里的字節(jié)數(shù)和為 8 個(gè)字節(jié)的倍數(shù)

例子：用了多少字節(jié)？

使用上邊的基本知識(shí)可以算出 B

對(duì)象的額外空間 16 bytes (參考日期對(duì)象用例)

int[] id：8 byte + ( 4N + 24 )

int[] sz：同上 (引用 + 24 個(gè)字節(jié) + int 類型開銷 * N)

int count：4 bytes

對(duì)齊空間：4 byte

總共 8N + 88 ~ 8 N bytes.

大意解釋待更新...

大意解釋待更新...

大意解釋待更新...

Version 0: Try each flow from the bottom. The first floor that the egg breaks on is the value of T.

Version 1: Using the binary search.Firstly, try floor T/2. If the egg breaks, T must be equal to T/2 or smaller.
If the egg does not break, T must be greater than T/2. Continue testing the mid-point of the subset of floors
until T is determined.

Version 2: Start test at floor 1 and exponentially grow (2^t) floor number (1, 2, 4, 8 ... 2^t)until first egg
breaks. The value of T must be in [2^(t-1), 2^t). This step costs lgT tosses. Then in the range got from last
step can be searched in ~lgT tosses using the binary search. Two step will cost ~2lgT tosses.

Version 3: Test floors in increments of sqrt(N) starting from the first floor.
{e.g: {1, sqrt(N), 2*sqrt(N), 3*sqrt(N)...t*sqrt(N)...}. When the egg breaks on t, test floor from (t-1)*sqrt(N)
and increment by each floor.
The remaining sqrt(N){e.g [(t-1)*sqrt(N), t*sqrt(N))} tests will be enough to check each floor between floor t-1
and t. The floor that breaks will be the value of T.

Version 4: Start test at floor 1 in increments of t^2 (e.g {1,4,9...t^2..N}), When the egg breaks on t, test
floor from (t-1)^2+1 and increment by each floor.