T(N)=aN^b? ? ? ? ? ? 冪次法則

三 數(shù)學(xué)模型

一個(gè)程序運(yùn)行的總時(shí)間主要與兩點(diǎn)有關(guān): 執(zhí)行每條語(yǔ)句的耗時(shí)；

執(zhí)行每條語(yǔ)句的頻率。

前者取決于計(jì)算機(jī)、Java編譯器和操作系統(tǒng)，后者取決于程序本身和輸入。

排列：

排列公式是建立一個(gè)模型，從n個(gè)不相同元素中取出m個(gè)排成一列（有序），第一個(gè)位置可以有n個(gè)選擇，第二個(gè)位置可以有n-1個(gè)選擇（已經(jīng)有1個(gè)放在前一個(gè)位置），則同理可知第三個(gè)位置可以有n-2個(gè)選擇，以此類推第m個(gè)位置可以有n-m+1個(gè)選擇，則排列數(shù)A(n m)=n*(n-1)*(n-2)...*(n-m+1)

由階乘的定義可知A(n m)=[n*(n-1)*(n-2)...*(n-m+1)]*[(n-m)*(n-m-1)...*1]/[(n-m)*(n-m-1)...*1]

上下合并可得A(n m)=n!/(n-m)!

組合：

組合公式對(duì)應(yīng)另一個(gè)模型,從n個(gè)不相同元素中取出m個(gè)排成一列（無(wú)序），可以先考慮排列A(n m)，由于m個(gè)元素組成的一組可以有m!種不同的排列（全排列A(m m) = m!），所以組合的總數(shù)就是A(n m)/m!，即為C(n m) = A(n m)/m! = n![m!(n-m)!]

數(shù)學(xué)歸納法證明 C(N，3) = N(N-1)(N-2)/6

當(dāng)N = 3時(shí)，cnt = 3*(3-1)*(3-2)/6 = 1成立

當(dāng)N=4，5，6......N時(shí)，cnt(N) = N(N-1)(N-2)/6 均成立。

則當(dāng)N=N+1時(shí)，先取其中N個(gè)數(shù)，可以有cnt(N)，

再?gòu)倪@N個(gè)數(shù)中取兩個(gè)數(shù)與余下一個(gè)組合，則共有N(N-1)/2（排列組合），

所以cnt(N+1) = cnt(N) + N(N-1)

『大O』：這種在描述算法性能的漸進(jìn)上限時(shí)十分有用，這在算法理論領(lǐng)域十分重要，但在預(yù)測(cè)算法性能或是比較算法時(shí)并沒(méi)有什么用。（上界）

因?yàn)樗枋龅膬H僅是運(yùn)行時(shí)間的上限，而算法的實(shí)際性能可能要好的多。一個(gè)算法的運(yùn)行時(shí)間可能既是O(N^2)也是~aNlogN的。因此，它不能解釋類似倍率實(shí)驗(yàn)等測(cè)試。

為什么應(yīng)用這么廣泛？

因?yàn)樗?jiǎn)化了對(duì)增長(zhǎng)數(shù)量級(jí)的上限的研究，甚至也適用于一些無(wú)法進(jìn)行精確分析的復(fù)雜算法。另外，它還可以和計(jì)算理論中用于將算法按照它們?cè)谧顗那闆r下的性能分類的”大Omega”和”大Theta"符號(hào)一起使用。

Ω用來(lái)表示最壞情況下的性能下限。（最快—下界）

Θ用于描述算法的最佳性能，即不存在有更好的最壞情況下的漸進(jìn)增長(zhǎng)數(shù)量級(jí)的算法。算法的最優(yōu)性顯然是實(shí)際應(yīng)用中值得考慮的一點(diǎn)，但是還有其他許多因素要考慮。（確界）

為什么都用大O，不用大Θ

我猜想原因之一是我們?cè)趫?zhí)行一個(gè)算法的時(shí)候往往不知道輸入的分布情況。所以考慮最壞情況比考慮一個(gè)（假設(shè)輸入程均勻分布下的）平均資源消耗更有意義。

我猜想另一個(gè)原因是，大O，能保證算法可行與否。

3.1 近似

3.5 成本模型

暴力算法：利用枚舉所有的情況，或者其它大量運(yùn)算又不用技巧的方式，來(lái)求解問(wèn)題的方法。

(實(shí)現(xiàn)并分析該問(wèn)題的一種簡(jiǎn)單的解法。)

總結(jié)

五 設(shè)計(jì)更快的算法

5.1 熱身運(yùn)動(dòng) 2-sum

分治法：分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

六 倍率實(shí)驗(yàn)

6.1 評(píng)估它解決大型問(wèn)題的可行性

6.2 評(píng)估使用更快的計(jì)算機(jī)所產(chǎn)生的價(jià)值

七 注意事項(xiàng)

1.大常數(shù)

2.非決定性的內(nèi)循環(huán)

3.指令時(shí)間

4.系統(tǒng)因素

5.對(duì)輸入的強(qiáng)烈依賴

6.多個(gè)問(wèn)題參量

八 處理對(duì)于輸入的依賴

8.5 均攤分析

通過(guò)記錄所有操作的總成本并除以操作總數(shù)來(lái)將成本均攤。

