1.5 練習

1．判斷題

（1）為了能夠正確地使用庫中定義的函數/類/方法，必須要了解它的API（即參數和返回值是什么）。（　）

（2）假設定義的先驗條件、后置條件還有實現的代碼都是對的，如果在執行代碼之前已經滿足了先驗條件，則保證在執行代碼后后置條件也一定為真。（　）

（3）當函數檢測到其先驗條件被違反時，應該輸出錯誤消息。（　）

（4）函數的簽名提供了其行為的完整規范。（　）

（5）精心設計的功能/方法通常具有未注明的副作用。（　）

（6）使用相同的計算機、編程語言和輸入數據，執行Θ (n)的算法肯定比執行Θ (n2)的算法快。（　）

（7）使用代碼行數多的函數可能比使用代碼行數少的函數更快。（　）

（8）當算法的預期輸入大小很小時，Θ 符號是算法效率的有效度量。（　）

（9）所有的O(n2)算法時間復雜度都是Θ (n2)。（　）

（10）所有的Θ (n2)算法時間復雜度都是O(n2)。（　）

2．選擇題

（1）以下哪項不屬于函數簽名的一部分？（　）

a．函數的名稱

b．該函數如何工作

c．參數

d．返回值

（2）函數中的哪些操作會產生副作用？（　）

a．將不可變參數設置為新對象

b．將可變參數設置為新對象

c．修改可變參數

d．返回一個值

（3）下面哪項表明滿足了函數的先驗條件？（　）

a．該函數不會崩潰

b．該函數返回一個值

c．該函數拋出了異常

d．以上都不是

（4）一般來說，以下哪項對算法在大型數據集上執行的時間影響最大？（　）

a．算法的效率

b．用于實現算法的計算機語言

c．算法中的代碼行數

d．計算機上硬盤的速度

（5）具有兩個循環的函數的漸近運行時間是（　）。

a．Θ (log2n)

b．Θ (n)

c．Θ (n2)

d．沒有足夠的信息來確定

（6）如果Θ (n2)的算法需要3s才能處理有100萬個元素的輸入，那么大約需要多長時間才能處理200萬個元素？（　）

a．6s

b．9s

c．12s

d．18s

（7）如果Θ (n3)的算法需要4s才能處理有100萬個元素的輸入，那么大約需要多長時間才能處理200萬個元素？（　）

a．8s

b．16s

c．32s

d．64s

（8）如果的算法需要20s才能處理有100萬個元素的輸入，那么大約需要多長時間才能處理200萬個元素？（　）

a．21s

b．25s

c．30s

d．40s

（9）如果的算法需要10s才能處理有10個元素的輸入，那么大約需要多長時間才能處理20個元素？（　）

a．20s

b．100s

c．1000s

d．10000s

（10）如果計算機每秒能夠執行10億次操作，那么一個需要執行n2次操作的算法，面對200萬個元素的輸入，大約需要執行多長時間？（　）

a．400s

b．2000s

c．4000s

d．20000s

3．簡答題

（1）函數/方法的副作用是什么？

（2）描述自上而下的設計的基本方法以及它與契約式設計之間的關系。

（3）如果需要重復地對一個有20個元素的隨機列表進行搜索以查找用戶輸入的不同值，應該使用哪種搜索方法？應不應該創建另一個包含相同元素但已經有序的列表來進行搜索？為什么你這樣認為？

（4）如果需要重復地對一個有2000000個元素的隨機列表進行搜索以查找用戶輸入的不同值，應該使用哪種搜索方法？應不應該創建另一個包含相同元素但已經有序的列表來進行搜索？為什么你這樣認為？

（5）對于上面的問題，Python的列表是存儲數字最合適的數據類型嗎？如果不是的話，你會使用Python的哪一個數據類型？

（6）如果計算機每秒能夠執行10億次操作，那么一個需要執行2n次操作的算法，面對n=100個元素的輸入，大約需要執行多長時間？

（7）如果計算機每秒能夠執行10億次操作，那么一個需要執行n2次操作的算法，面對n=1000000個元素的輸入，大約需要執行多長時間？如果算法需要執行n3次操作呢？

