資料結構與演算法簡介

Da-Wei Chiang

大綱

  • 何謂資料結構
  • 常見的資料結構
  • 何謂演算法
  • 常見的演算法
  • 如何評判演算法的好壞
    • 時間複雜度
    • 空間複雜度

何謂資料結構

  • 不管是寫任何的程式，我們都需要將資料存在記憶體中，必要時取出資料進行運算
  • 因此程式執行的效能好壞與資料在記憶體中的儲存形式密切相關
  • 如何有效率的將資料儲存於記憶體中，使存取速度提升進而增進程式效率就需要資料結構這們學問

常見的資料結構

  • 陣列(Array)
  • 鏈結串列(Linked List)
  • 佇列(Queue)
  • 堆疊(Stack)
  • 樹(Tree)
    • 二元樹(Binary Tree)
    • 堆積樹(Heap Tree)

何謂演算法

  • 解決問題的方法
  • 好的資料結構須搭配好的演算法才能真正提升程式效率

常見的演算法

  • 排序(Sort)
    • 泡沫排序(Bubble Sort)
    • 選擇排序(Selection Sort)
    • 插入排序(Insertion Sort)
    • 堆積樹排序(Heap Sort)
    • 合併排序(Merge Sort)
    • 快速排序(Quick Sort)
  • 搜尋(Search)
    • 線性搜尋法(Linear Search)
    • 順序搜尋法(Sequential Search)
    • 二元搜尋法(Binary Search)
  • 圖形(Graph)
    • 廣度優先(BFS)
    • 深度優先(DFS)
    • 最短路徑演算法
  • 貪婪演算法(Greedy Algorithm)
    • 銷售員問題(Traveling Salesman Problem)
  • 動態規劃演算法(Dynamic Algorithm)
    • 背包問題(Knapsack Problem)

如何評判演算法的好壞

  • 如何評判演算法的好壞, 有以下兩種方式
    • 時間複雜度: 程式的執行快慢 (快慢不是以執行時間計算, 而是以執行步驟的次數評判)
    • 空間複雜度: 程式執行所佔的記憶體大小
  • 我們通常以Big O來衡量時間、空間複雜度.

時間複雜度(一) 範例

  • 下方程式你覺得需要花多少的時間執行?
def Compare(n):
    print(n)

時間複雜度(一) 說明

def Compare(n):
    print(n)
  • 此程式不論n帶進多少, 執行時間不隨著n的不同而增長. 因此時間複雜度為Big O的常數項.我們會寫為O(1)

時間複雜度(二) 範例

  • 下方程式你覺得需要花多少的時間執行?
def Compare(n):
    for i in range(n):
        print(i)

時間複雜度(二) 說明

def Compare(n):
    for i in range(n):
        print(i)
  • 此程式會隨著n的增大而執行的時間變長. 因此時間複雜度是線性成長. 我們會寫為O(n)

時間複雜度(三) 範例

  • 下方程式你覺得需要花多少的時間執行?
def Compare(n):
    for i in range(n):
        for j in range(n):
            print(i*j)

時間複雜度(三) 說明

def Compare(n):
    for i in range(n):
        for j in range(n):
            print(i*j)
  • 此程式會隨著n的增大而執行的時間變長. 因此時間複雜度是指數成長. 我們會寫為O(n^2)

常見的時間複雜度Big O

  • Big O的概念並不難, 僅需查看在完成指定結果前共執行了幾個步驟即可.
    • $O(1)$ : 只需「1」個步驟即可完成指定結果. 如: print輸出, 索引值取值...等等
    • $O(n)$ : 需「n」個步驟才完成指定結果. 如: 迴圈跑n次...等等
    • $O(n^2)$ : 需「$n^2$」個步驟才完成指定結果. 如: 雙迴圈印九九乘法表
    • $O(log n)$ : 每次執行的次數都以指數的方式遞減. 如: 二元搜尋法
    • $O(nlog n)$ : 每次執行的次數都以指數的方式遞減. 如: 合併排序法
    • ... 等等

動腦時間

  • 試想一下上述所提及的Big O, 哪個執行結果最快? 也是我們在設計演算法時最希望得到的結果？

圖示化Big O

  • 我們以圖形來觀看Big O的執行結果
In [24]:
## 視覺化範例
import matplotlib.pyplot as plt
import numpy as np

point = np.array(range(1, 11))

O_1 = point/point
O_n = point
O_n2 = point*point
O_logn = np.log2(point)
O_nlogn = point * np.log2(point)

O_2_n = 2 ** point

plt.plot(point, O_1, label="O(1)")
plt.plot(point, O_n, label="O(n)")
plt.plot(point, O_n2, label="O(n^2)")
plt.plot(point, O_logn, label="O(log n)")
plt.plot(point, O_nlogn, label="O(nlog n)")
plt.plot(point, O_2_n, label="O(2^n)")
plt.xlabel('執行次數')
plt.ylabel('耗費時間')
plt.axis([1, 10, 0, 100])
plt.legend()
plt.show()

空間複雜度

  • 計算程式執行時所佔的記憶體空間.
  • 一般來說, 程式執行時會耗費的空間有以下三種
    • 輸入所需空間
    • 程式計算所耗費的空間
    • 輸出所需空間
  • 輸入、輸出為每個演算法必不可少的步驟. 因此空間複雜度僅計算「程式計算時所耗費的空間」

空間複雜度(一) 範例

  • 有一數組「1, 5, 4, 3, 5, 2」
  • 撰寫一隻程式判斷是否有重複的數字. 程式撰寫如下.
  • 請問此程式的時間複雜度是多少？
num = [1, 5, 4, 3, 5, 2]

for i in range(1, len(num)):
    for j in range(i):
        if(num[i] == num[j]):
            print(num[i], '重複了')

空間複雜度(一) 說明

num = [1, 5, 4, 3, 5, 2]

for i in range(1, len(num)):
    for j in range(i):
        if(num[i] == num[j]):
            print(num[i], '重複了')
  • 此程式的撰寫方法時間複雜度為O(n^2). 因為沒有用到任何儲存空間. 因此空間複雜度為O(1)

空間複雜度(二) 範例

  • 上例的問題其實有很多解法. 比如說我們更改程式如下
  • 請問此程式的時間複雜度與空間複雜度各是多少？
num = [1, 5, 4, 3, 5, 2]
check_dict = {}
for i in num:
    if(i not in check_dict):
        check_dict[i] = 1
    else:
        print(i, '重複了')

空間複雜度(二) 說明

num = [1, 5, 4, 3, 5, 2]
check_dict = {}
for i in num:
    if(i not in check_dict):
        check_dict[i] = 1
    else:
        print(i, '重複了')
  • 此程式透過pyhon內建資料結構字典將所有走訪num, 將所有走訪過的元素都儲存起來.因此時間複雜度為O(n), 空間複雜度為O(n)

時間 vs 空間

  • 由上述的例子我們知道以下幾件事情.
    • 同樣的問題透過不同的演算法解決. 會有不同的時間複雜度與空間複雜度.
    • 時間跟空間是可以互換的. 較差的時間複雜度可透過增加空間的儲存來使時間複雜度變好但空間複雜度變差. 反之亦然.
  • 大多數情況「時間複雜度的重要程度大於空間複雜度」. 因此, 在探討演算法時我們主要以「時間複雜度為主」