### 10.5.1 算法復雜度
為了回答上述問題,首先要明確如何衡量算法的好壞。以搜索問題為例,線性搜索算法
直接了當,易設計易實現,這算不算“好”?而二分搜索算法雖然設計實現稍難一些,但因 無需檢查每一個數據而大大提高了搜索效率,這又算不算“好”?
在解決數學問題時,不論是證明定理還是計算表達式,只要證明過程正確、計算結果精 確,問題就可以認為成功地解決了,即正確性、精確性是評價數學解法好壞的標準。而在用 計算機解決問題時,僅僅要求算法能正確、精確地解決問題,是不夠的。試想,假如一個算 法雖然能夠正確地解決問題,但需要在計算機上運行 100 年或者需要占用 100TB 的內存, 這樣的算法有實際意義嗎?不要以為 100 年或 100TB 是危言聳聽,很多簡單算法都可能輕 易地達到或突破這樣的需求(參見稍后對 Hanoi 塔算法的分析)。可見,利用計算機解決問 題必須考慮算法的經濟性,即算法所耗費的資源問題。計算機用戶當然都希望能多快好省地 解決問題,因此好的算法應當盡量少地耗費資源。
通常只考慮算法所占用的 CPU 時間和存儲器空間這兩種資源①。所謂算法分析,就是分 析特定算法在運行時所耗費的時間和存儲空間的數量,分別稱為算法的時間復雜度和空間復 雜度。本節只討論算法的時間復雜度,畢竟存儲空間的大小在現代計算機中已經越來越不再 是一個問題。
雖然討論的是算法耗費的“時間”,但我們并不是真的去測量程序在計算機中的實際運 行時間,因為實際運行時間依賴于特定機器平臺(CPU、內存、操作系統、編程語言等), 同一算法在不同平臺上執行可能得到不同的分析結果,故很難據此對算法進行分析和比較。 例如,在最先進的計算機上執行線性搜索也許比在老式計算機上執行二分搜索要快,據此得 出線性搜索優于二分搜索顯然不合理。
實際上,算法分析指的是分析算法的代碼,估計出為解決問題需要執行的操作(或語句、 指令等類似概念)的數目,或稱算法的“步數”。之所以分析算法步數,是因為:第一,步 數確實能反映執行時間——步數越多執行時間就越長;第二,算法的步數不依賴于平臺,更 容易分析和比較。
例如,下面的函數 f1()需要執行 11 次賦值操作,其中包含 10 次加法運算②:
```
def f1():
x = 0
for i in range(10):
x = x + 1
```
而下面的函數 f2()需要 21 次賦值操作(20 次加法):
```
def f2():
x = 0
for i in range(20):
x = x + 1
```
比較一下 f1 和 f2,顯然 f1 運行時間更短,但這并不意味著 f1 比 f2 采用的算法“好”, 因為它們的“算法”顯然是一樣的,只不過 f1 要處理的數據更少:f1 將 10 個 1 相加,而 f2 將 20 個 1 相加。可見,算法復雜度是跟算法處理的數據量有關的。
算法通常都設計成能處理任意大小的輸入數據,這就導致算法的步數并不是固定的,而 是隨著問題規模的變化而變化,因此算法的步數可表示為問題規模的函數。假設用 n 表示問題規模,算法分析不僅要考慮算法步數與 n 的關系,更重要的是還要考慮“當 n 逐漸增大時” 算法復雜度會如何變化。例如,將上述 f1 和 f2 改寫成更一般的形式:
> ① 不考慮開發算法的人力物力等代價。
> ② 注意我們分析的層次是源代碼級別,而不是機器指令級別。
```
def f(n):
x = 0
for i in range(n):
x = x + 1
```
不難得出此函數需要執行的步數為 n+1。當 n 增大時,算法執行時間也會增加,而且是線性地增加,即:當 n 增加 1 倍變成 2n,執行時間變成 2n+1,大約比 n+1 增加 1 倍。
說 A 算法比 B 算法好,并不是指對于特定的 n,A 比 B 節省 50%的時間,而是指隨著 n 的不斷增大,A 對 B 的優勢會越來越大。
算法復雜度的大 O 表示法
再次觀察上面例子中函數 f()的步數表達式“n+1”,不難看出其中對執行時間起決定作 用的是 n,而 n 后面的+1 是可以忽略不計的。按照“當 n 逐漸增大時”進行分析的思想, 即便是 n+100、n+1000000 中,n 后面的常數也是可以忽略不計的,因為與逐漸增大趨于∞ 的 n 相比,任何常數都是浮云。事實上,分析算法復雜度時,我們只分析其增長的數量級, 而不是分析其精確的步數公式。
數學中的“大 O 表示法”根據函數的增長率特性來刻畫函數,可以用來描述算法的復 雜度。令 f(n)和 g(n)是兩個函數,如果存在正常數 c,使得只要 n 足夠大(例如超過某個 n0), 函數 f(n)的值都不會超過 c×g(n),即當 n > n0 時,
```
f(n) <= c x g(n)
```
則可記為
```
f (n) = O(g(n))
```
在描述算法復雜度時,n 對應于問題規模,f(n)是算法需執行的步數,g(n)是表示增長數 量級的某個函數。說算法的復雜度為 O(g(n)),意思就是當 n 足夠大時,該算法的執行步數(時間)永遠不會超過 c×g(n)。
例如,假設一個算法當輸入規模為 n 時需要執行 n+100 條指令,則當 n 足夠大時(只 要大于 100),
```
n + 100 <= n + n = 2n
```
套用大 O 表示法的定義,取 g(n)=n,則可將此算法的復雜度表示為 O(n)。同理,如果一個 算法的步數為 n+1000000,它的復雜度仍然可表示為 O(n)。由此可見,兩個不同的算法雖然 具有不同的代碼和執行步數,但完全可能具有相同的復雜度,即當問題規模足夠大時,它們 的執行時間按相同數量級的增長率增長,利用大 O 表示法即可描述這一點。
實際分析算法時,為了使 O(g(n))中的 g(n)函數盡量簡單,在得到算法的步數表達式 f(n) 之后,可以利用兩條規則來簡化推導,直接得出 f(n)的大 O 表示。規則如下:
(1)如果 f(n)是若干項之和,則只需保留最高次項,省略所有低次項;
(2)如果 f(n)是若干項之積,則可省略任何常數因子(即與 n 無關的因子)。 例如,分析下列代碼:
```
def f(n):
x = 0
for i in range(n):
for j in range(n):
for k in range(n):
x = x + 1
for i in range(n):
for j in range(n):
for k in range(n):
x = x + 1
for i in range(n):
x = x + 1
```
易知此算法的步數為 2n<sup>3</sup>+n+1。根據第一條規則,可只保留 2n3;再根據第二條規則,可只保留 n<sup>3</sup>。所以,此算法的復雜度為 O(n<sup>3</sup>)。當然我們也可以直接從 f(n)開始推導,利用大 O表示法的定義來驗證這個結果是正確的:對于 n > 1,

取 g(n)為 n3,c 為 4,即得 f(n) = O(n3)。 總之,以上兩條規則告訴我們,在分析算法代碼時可以忽略許多代碼,而只關注那些嵌套層數最多、并且每一層循環的循環次數都與問題規模 n 有關的循環。
- 前言
- 第 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 事件
- 參考文獻