九 內(nèi)存

典型的的Java實(shí)現(xiàn)使用8位表示一個(gè)字節(jié)，用2字節(jié)（16位）表示一個(gè)char值，用4字節(jié)（32位）表示一個(gè)int值，用8字節(jié)（64位）表示一個(gè)double或者long值，用1字節(jié)表示一個(gè)boolean值（因?yàn)橛?jì)算機(jī)訪問(wèn)內(nèi)存的方式都是一次1字節(jié)）

9.1 對(duì)象

一個(gè)對(duì)象所使用的內(nèi)存量，需要將所有實(shí)例變量使用的內(nèi)存與對(duì)象本身的開(kāi)銷（一般是16字節(jié)）相加。

這些開(kāi)銷包括一個(gè)指向?qū)ο蟮念惖囊?、垃圾收集信息以及同步信息?/p>

另外，一般內(nèi)存的使用都會(huì)被填充為8字節(jié)（64位計(jì)算機(jī)中的機(jī)器字）的倍數(shù)。

對(duì)象的引用一般都是一個(gè)內(nèi)存地址，因此會(huì)使用8字節(jié)。

9.2 鏈表

一個(gè)Stack對(duì)象32字節(jié)，一個(gè)node對(duì)象40字節(jié)，一個(gè)Integer對(duì)象24字節(jié)

9.3 數(shù)組

Java中數(shù)組被實(shí)現(xiàn)為對(duì)象，它們一般會(huì)因?yàn)橛涗涢L(zhǎng)度而需要額外的內(nèi)存。

一個(gè)原始數(shù)據(jù)類型的數(shù)組一般需要24字節(jié)的頭信息（16字節(jié)的對(duì)象開(kāi)銷，4字節(jié)用于保存長(zhǎng)度以及4字節(jié)填充字）再加上保存值所需的內(nèi)存。

例如，一個(gè)含有N個(gè)int值的數(shù)組需要使用（24+4N）字節(jié)（會(huì)被填充為8的倍數(shù)）

一個(gè)含有N個(gè)double值的數(shù)組需要使用（24+8N）字節(jié)

一個(gè)對(duì)象的數(shù)組就是一個(gè)對(duì)象的引用的數(shù)組，所以我們應(yīng)該在對(duì)象所需的內(nèi)存之外加上引用所需的內(nèi)存。

例如，一個(gè)含有N個(gè)Date對(duì)象的數(shù)組需要使用24字節(jié)（數(shù)組開(kāi)銷）加上8N字節(jié)（所有引用）加上每個(gè)對(duì)象的32字節(jié)，總共（24+40N）字節(jié)。

二維數(shù)組是一個(gè)數(shù)組的數(shù)組（每個(gè)數(shù)組都是一個(gè)對(duì)象）。

例如，一個(gè)M*N的double類型的二維數(shù)組需要使用24字節(jié)（數(shù)組的數(shù)組的開(kāi)銷）加上8M字節(jié)（所有元素?cái)?shù)組的引用）加上24M字節(jié)（所有元素?cái)?shù)組的開(kāi)銷）加上8MN字節(jié)（M個(gè)長(zhǎng)度為N的double類型的數(shù)組），總共（8MN+32M+24）~8MN字節(jié)。

9.4 字符串對(duì)象

String的標(biāo)準(zhǔn)實(shí)現(xiàn)含有4個(gè)實(shí)例變量：一個(gè)指向字符數(shù)組的引用（8字節(jié)）和三個(gè)int值（各4字節(jié)）。

第一個(gè)int值描述的是字符數(shù)組中的偏移量。

第二個(gè)int值是一個(gè)計(jì)數(shù)器（字符串的長(zhǎng)度）。對(duì)象所表示的字符串由value[offset]到value[offset+count-1]中的字符組成。

第三個(gè)int值是一個(gè)散列值，它在某些情況下可以節(jié)省一些計(jì)算，現(xiàn)在先忽略它。

因此每個(gè)String對(duì)象總共會(huì)使用40字節(jié)（16字節(jié)表示對(duì)象，三個(gè)int實(shí)例變量各需4個(gè)字節(jié)，加上數(shù)組引用的8字節(jié)和4個(gè)填充字節(jié)）

這是除字符數(shù)組之外字符串所需的內(nèi)存空間，所有字符所需的內(nèi)存需要另計(jì)。

（因?yàn)镾tring的char數(shù)組常常在多個(gè)字符串之間共享）這種設(shè)計(jì)使String的實(shí)現(xiàn)在能夠在多個(gè)對(duì)象都含有相同的value[]數(shù)組時(shí)節(jié)省內(nèi)存。

9.5 字符串的值和子字符串

一個(gè)長(zhǎng)度為N的String對(duì)象一般需要使用40字節(jié)（String對(duì)象本身）加上（24+2N）字節(jié)（字符數(shù)組），總共（64+2N）字節(jié)。

當(dāng)你調(diào)用substring()方法時(shí)，就創(chuàng)建了一個(gè)新的String對(duì)象（40字節(jié)），但它依然重用了相同的value[]數(shù)組，因此該字符串的子字符串只會(huì)使用40字節(jié)的內(nèi)存。