### 10.5.2 算法分析實例
本節以本章介紹的若干算法為例來討論對算法復雜性的分析。
搜索問題的兩個算法 對于搜索問題,本章介紹了線性搜索和二分搜索兩個算法。
線性搜索算法的思想是逐個檢查列表成員,編碼時可以用一個循環語句來實現。循環體 的執行次數取決于列表長度:如果列表長度為 n,則循環體最多執行 n 次。因此,如果列表 長度增大一倍,則循環次數最多增加一倍,算法執行的步數或實際運行時間最多增加一倍。 可見,線性搜索算法在最壞情形下的運行時間與輸入列表的大小 n 呈線性關系,即復雜度為 O(n),稱為線性時間算法。
二分搜索算法的主體也是一個循環,但該循環不是逐個檢查列表數據,而是每次檢查位 于列表中點的數據,并根據該中點數據與要查找的數據的大小比較情況來排除掉左半列表或 右半列表。接著對保留下來的一半列表重復進行這個“折半”過程。顯然,循環的次數取決 于輸入列表能“折半”多少次。如果初始輸入列表有 16 個數據,則第一輪循環后剩下 8 個數據,第二輪循環后剩下 4 個數據,第三輪后剩下 2 個,第四輪后只剩下 1 個數據。因此, 最多四輪循環后就能得出搜索結論:要么找到,要么不存在。一般地,如果輸入規模為 n, 則二分搜索算法最多循環 log2n 次,即復雜度為 O(log2n),稱為對數時間算法。要說明的是, O(log2n)表示復雜度與問題規模 n 的對數成正比,至于這個對數是以 2 為底還是以 10 為底并 不重要,因此我們經常省略對數的底,寫成 O(log n)。
O(n)與 O(log n)到底有多大差別?回到 10.2 中提到的猜數游戲,假如某甲心中想好一個1百萬以內的數讓某乙來猜。某乙從小到大逐個試猜(即線性搜索)的話,運氣好猜 1 次就能命中,運氣不好最多要猜 1 百萬次。平均來說需要猜 50 萬次才能猜中。而如果某乙每次 猜中間數(即二分搜索)的話,則最少猜 1 次,最多也不過猜 log21000000≈20 次就能猜中。 可見,隨著 n 的增大,O(log n)遠遠優于 O(n)。
排序問題的兩個算法
對于排序問題,本章介紹了選擇排序和歸并排序兩個算法。
首先推導選擇排序算法的步數與問題規模(即數據列表的長度)的關系。選擇排序算法 首先找出全體數據中的最小值,并將該值作為結果列表的第一個成員。其次,算法從剩余數 據中找出最小值,并將該值作為結果列表的第二個成員。依此類推,直至產生有序列表。假 設列表初始大小為 n,為找出最小值,算法需檢查每一個數據。接下來算法從剩余 n-1 個數 據中找出最小值,這需要檢查 n-1 個數據;第三次循環從 n-2 個剩余數據中找出最小值。這 個過程一直繼續到只剩 1 個數據為止。因此,選擇排序需要執行的步數為

按照前述規則,可以看出選擇排序算法所需的步數與數據列表大小的平方成正比,即算法復雜度為 O(n<sup>2</sup>),稱為二次方時間算法。 其次,我們來推導歸并排序算法的步數與列表大小的關系。歸并排序算法的基本思想是將列表一分為二,然后對兩半數據各自排序,最后再合并成一個列表。其中對兩個子列表的 排序又是通過遞歸調用歸并排序來實現的,最終將分解到長度為 1 的列表,這時可直接進行 歸并。由此可見真正的排序工作是在歸并過程中完成的,該過程所做的只是將來自子列表的 數據按從小到大的順序逐個復制到初始列表的合適位置。圖 10.11 展示了對列表[0,5,7,2]進 行歸并排序的過程。圖中用虛線表示初始列表的遞歸分解過程,逐步分解后最終得到長度為 1 的列表。這些長度為 1 的列表再進行歸并,逐步形成長度為 2、4 的有序的列表,圖中用實線箭頭表示歸并時各數據的逐步到位過程。從圖 10.11 容易分析出歸并排序算法的步數。 從左向右,分解過程并不比較數據大小來排序,這部分工作可以忽略。接下來的歸并過程包 含大量比較、復制操作,是整個算法的工作量的體現。歸并過程分為 log2n 層,以逐步形成 長度為 2、22、23、…、n 的有序子列表①。又因為每一層歸并都需要對全部 n 個數據進行處 理,所以歸并排序算法的步數是“n×層數”,即具有復雜度 O(nlog n),可稱為 nlog n 時間 算法。

