《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭?著

標簽：數(shù)據(jù)結(jié)構(gòu)、算法

第一章 復(fù)雜度分析分為兩個部分，第一部分，首先從復(fù)雜度分析的意義開始引入，然后介紹了大O復(fù)雜度表示法，介紹了兩種時間復(fù)雜度分析方法，介紹了幾種常見的時間復(fù)雜度量級，最后簡介了空間復(fù)雜度分析方法。第二部分通過代碼舉例分析的方式，介紹了最好、最壞、平均、均攤四種時間復(fù)雜度分析方法。

點評：第一章的內(nèi)容并不長，對復(fù)雜度分析的術(shù)語和概念等知識的描述不多，因為這不是一本教科書，作者從直接給出代碼樣例復(fù)雜度分析的角度來闡述復(fù)雜度分析，讓內(nèi)容變得更加通俗易懂，便于初學(xué)者學(xué)習(xí)，而且，選取的代碼，也有特色，實用性強。

內(nèi)容推薦：

1：講解了兩種比較實用時間復(fù)雜度分析方法：加法法則和乘法法則。這兩種方法，所有的復(fù)雜度分析的書都會涉及，但是用這兩個詞并不多，這兩個詞來表述這兩個方法，對學(xué)習(xí)者交流不錯。請記住這兩個詞：加法法則和乘法法則。

2：幾種常見的時間復(fù)雜度量級，這一段也有意思，作者代為總結(jié)對學(xué)習(xí)者有幫助。

3：第二部分，介紹四種時間復(fù)雜度分析方法，要注意，這類復(fù)雜度分析方法，有一個前提，就是問題的輸入規(guī)模，即n，是不變的，在輸入規(guī)模不變時，有些代碼針對不同的輸入實例，時間復(fù)雜度是不一樣的。

4：第二部分中，介紹的加權(quán)平均時間復(fù)雜度（期望時間復(fù)雜度），這個術(shù)語和方法，在常見的數(shù)據(jù)結(jié)構(gòu)或算法教材中復(fù)雜度分析中是沒有的，在教材中，這種方法叫做概率分析，屬于高級算法分析方法。均攤分析也是高級算法分析方法之一。因為這本書的側(cè)重點不是理論，也不是教材，所以概率分析和均攤分析的理論知識，讀者需要從其他書籍中獲取了。

5：這一章結(jié)束時，留的事件復(fù)雜度分析思考題，不錯，因為這段代碼有一定的實用性（這是C++ STL中數(shù)組容器的實現(xiàn)原理），而且這段代碼的時間復(fù)雜度分析，可以把書中介紹的最好、最壞、平均、均攤四種時間復(fù)雜度分析方法四都用上。