（8）對以下代碼片段的時間復雜度進行Θ 分析。

a．n = input('enter n: ')
   for i in range(n):
       x = 2 * n
       while x > 1:
             x = x / 2

b．n = input('enter n: ')
   total = 0
   for i in range(n):
       for j in range(10000):
                total += j
   print total

c．total = 0
   n = input('enter n: ')
   for i in range(2 * n):
       for j in range(i, n):
                total += j
   for j in range(n):
       total += j
   print j

（9）書中第一個版本的線性搜索算法使用了Python的index方法，而沒有用任何循環。但是，我們也提到了線性搜索算法的時間復雜度是Θ (n)。通常來說，沒有循環的算法的時間復雜度應該是Θ (1)。請解釋這一（明顯的）差異。

4．編程練習

（1）創建一個包含0～999999的擁有100萬個整數的列表。分別用index方法和for語句的線性搜索，以及二分搜索對最好和最壞情況進行計時（像這一章的例子中那樣，使用time.time函數）。在注釋中列出你使用的計算機規格（CPU芯片和時鐘速度、操作系統和Python版本）以及3個搜索在最好和最壞情況下的執行時間。

（2）創建元素為1～1000萬的整數，元素個數為10000、100000和1000000的隨機列表。使用內置的列表sort方法來對每個列表進行排序并計時。在注釋中列出你使用的計算機規格（CPU芯片和時鐘速度、操作系統和Python版本）以及對每個列表進行排序所需的時間。注釋中里還應該包括sort方法的Θ 時間復雜度。

（3）選擇排序算法是這樣來進行排序操作的：在未排序的序列里找到最小元素，然后和列表的第0個位置的元素互換；之后，再從列表里尋找第二小的元素，然后和列表的第1個位置的元素互換；以此類推，找到第n ? 1個最小的元素并將其置于n ? 2的位置。這時，最大的元素也就會處于位置n ? 1上了。在Python里實現這個算法，并注明算法的Θ 時間復雜度。同樣，對上一個問題里創建的那3個列表進行排序，并計時。

（4）設計一個比較對不同大小的列表執行線性搜索和二分搜索的實驗。將結果輸出成圖，看看能不能找到線性搜索勝過二分搜索的那個“交叉”點。由于小列表搜索速度非常快，因此你得發揮一下聰明才智才能得到搜索時間的有效數據（提示：通過計算多次指定的搜索來得到更大的搜索時間總和）。寫一份完整的實驗報告，解釋你的實驗設置、方法、數據以及分析。

（5）完成在1.2.3小節里的統計信息程序。請務必在已知結果的數據集上徹底測試你的程序。

（6）在1.2.3小節的程序里添加一個函數，這個函數能夠返回5個整數，分別是90分數段、80分數段、70分數段、60分數段和60以下分數段的分數的個數。確保為新函數提供完整的規范，并且包括適當的先驗條件與后置條件，以及相應的實現代碼。

（7）每當需要一組數據的平均值的時候，通常也需要計算標準差。這樣一來，在1.2.3小節里的統計信息程序的現有API在某種程度上是低效的，這是因為在計算平均值和標準差的時候，會導致前者被計算了兩次（為什么？）。重新設計這個程序的API來避免這個問題。你的新設計應該允許用戶高效地單獨計算平均值、單獨計算標準差以及同時計算兩個值。

（8）設計并實現一個問答程序。這個程序能夠從文件里讀取問答信息。例如，關于美國各個州的首府的問答程序將會在文件的每一行中找到州名和它的首府的名稱（如俄亥俄州：哥倫布市）。你的程序應該詢問一定數量的問題并輸出正確答案的數量。在你的設計中至少要有3個獨立的函數。

（9）編寫一個函數的規范和實現，從有序列表中擠出（“squeeze”）重復項。例如：

>>> x = [1, 1, 3, 3, 3, 4, 5, 5, 8, 9, 9, 9, 9, 10]
>>> squeeze(x)
>>> x
[1, 3, 4, 5, 8, 9, 10]

徹底地測試你的函數并分析其效率。