圖 10.11 歸并排序過程示意圖
n<sup>2</sup> 與 nlog n 有多大差別呢?當 n 較小時,兩者差距不大,選擇排序算法甚至有可能還快 一些,因為它的代碼更簡單。但是,隨著 n 的增大,log n 只是緩慢地增大,因此 n×log n 的增長速度遠遠低于 n×n。這就是說,對于大量數據,歸并排序算法的性能遠遠好于選擇 排序算法。
> ① 如果 n 不是 2 的冪,子列表的長度當然也不會都是 2 的冪。
Hanoi 塔算法
下面推導 Hanoi 塔問題的遞歸算法的步數與圓盤個數 n 的關系。與基于循環(迭代)的算法不同,遞歸算法不容易直接從代碼形式上看出具體的操作步數。對于 Hanoi 塔遞歸算法, 我們可以直接考慮將 n 個圓盤從 A 柱移到 C 柱所需的移動次數。
根據算法的結構,為了移動 n 個圓盤,需要先將 n-1 個圓盤從最大圓盤上移開,然后移 動最大圓盤,最后再將 n-1 個圓盤移到最大圓盤上。假設 f(n)是移動 n 個圓盤所需的步數, 則應用一點中學數學知識很容易推導出

可見,Hanoi 塔算法的復雜度為 O(2n),稱為指數時間算法,這是因為問題規模的度量 n 出 現在步數公式的指數部分。
指數時間算法到底有多復雜呢?讀者也許聽說過“指數爆炸”這個名詞,它表明指數時 間算法所需要的執行時間會隨著問題規模的增長而迅速增長。在 Hanoi 塔故事中,即使僧侶 們 1 秒鐘就能移動一步圓盤,并且每天都不休息,為了移動 64 個圓盤,也需要花費 264-1秒,即 5850 億年!可見,指數時間算法只適用于解決小規模的問題。
總之,利用計算機解決問題時,需要考慮算法的時間復雜性,這是衡量問題難度和算法 優劣的一個重要指標。有些應用對于運行時間有較高要求,運行時間過長的話可能導致計算 結果過時、失效。圖 10.12 給出了本章見過的各種算法復雜度的大致比較,圖中橫坐標表示 問題規模 n,縱坐標是算法執行時間(或步數)。雖然圖中曲線不是很精確,但足以說明指 數時間和二次方時間算法是多么不適合大量數據,而其他幾種復雜度的曲線則相當平緩。

