資料結構與演算法 Using Python

目錄

清單

• 資料結構與演算法 Using Python
  • 目錄
  • About Data Structure
  • Analysis of Algorithm
    • Running Time
    • Experimental Studies
    • Theoretical Analysis
    • Pseudocode (虛擬碼、偽代碼)
    • Pseudocode Details
    • Important Functions
    • Primitive Operations (演算法的基本操作)
    • Counting Primitive Operatioins
    • Growth Rate of Running Time (執行時間增長率)
    • Constant Factors
    • Big-Oh Notation
    • Big-Oh Example
    • Big-Oh and Grow Rate
    • Big-Oh Rules
    • Asymptotic Algorithm Analysis (漸進演算法分析)
    • Computing Prefix Averages
    • Prefix Averages
    • Review Math Define & Big-Oh
  • Maps/Dictionaries
  • Array
    • 特性
    • Insertion (插入元素)
    • Removeal (移除元素)
    • Add/Append (添加元素)
    • Comparison of the Strategies (策略比較)
    • Python Sample
  • Queues
    • 主要函數
    • 輔助函數
  • Queue的應用
    • 直接
    • 間接
    • 以Array實作Queue
  • Stacks
    • 主要函數
    • 輔助函數
  • Stack的應用
    • 直接
    • 間接
    • 以Array實作Stack
    • 配對檢測
    • 計算邏輯
  • Linked Lists (鏈結串列)
    • Singly Linked List (單向鏈結串列)
  • Recursion
  • Trees
  • Graphs
  • Searching
  • Sorting
  • Text Processing
  • Dynamic Programming
  • Artificial Intelligence Algorithms

---

About Data Structure

在資料結構中，常以抽象概念定義名詞，不依賴某種程式語言已有的結構特性，如array是個有序容器，起始index為0，同個array中只存放相同type的item，然而每個程式語言實作array後的特性未必相同

Analysis of Algorithm

Running Time

執行時間增長幅度通常取決於輸入大小，由於平均執行時間難以估計，所以通常以最壞的情況評估

Experimental Studies

以程式實現演算法，以不同的輸入規模測試並記錄時間(如下)，最後畫成圖表

from time import time
start_time = time()
'''
# run algorithm
'''
end_time = time()
elapsed = end_time - start_time

若採實驗的方式，需要確保硬體跟執行環境的統一，以及精準不受其他效能干擾因素的環境

Big-O (O) 代表worst case
Theta (θ) 代表average case
Omega (Ω) 代表best case

Theoretical Analysis

• 使用高階的描述取代實驗
• 輸入測資的大小定義為 n
• 考慮所有可能的測資
• 使用獨立的硬體跟軟體環境，來評估一個演算法的速度

Pseudocode (虛擬碼、偽代碼)

• 演算法的高階描述
• 比英文敘述更有條理
• 不如程式碼詳細
• 可能會有被忽略的程式設計問題

Pseudocode Details

Control flow

​​​​- if...then...[else...]
​​​​- while...do...
​​​​- repeat...until...
​​​​- for...do...
​​​​- Indentation replaces braces (以縮排取代大括號)
​​​​- Method declaration
​​​​- Method call
​​​​- Returnn value
​​​​- Expressions

Important Functions

Name	Time Complexity
Constant	1
Logarithmic	log(n)
Linear	n
N-Log-N	nlog(n)
Quadratic	n^2
Cubic	n^3
Exponential	2^n
Factorial	n!

Primitive Operations (演算法的基本操作)

• 基本計算執行
• 可在虛擬碼中辨別
• 不依賴程式語言
• 不需要過於詳細的定義
• 假設某個操作需要的時間是固定的

e.g, 評估表達式(即計算值)、將變數賦予值(即assignment)、取得陣列中的某個索引值、呼叫function/method、回傳值(return)

Counting Primitive Operatioins

透過檢視pseudocode，計算原始操作的最大值作為輸入大小的函數

op：operation，即1個操作時間
n ops：n operations，即n個操作時間

