第一章、 算法簡介
一些常見的大O運(yùn)行時間
》 O(log n)，也叫對數(shù)時間，這樣的算法包括二分查找。
》 O(n)，也叫線性時間，這樣的算法包括簡單查找。
》 O(n * log n)，這樣的算法包括第4章將介紹的快速排序——一種速度較快的排序算法。
》 O(n2)，這樣的算法包括第2章將介紹的選擇排序——一種速度較慢的排序算法。
》 O(n!)，這樣的算法包括接下來將介紹的旅行商問題的解決方案——一種非常慢的算法。
小結(jié)
》 二分查找的速度比簡單查找快得多。
》 O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
》 算法運(yùn)行時間并不以秒為單位。
》 算法運(yùn)行時間是從其增速的角度度量的。
》 算法運(yùn)行時間用大O表示法表示。
第二章、選擇排序
總結(jié)
? 計算機(jī)內(nèi)存猶如一大堆抽屜。
? 需要存儲多個元素時，可使用數(shù)組或鏈表。
? 數(shù)組的元素都在一起。
? 鏈表的元素是分開的，其中每個元素都存儲了下一個元素的地址。
? 數(shù)組的讀取速度很快。
? 鏈表的插入和刪除速度很快。
? 在同一個數(shù)組中，所有元素的類型都必須相同(都為int、double等)。
第三章、 遞歸、棧
關(guān)于遞歸
我懷著激動的心情編寫本章，因為它介紹的是遞歸——一種優(yōu)雅的問題解決方法。遞歸是我 最喜歡的主題之一，它將人分成三個截然不同的陣營:恨它的、愛它的以及恨了幾年后又愛上它 的。我本人屬于第三個陣營 --- 作者
計算機(jī)在內(nèi)部使用被稱為調(diào)用棧的棧。我們來看看計算機(jī)是如何使用調(diào)用棧的。下面是一個 簡單的函數(shù)。
def greet(name):
print( "hello, " + name + "!" greet2(name) )
print( "getting ready to say bye..." bye() )
這個函數(shù)問候用戶，再調(diào)用另外兩個函數(shù)。這兩個函數(shù)的代碼如下。
def greet2(name):
print( "how are you, " + name + "?")
def bye():
print ("ok bye!")
現(xiàn)在你又回到了函數(shù)
greet。由于沒有別的事情要做，你就從函數(shù)greet返回。這個棧用于存儲多個函數(shù)的變量，被稱為調(diào)用棧。
遞歸調(diào)用棧
遞歸函數(shù)也使用調(diào)用棧!來看看遞歸函數(shù)factorial的調(diào)用棧。factorial(5)寫作5!，其
定義如下:5! = 5 * 4 * 3 * 2 * 1。同理，factorial(3)為3 * 2 * 1。下面是計算階乘的遞歸函數(shù)。
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
下面來詳細(xì)分析調(diào)用fact(3)時調(diào)用棧是如何變化的。別忘了，棧頂?shù)姆娇蛑赋隽水?dāng)前執(zhí)行 到了什么地方。
使用棧雖然很方便，但是也要付出代價:存儲詳盡的信息可能占用大量的內(nèi)存。每個函數(shù)調(diào) 用都要占用一定的內(nèi)存，如果棧很高，就意味著計算機(jī)存儲了大量函數(shù)調(diào)用的信息。在這種情況 下，你有兩種選擇。
? 重新編寫代碼，轉(zhuǎn)而使用循環(huán)。
? 使用尾遞歸。這是一個高級遞歸主題，不在本書的討論范圍內(nèi)。另外，并非所有的語言
都支持尾遞歸。
小結(jié)
? 遞歸指的是調(diào)用自己的函數(shù)。
? 每個遞歸函數(shù)都有兩個條件:基線條件和遞歸條件（遞歸用巧勁）
? 棧有兩種操作:壓入和彈出。
? 所有函數(shù)調(diào)用都進(jìn)入調(diào)用棧。
? 調(diào)用?？赡芎荛L，這將占用大量的內(nèi)存。
遞歸條件指的是函數(shù)調(diào)用自己，而基線條件則 指的是函數(shù)不再調(diào)用自己，從而避免形成無限循環(huán)。