圖 10.12 各種算法復雜度比較
- 前言
- 第 1 章 計算與計算思維
- 1.1 什么是計算?
- 1.1.1 計算機與計算
- 1.1.2 計算機語言
- 1.1.3 算法
- 1.1.4 實現
- 1.2 什么是計算思維?
- 1.2.1 計算思維的基本原則
- 1.2.2 計算思維的具體例子
- 1.2.3 日常生活中的計算思維
- 1.2.4 計算思維對其他學科的影響
- 1.3 初識 Python
- 1.3.1 Python 簡介
- 1.3.2 第一個程序
- 1.3.3 程序的執行方式
- 1.3.4 Python 語言的基本成分
- 1.4 程序排錯
- 1.5 練習
- 第 2 章 用數據表示現實世界
- 2.1 數據和數據類型
- 2.1.1 數據是對現實的抽象
- 2.1.1 常量與變量
- 2.1.2 數據類型
- 2.1.3 Python 的動態類型*
- 2.2 數值類型
- 2.2.1 整數類型 int
- 2.2.2 長整數類型 long
- 2.2.3 浮點數類型 float
- 2.2.4 數學庫模塊 math
- 2.2.5 復數類型 complex*
- 2.3 字符串類型 str
- 2.3.1 字符串類型的字面值形式
- 2.3.2 字符串類型的操作
- 2.3.3 字符的機內表示
- 2.3.4 字符串類型與其他類型的轉換
- 2.3.5 字符串庫 string
- 2.4 布爾類型 bool
- 2.4.1 關系運算
- 2.4.2 邏輯運算
- 2.4.3 布爾代數運算定律*
- 2.4.4 Python 中真假的表示與計算*
- 2.5 列表和元組類型
- 2.5.1 列表類型 list
- 2.5.2 元組類型 tuple
- 2.6 數據的輸入和輸出
- 2.6.1 數據的輸入
- 2.6.2 數據的輸出
- 2.6.3 格式化輸出
- 2.7 編程案例:查找問題
- 2.8 練習
- 第 3 章 數據處理的流程控制
- 3.1 順序控制結構
- 3.2 分支控制結構
- 3.2.1 單分支結構
- 3.2.2 兩路分支結構
- 3.2.3 多路分支結構
- 3.3 異常處理
- 3.3.1 傳統的錯誤檢測方法
- 3.3.2 傳統錯誤檢測方法的缺點
- 3.3.3 異常處理機制
- 3.4 循環控制結構
- 3.4.1 for 循環
- 3.4.2 while 循環
- 3.4.3 循環的非正常中斷
- 3.4.4 嵌套循環
- 3.5 結構化程序設計
- 3.5.1 程序開發過程
- 3.5.2 結構化程序設計的基本內容
- 3.6 編程案例:如何求 n 個數據的最大值?
- 3.6.1 幾種解題策略
- 3.6.2 經驗總結
- 3.7 Python 布爾表達式用作控制結構*
- 3.8 練習
- 第 4 章 模塊化編程
- 4.1 模塊化編程基本概念
- 4.1.1 模塊化設計概述
- 4.1.2 模塊化編程
- 4.1.3 編程語言對模塊化編程的支持
- 4.2 Python 語言中的函數
- 4.2.1 用函數減少重復代碼 首先看一個簡單的用字符畫一棵樹的程序:
- 4.2.2 用函數改善程序結構
- 4.2.3 用函數增強程序的通用性
- 4.2.4 小結:函數的定義與調用
- 4.2.5 變量的作用域
- 4.2.6 函數的返回值
- 4.3 自頂向下設計
- 4.3.1 頂層設計
- 4.3.2 第二層設計
- 4.3.3 第三層設計
- 4.3.4 第四層設計
- 4.3.5 自底向上實現與單元測試
- 4.3.6 開發過程小結
- 4.4 Python 模塊*
- 4.4.1 模塊的創建和使用
- 4.4.2 Python 程序架構
- 4.4.3 標準庫模塊
- 4.4.4 模塊的有條件執行
- 4.5 練習
- 第 5 章 圖形編程
- 5.1 概述
- 5.1.1 計算可視化
- 5.1.2 圖形是復雜數據
- 5.1.3 用對象表示復雜數據
- 5.2 Tkinter 圖形編程
- 5.2.1 導入模塊及創建根窗口
- 5.2.2 創建畫布
- 5.2.3 在畫布上繪圖
- 5.2.4 圖形的事件處理
- 5.3 編程案例
- 5.3.1 統計圖表
- 5.3.2 計算機動畫
- 5.4 軟件的層次化設計:一個案例
- 5.4.1 層次化體系結構
- 5.4.2 案例:圖形庫 graphics
- 5.4.3 graphics 與面向對象
- 5.5 練習
- 第 6 章 大量數據的表示和處理
- 6.1 概述
- 6.2 有序的數據集合體
- 6.2.1 字符串
- 6.2.2 列表
- 6.2.3 元組
- 6.3 無序的數據集合體
- 6.3.1 集合
- 6.3.2 字典
- 6.4 文件
- 6.4.1 文件的基本概念
- 6.4.2 文件操作
- 6.4.3 編程案例:文本文件分析
- 6.4.4 緩沖
- 6.4.5 二進制文件與隨機存取*
- 6.5 幾種高級數據結構*
- 6.5.1 鏈表
- 6.5.2 堆棧
- 6.5.3 隊列
- 6.6 練習
- 第 7 章 面向對象思想與編程
- 7.1 數據與操作:兩種觀點
- 7.1.1 面向過程觀點
- 7.1.2 面向對象觀點
- 7.1.3 類是類型概念的發展
- 7.2 面向對象編程
- 7.2.1 類的定義
- 7.2.2 對象的創建
- 7.2.3 對象方法的調用
- 7.2.4 編程實例:模擬炮彈飛行
- 7.2.5 類與模塊化
- 7.2.6 對象的集合體
- 7.3 超類與子類*
- 7.3.1 繼承
- 7.3.2 覆寫
- 7.3.3 多態性
- 7.4 面向對象設計*
- 7.5 練習
- 第 8 章 圖形用戶界面
- 8.1 圖形用戶界面概述
- 8.1.1 程序的用戶界面
- 8.1.2 圖形界面的組成
- 8.1.3 事件驅動
- 8.2 GUI 編程
- 8.2.1 UI 編程概述
- 8.2.2 初識 Tkinter
- 8.2.3 常見 GUI 構件的用法
- 8.2.4 布局
- 8.2.5 對話框*
- 8.3 Tkinter 事件驅動編程
- 8.3.1 事件和事件對象
- 8.3.2 事件處理
- 8.4 模型-視圖設計方法
- 8.4.1 將 GUI 應用程序封裝成對象
- 8.4.2 模型與視圖
- 8.4.3 編程案例:匯率換算器
- 8.5 練習
- 第 9 章 模擬與并發
- 9.1 模擬
- 9.1.1 計算機建模
- 9.1.2 隨機問題的建模與模擬
- 9.1.3 編程案例:乒乓球比賽模擬
- 9.2 原型法
- 9.3 并行計算*
- 9.3.1 串行、并發與并行
- 9.3.2 進程與線程
- 9.3.3 多線程編程的應用
- 9.3.4 Python 多線程編程
- 9.3.5 小結
- 9.4 練習
- 第 10 章 算法設計和分析
- 10.1 枚舉法
- 10.2 遞歸
- 10.3 分治法
- 10.4 貪心法
- 10.5 算法分析
- 10.5.1 算法復雜度
- 10.5.2 算法分析實例
- 10.6 不可計算的問題
- 10.7 練習
- 第 11 章 計算+X
- 11.1 計算數學
- 11.2 生物信息學
- 11.3 計算物理學
- 11.4 計算化學
- 11.5 計算經濟學
- 11.6 練習
- 附錄
- 1 Python 異常處理參考
- 2 Tkinter 畫布方法
- 3 Tkinter 編程參考
- 3.1 構件屬性值的設置
- 3.2 構件的標準屬性
- 3.3 各種構件的屬性
- 3.4 對話框
- 3.5 事件
- 參考文獻