1.3 怎樣尋找最好的算法？：

????這一小節(jié)主要介紹了如何在面對(duì)一個(gè)具體問(wèn)題時(shí)，盡量減少做無(wú)用功，從一道“總和最大區(qū)間問(wèn)題”切入，四個(gè)算法完成了從時(shí)間復(fù)雜度 O(n^3) 到 O(n) 的轉(zhuǎn)變。我在力扣上也找到這道題（https://leetcode.cn/problems/maximum-subarray/）

????本來(lái)力扣原題只需要找出最大值，是不需要進(jìn)行具體最大值對(duì)應(yīng)區(qū)間的下標(biāo)的（會(huì)難一點(diǎn)），我在這里用四種方法找到了并分別用p和q表示區(qū)間的左右下標(biāo)。這四種方法中分治法最精妙也最有意思，和正常人的思維完全不同，倒是很貼合機(jī)器的處理方式。而第四種最快的O(n)算法作者在書(shū)里寫(xiě)的兩遍掃描太麻煩了，就自己另外找了一個(gè)更好用更易懂的【在線處理】算法。

1.4 關(guān)于排序的討論：

????書(shū)中這一節(jié)主要介紹排序，其實(shí)這幾種經(jīng)典的排序算法都是教案上的老東西了，現(xiàn)如今，更多的日常使用中，比如各種語(yǔ)言內(nèi)置的或數(shù)據(jù)處理時(shí)使用的排序算法更多是的一種混合排序算法，比如將【快排】和【堆排】結(jié)合起來(lái)的內(nèi)省算法（Introspective Sort, i.e. Introsort），就是如今大多數(shù)標(biāo)準(zhǔn)函數(shù)庫(kù)STL中排序函數(shù)的算法；此外還有Java和Android操作系統(tǒng)內(nèi)部使用的蒂姆排序（Timsort）等，其實(shí)Timsort最初在python中實(shí)現(xiàn)，今天仍然是該語(yǔ)言默認(rèn)的排序算法，具體細(xì)節(jié)可見(jiàn)源碼（https://github.com/python/cpython/blob/main/Objects/listsort.txt）。蒂姆排序速度和快排相當(dāng)，并具有【穩(wěn)定性】，便于多列列表的排序，使用廣泛。

????這里的排序題，力扣上也有（https://leetcode.cn/problems/sort-an-array/）

????算法設(shè)計(jì)就是在盡量“少做無(wú)用功”，這話我大概懂了，但是具體操作起來(lái)還是很難啊怎么辦。另外章節(jié)的最后作者給出了“排序算法的復(fù)雜度不可能小于O(nlgn)” 的數(shù)學(xué)證明，大概意思就是因?yàn)橐M(jìn)行比較，可以畫(huà)出一顆“決策樹(shù)”，相當(dāng)于N個(gè)元素的數(shù)組最多有可能會(huì)出現(xiàn)N!的序列，要區(qū)分這么多種序列，挑出最小一個(gè)，至少需要比較log(N!)（即樹(shù)高）次，使用斯特林公式（Stirling Formula），便可以得出log(N!) ~ O(nlgn)的結(jié)論。