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

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

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

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

內(nèi)容推薦：

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

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

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

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

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