Line 1：2 ops (定義+取值)
Line 3：2 ops (取值+賦值)
Line 4：2n ops ((向data取值+賦值給val)*迴圈n次)
Line 5：2n ops (取biggest值，判斷val>biggest狀態)
Line 6：0~n ops (受Line 5判斷，有可能完全跑不到(0)，或n次迴圈都跑到(n))
Line 7：1 ops (回傳)

將以上加總：
best case：4n+5 = 4n+c ≈ 4n
worst case：5n+5 = 5n+c ≈ 5n
由於n很大，所以較少的+1、+2…是可以忽略的

Growth Rate of Running Time (執行時間增長率)

• 改變軟體環境或硬體設備
• T(n)的線性時間增長率是find_max的固有屬性

Constant Factors

• 增長率不受常數或低階項影響

  例如

  ${10}^{2}n+{10}^5$ 為linear，而

  ${10}^5{n}^2+{10}^{8}n$為

  $n^2$

Big-Oh Notation

給定一個函數f(n)跟g(n)，我們稱作f(n)是O(g(n)) (讀作Big-O g(n))

e.g,
2n + 10 is O(n)
2n + 10 <= cn
(c-2)n >= 10
n >= 10/(c-2)
得到c = 3, n0 = 10

Big-Oh Example

• $7n-2$

  c = 7, n0 = 1

• $3n^3+20n^2+5$

  c = 28, n0 = 1

• $3logn+5$

  c = 8, n0 = 2

Big-Oh and Grow Rate

• Big-O符號界定了function的增長率上限
• 「f(n) is O(g(n))」表示f(n) <= g(n)的增長率
  

Big-Oh Rules

• 去掉低階項與常數

  若f(n)是d次多項式，則f(n)是O(

  $n^d$)

• 使用盡可能小的函數

  2n 為O(n)，而不是O(

  $n^2$)

• 使用最簡單的表達式

  3n+5 為O(n)，而不是O(3n)

Asymptotic Algorithm Analysis (漸進演算法分析)

• worst case由輸入大小

Computing Prefix Averages

Prefix Averages

Review Math Define & Big-Oh

Maps/Dictionaries

Array

Using python (少用)
arr1 = array((Data Type), list)

特性

• 有序，連續
• 起始為0
• 儲存的內容型別一致，稱作element或item

Insertion (插入元素)

從中間插入element時，worst case為O(n)

Removeal (移除元素)

刪除任意位置item時，worst case為O(n)

Add/Append (添加元素)

與Insert的差別在於，添加的位置在array的最後，因此不會需要搬移其他items位置
worst case為O(1)

Comparison of the Strategies (策略比較)

Incremental Strategy Analysis (增量策略分析)

Doubling Strategy Analysis

Python Sample

Queues

FIFO

主要函數

• enqueue()

• dequeue()

輔助函數

• first()

• len()

• is_empty()

example

Queue的應用

直接

• Waiting lists, bureaucracy
• Access to shared resources (e.g., printer)
• Multiprogramming

間接

• Auxiliary data structure for algorithms
• Component of other data structures

以Array實作Queue

f為front
r為end

當不斷dequeue時，前面閒置的空間過多，當r已經用完後面空間時，會將指標指到前面的空間形成環狀

Stacks

LIFO

主要函數

• push()

• pop()

輔助函數

• top()

• len()

• is_empty()

example

Stack的應用

直接

• Page-visited history in a Web browser
• Undo sequence in a text editor
• Chain of method calls in a language that
  supports recursion

間接

• Auxiliary data structure for algorithms
• Component of other data structures

以Array實作Stack

t為top

配對檢測

Parentheses Matching (括號檢測)

• Algorithm
• Python
• HTML Tag

計算邏輯

Evaluating Arithmetic Expressions (算術表達式)

+ - * /等運算規則的優先順序判斷
e.g, 14 – 3 * 2 + 7 = (14 – (3 * 2) ) + 7

Linked Lists (鏈結串列)

Singly Linked List (單向鏈結串列)

Recursion

Trees

Graphs

Searching

Sorting

Text Processing

Dynamic Programming

Artificial Intelligence Algorithms

---

tags: Data Structure and Algorithms Python