- 科學(xué)方法:(一種科學(xué)家用來理解自然世界的方法)
- 觀察(根據(jù)一定的步驟,來研究將問題規(guī)模和運(yùn)行時(shí)間的關(guān)系量化):
- 舉例(可以說是構(gòu)造一個(gè)實(shí)驗(yàn))
- 工具(比如說一個(gè)計(jì)時(shí)器,來記錄某個(gè)實(shí)驗(yàn)的過程數(shù)據(jù))
- 實(shí)驗(yàn)數(shù)據(jù)的分析:
- 1-圖像分析(畫圖猜想)
- 數(shù)學(xué)模型(構(gòu)造一個(gè)數(shù)學(xué)模型來描述程序的運(yùn)行時(shí)間:執(zhí)行每條語句的耗時(shí)和執(zhí)行每條語句的頻率)
- 近似頻率(忽略低次項(xiàng))
- 近似運(yùn)行時(shí)間(對每塊代碼塊分塊估算時(shí)間)
- 算法分析的意義(經(jīng)典算法理論大部分發(fā)表于數(shù)十年前,但依舊適用于今天的計(jì)算機(jī))
- 成本模型(一個(gè)衡量算法性能的指標(biāo)
- 總結(jié)(得到其運(yùn)行時(shí)間的數(shù)學(xué)模型所需步驟):
- 確定輸入模型,定義問題的規(guī)模
- 識別內(nèi)循環(huán)
- 根據(jù)內(nèi)循環(huán)中的操作確定成本模型
- 對于給定的輸入,判斷這些操作的執(zhí)行頻率.這可能需要進(jìn)行數(shù)學(xué)分析(學(xué)習(xí)具體算法的時(shí)候有例子)
tip:數(shù)學(xué)中的常見函數(shù),包括(向下取整,向上取整,自然對數(shù),以2為底的對數(shù),以2為底的對數(shù)想下取整,調(diào)和級數(shù)??,階乘)
數(shù)學(xué)中的常見近似函數(shù),包括(調(diào)和級數(shù)求和??,等差數(shù)列求和,等比數(shù)列求和,斯特靈公式??,二項(xiàng)式系數(shù),指數(shù)函數(shù))
-
增長數(shù)量級的分類:
圖片.png -
設(shè)計(jì)更快的算法(一般步驟):
- 實(shí)現(xiàn)并分析該問題的一種簡單算法,通常稱為暴力算法
- 考查算法的各種改進(jìn)
- 用實(shí)驗(yàn)證明新的算法更快
tip:對于實(shí)際問題來說,運(yùn)行時(shí)間只是選擇算法時(shí)所考慮的各種因素之一.
- 倍率實(shí)驗(yàn)(簡單有效的預(yù)測任意程序的性能葵第，并判斷它們的運(yùn)行時(shí)間大致的增長數(shù)量級):
- 開發(fā)一個(gè)輸入生成器來產(chǎn)生實(shí)際情況下的各種 可能的輸入
- 開發(fā)一個(gè)程序,能夠計(jì)算每次實(shí)驗(yàn)和上次實(shí)驗(yàn)的運(yùn)行時(shí)間的比值
- 反復(fù)運(yùn)行,直到該比值趨近于極限 2^x (對于比值沒有極限的算法無效)
- 這個(gè)程序的運(yùn)行時(shí)間的增長數(shù)量級約為 N^x
有一個(gè)疑問,假如增長數(shù)量級是對數(shù)級的呢?
- 猜想①:logN級別的數(shù)量級對比N^x數(shù)量級,會小很多,可能會被忽略;
- 猜想②:可以將第3)步的極限解釋為有l(wèi)ogN的可能性[ logN / log (N/2) = logN/(logN-1)],即比值趨近于 2^x * [logN/(logN-1)],對應(yīng)的 增長數(shù)量級 約為 N^x * logN
書中的背后一頁用倍率公式解釋了我的上述疑問,即 如果 T(N) ~ a(N^b)(logN) ,那么T(2N)/T(N) ~ 2^b
一般來說,在數(shù)學(xué)模型中,對數(shù)項(xiàng)是不能忽略的,但在倍率假設(shè)中,它在預(yù)測性能的公式中,顯得不是很重要
倍率實(shí)驗(yàn)的作用:
- 評估算法解決大型問題的可行性
- 評估使用更快的的計(jì)算機(jī)所產(chǎn)生的價(jià)值
解釋一下表1.4.9:
- 系數(shù)為2、系數(shù)為10 這兩列以下的數(shù)據(jù)的意思指的是 當(dāng)輸入規(guī)模增長2\10倍時(shí),算法運(yùn)行時(shí)間增長了多少倍.(比如平方級別增長了8\1000倍)
- 注意事項(xiàng):
- 大常數(shù)：忽略低次項(xiàng)的常數(shù)系數(shù)合溺，有可能是錯(cuò)誤的
- 非決定性的內(nèi)循環(huán)：成本模型不能只考慮內(nèi)循環(huán)卒密，內(nèi)循環(huán)外也有大量指令需要考慮。成本模型可能需要改進(jìn)棠赛。
- 指令時(shí)間：每條指令的執(zhí)行時(shí)間不一定相同哮奇。
- 系統(tǒng)因素：系統(tǒng)能夠大大的影響程序性能。
- 兩個(gè)不分伯仲的程序：這兩個(gè)程序可能各有優(yōu)劣恭朗，最佳實(shí)現(xiàn)不一定有必要找出來。
- 對輸入的強(qiáng)烈依賴依疼，運(yùn)行時(shí)間和輸入不一定是無關(guān)的痰腮。
- 多個(gè)問題參量：可能存在多個(gè)變量影響著程序的性能。
- 綜上所述：有效近似的估算出任何程序所需的運(yùn)行時(shí)間律罢，就足夠了膀值。
- 處理對輸入的依賴：
- 對我們所要解決的問題的輸入建模棍丐。讓輸入模型更加切合實(shí)際。***個(gè)人理解：輸入不一定要很復(fù)雜沧踏，只要能夠分析程序的性能歌逢，簡單反而更好。
- 對最壞情況下的性能的保證翘狱。從極度悲觀的角度來估算算法的性能秘案。
- 隨機(jī)化算法。對輸入隨機(jī)化潦匈。
- 操作的順序阱高。算法的“輸入”可能不只是數(shù)據(jù)，還有可能是一系列操作的順序茬缩。
- 均攤分析赤惊。所有操作的總成本除于操作總數(shù)將成本均攤。我們可以允許執(zhí)行一些昂貴的操作凰锡，但是所有操作的平均成本較低未舟，也是可以接受的。
- 內(nèi)存
tip：一般內(nèi)存的使用都會被填充為8字節(jié)的倍數(shù)掂为。
* 原始數(shù)據(jù)所需內(nèi)存：
類型
字節(jié)（每個(gè)字節(jié)8位）
圖片.png
- 對象：
所有實(shí)例變量使用的內(nèi)存+對象本身的開銷（一般是16字節(jié)裕膀，包括一個(gè)指向?qū)ο蟮念惖囊谩⒗占畔⑵刑汀⑼叫畔ⅲ?br> 例如：一個(gè)Integer對象會使用24字節(jié)（16字節(jié)的對象開銷魂角，4字節(jié)保存它的int值，4個(gè)填充字節(jié)） - 鏈表
嵌套的非靜態(tài)類（內(nèi)部類）智绸。在普通對象的基礎(chǔ)上還需要一個(gè)指向外部類的引用（8字節(jié)） - 數(shù)組：
- 原始類型的數(shù)組：一般需要24字節(jié)的頭信息（16字節(jié)的對象開銷野揪，4字節(jié)用于保存長度、4填充字節(jié)）+保存值所需的內(nèi)存瞧栗。
- 例如：一個(gè)有N個(gè)int值的數(shù)組需要使用（24+4N）字節(jié)（會被填充為8的倍數(shù)斯稳。
- 對象的數(shù)組：其實(shí)就是一個(gè)對象引用的數(shù)組，所以我們應(yīng)該在對象所需內(nèi)存外加上引用所需的內(nèi)存迹恐。
- 例如：一個(gè)含有N個(gè)Integer對象的數(shù)組需要24字節(jié)（數(shù)組開銷）+8N字節(jié)（所有引用）+32N字節(jié)（所有對象所需內(nèi)存）=24+40N字節(jié)
- 例如2：一個(gè)含有MN個(gè)int值的二維數(shù)組需要 24字節(jié)（二維數(shù)組的開銷）加上8M字節(jié)（所有元素?cái)?shù)組的引用）加上(24+4N)M（所有元素?cái)?shù)組的 占用見上面第（1）點(diǎn)）
- 原始類型的數(shù)組：一般需要24字節(jié)的頭信息（16字節(jié)的對象開銷野揪，4字節(jié)用于保存長度、4填充字節(jié)）+保存值所需的內(nèi)存瞧栗。
- 字符串對象：
一個(gè)指向字符數(shù)組的引用（8字節(jié)）挣惰、3個(gè)int值（共12字節(jié)）（第一個(gè)int是字符數(shù)組中的偏移量、第二個(gè)int是字符串的長度殴边、第三個(gè)int是散列值）憎茂、對象本 身的消耗（16字節(jié)）以及4個(gè)填充字節(jié)；除此之外锤岸，還要加上字符數(shù)組所需的內(nèi)存空間竖幔。 - 子字符串（java實(shí)現(xiàn)）subString()：
其實(shí)只是修改了字符串對象中的三個(gè)int值。 - 注意避免最常見的兩大錯(cuò)誤是偷。
- 過于關(guān)注程序的性能拳氢。我們的首要任務(wù)應(yīng)該是寫成清晰正確的代碼募逞。而且要考慮生產(chǎn)效率。如果算法本身就很快馋评，或者調(diào)試一個(gè)新算法時(shí)間遠(yuǎn)遠(yuǎn)超于直 接運(yùn)行一個(gè)稍慢的程序放接，又或者花了大量時(shí)間精力去實(shí)現(xiàn)一個(gè)理論上能改進(jìn)程序的算法，然而沒成功等等情況留特，那就沒有必要去調(diào)優(yōu)纠脾。
- 完全忽略程序的性能。
- 所以總結(jié)起來說就是磕秤，需要根據(jù)實(shí)際情況選擇乳乌，要尋找一個(gè)平衡點(diǎn)。
（完）
