《Python算法教程》——2.7 練習題

本節書摘來自異步社群《python算法教程》一書中的第2章，第2.7節，作者[挪威]magnus lie hetland（赫特蘭）， 淩傑 譯，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

2-1.　當我們用python中的list建構一個多元數組時，通常需要使用循環來完成（或某種與list推導式等效的技術），為什麼不能用表達式[[0]10]10來建立一個10×10的數組呢？這樣做會有什麼問題嗎？

2-2.　讓我們來做個假設（也許會有點不切實際）：如果我們允許在配置設定記憶體時出現未初始化的情況（也就是說，這塊記憶體中還保有上一次被使用時留下的“垃圾資料”），并且配置設定記憶體也隻需要常數時間。這時如果您想建立一個含有n 個整數的數組，并且希望跟蹤其每一項——看看它是處于非初始化狀态，還是您已經在它裡面儲存過一個數字了。這種檢查操作也是可以在常數時間内完成的。那麼，我們究竟應該怎樣做，才能保證它在常數時間内完成它的初始化操作呢？（以及應該如何在常數時間裡完成一個空鄰接數組的初始化操作，以避免其成為一個以平方級時間為最小運作時間的操作？）

2-3.　請證明o 與Ω的性質正好相反，即如果f = o (g )，那麼g = Ω(f )，反之亦然。

2-4.　對數通常有各自不同的底數，但在算法學上，我們往往并不會太在意它。為了明白其中的原因，我們可以來考慮一下這個等式：logbn= (logan )/(logab)。首先，您知道這個等式為什麼成立嗎？其次，為什麼它能告訴我們不需要去操心對數的底數問題？

2-5.　請證明任何指數級操作（Θ(kn )，其中k > 1）的增長都要快于多項式級操作（Θ(nj )，其中j > 0）。

2-6.　請證明任何多項式操作（Θ(nk )，其中k 為任意常數且k > 0）的漸近增長都要快于對數級操作（Θ(lg n )）。（值得注意的是，這裡的多項式中包括根數在内，如平方根（k = 0.5）等）。

2-7.　請研究或推算一下python list類型上各個操作的漸近複雜度，如索引、元素項指派、順序反轉、元素的追加及插入（最後兩項我們在list的黑盒子專欄中已經讨論過了）。如果我們改用連結清單類型來實作這些操作會有什麼不同？請以list.extend為例加以說明。

2-8.　請證明表達式Θ(f ) + Θ(g ) = Θ(f + g ) and Θ(f ) · Θ(g ) = Θ(f · g )成立。另外，您也可以試試是否能證明max(Θ(f ), Θ(g )) = Θ(max(f , g )) = Θ(f + g )成立。

2-9.　在附錄c中，您會找到一組與樹有關的、帶編号的陳述句，請證明它們是等效的。

2-10.　假設t 是一棵有根樹，它至少應包含三個節點，并且每個内部節點下面又正好都有兩個子節點。那麼，如果t 上有n 個葉節點，樹上到底應有多少個節點呢？

2-11.　請證明一個dag可以由任何形式的（底層）結構組成。換言之，任何（無向）圖結構都可以成為一個dag的底層圖結構。或者說，對于任何給定的圖結構，我們都可以通過調整其邊線方向，從中産生出一個有向圖，而它正好是一個dag。

2-12.　請考慮下面這種圖結構的表示法：我們使用字典類型，設定其每個鍵為兩個節點的元組，然後将該元組的值設定為邊的權值，如w[u, v] = 42。請問：該表示法有什麼優點和缺點？您有辦法彌補這些缺點嗎？