• 科學(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í)間(對(duì)每塊代碼塊分塊估算時(shí)間)
  • 算法分析的意義(經(jīng)典算法理論大部分發(fā)表于數(shù)十年前,但依舊適用于今天的計(jì)算機(jī))
  • 成本模型(一個(gè)衡量算法性能的指標(biāo)
  • 總結(jié)(得到其運(yùn)行時(shí)間的數(shù)學(xué)模型所需步驟):
    • 確定輸入模型,定義問題的規(guī)模
    • 識(shí)別內(nèi)循環(huán)
    • 根據(jù)內(nèi)循環(huán)中的操作確定成本模型
    • 對(duì)于給定的輸入,判斷這些操作的執(zhí)行頻率.這可能需要進(jìn)行數(shù)學(xué)分析(學(xué)習(xí)具體算法的時(shí)候有例子)

tip:數(shù)學(xué)中的常見函數(shù),包括(向下取整,向上取整,自然對(duì)數(shù),以2為底的對(duì)數(shù),以2為底的對(duì)數(shù)想下取整,調(diào)和級(jí)數(shù)??,階乘)

數(shù)學(xué)中的常見近似函數(shù),包括(調(diào)和級(jí)數(shù)求和??,等差數(shù)列求和,等比數(shù)列求和,斯特靈公式??,二項(xiàng)式系數(shù),指數(shù)函數(shù))

• 增長數(shù)量級(jí)的分類:

  
  
  圖片.png

• 設(shè)計(jì)更快的算法(一般步驟):

  • 實(shí)現(xiàn)并分析該問題的一種簡單算法,通常稱為暴力算法
  • 考查算法的各種改進(jìn)
  • 用實(shí)驗(yàn)證明新的算法更快

tip:對(duì)于實(shí)際問題來說,運(yùn)行時(shí)間只是選擇算法時(shí)所考慮的各種因素之一.

• 倍率實(shí)驗(yàn)(簡單有效的預(yù)測任意程序的性能，并判斷它們的運(yùn)行時(shí)間大致的增長數(shù)量級(jí)):
  • 開發(fā)一個(gè)輸入生成器來產(chǎn)生實(shí)際情況下的各種 可能的輸入
  • 開發(fā)一個(gè)程序,能夠計(jì)算每次實(shí)驗(yàn)和上次實(shí)驗(yàn)的運(yùn)行時(shí)間的比值
  • 反復(fù)運(yùn)行,直到該比值趨近于極限 2^x (對(duì)于比值沒有極限的算法無效)
  • 這個(gè)程序的運(yùn)行時(shí)間的增長數(shù)量級(jí)約為 N^x

有一個(gè)疑問,假如增長數(shù)量級(jí)是對(duì)數(shù)級(jí)的呢?

• 猜想①:logN級(jí)別的數(shù)量級(jí)對(duì)比N^x數(shù)量級(jí),會(huì)小很多,可能會(huì)被忽略;
• 猜想②:可以將第3)步的極限解釋為有l(wèi)ogN的可能性[ logN / log (N/2) = logN/(logN-1)],即比值趨近于 2^x * [logN/(logN-1)],對(duì)應(yīng)的 增長數(shù)量級(jí) 約為 N^x * logN

書中的背后一頁用倍率公式解釋了我的上述疑問,即 如果 T(N) ~ a(N^b)(logN) ,那么T(2N)/T(N) ~ 2^b

一般來說,在數(shù)學(xué)模型中,對(duì)數(shù)項(xiàng)是不能忽略的,但在倍率假設(shè)中,它在預(yù)測性能的公式中,顯得不是很重要

倍率實(shí)驗(yàn)的作用:

• 評(píng)估算法解決大型問題的可行性
• 評(píng)估使用更快的的計(jì)算機(jī)所產(chǎn)生的價(jià)值

解釋一下表1.4.9:

• 系數(shù)為2、系數(shù)為10 這兩列以下的數(shù)據(jù)的意思指的是 當(dāng)輸入規(guī)模增長2\10倍時(shí),算法運(yùn)行時(shí)間增長了多少倍.(比如平方級(jí)別增長了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)不一定有必要找出來。
  • 對(duì)輸入的強(qiáng)烈依賴，運(yùn)行時(shí)間和輸入不一定是無關(guān)的。
  • 多個(gè)問題參量：可能存在多個(gè)變量影響著程序的性能。
  • 綜上所述：有效近似的估算出任何程序所需的運(yùn)行時(shí)間，就足夠了。
• 處理對(duì)輸入的依賴：
  • 對(duì)我們所要解決的問題的輸入建模。讓輸入模型更加切合實(shí)際。***個(gè)人理解：輸入不一定要很復(fù)雜，只要能夠分析程序的性能，簡單反而更好。
  • 對(duì)最壞情況下的性能的保證。從極度悲觀的角度來估算算法的性能。
  • 隨機(jī)化算法。對(duì)輸入隨機(jī)化。
  • 操作的順序。算法的“輸入”可能不只是數(shù)據(jù)，還有可能是一系列操作的順序。
  • 均攤分析。所有操作的總成本除于操作總數(shù)將成本均攤。我們可以允許執(zhí)行一些昂貴的操作，但是所有操作的平均成本較低，也是可以接受的。
• 內(nèi)存

tip：一般內(nèi)存的使用都會(huì)被填充為8字節(jié)的倍數(shù)。

* 原始數(shù)據(jù)所需內(nèi)存：

類型
字節(jié)（每個(gè)字節(jié)8位）

圖片.png

• 對(duì)象：
  所有實(shí)例變量使用的內(nèi)存+對(duì)象本身的開銷（一般是16字節(jié)，包括一個(gè)指向?qū)ο蟮念惖囊?、垃圾收集信息、同步信息?br> 例如：一個(gè)Integer對(duì)象會(huì)使用24字節(jié)（16字節(jié)的對(duì)象開銷，4字節(jié)保存它的int值，4個(gè)填充字節(jié)）
• 鏈表
  嵌套的非靜態(tài)類（內(nèi)部類）。在普通對(duì)象的基礎(chǔ)上還需要一個(gè)指向外部類的引用（8字節(jié)）
• 數(shù)組：
  • 原始類型的數(shù)組：一般需要24字節(jié)的頭信息（16字節(jié)的對(duì)象開銷，4字節(jié)用于保存長度、4填充字節(jié)）+保存值所需的內(nèi)存。
    • 例如：一個(gè)有N個(gè)int值的數(shù)組需要使用（24+4N）字節(jié)（會(huì)被填充為8的倍數(shù)。
  • 對(duì)象的數(shù)組：其實(shí)就是一個(gè)對(duì)象引用的數(shù)組，所以我們應(yīng)該在對(duì)象所需內(nèi)存外加上引用所需的內(nèi)存。
    • 例如：一個(gè)含有N個(gè)Integer對(duì)象的數(shù)組需要24字節(jié)（數(shù)組開銷）+8N字節(jié)（所有引用）+32N字節(jié)（所有對(duì)象所需內(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)）
• 字符串對(duì)象：
  一個(gè)指向字符數(shù)組的引用（8字節(jié)）、3個(gè)int值（共12字節(jié)）（第一個(gè)int是字符數(shù)組中的偏移量、第二個(gè)int是字符串的長度、第三個(gè)int是散列值）、對(duì)象本 身的消耗（16字節(jié)）以及4個(gè)填充字節(jié)；除此之外，還要加上字符數(shù)組所需的內(nèi)存空間。
• 子字符串（java實(shí)現(xiàn)）subString()：
  其實(shí)只是修改了字符串對(duì)象中的三個(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)。

（完）