C.S. Overview

13 5 月, 2021

電腦科學的範圍太廣大，永遠有學不完的東西，趁看過記憶猶新時把相關的東西記錄起來，以後日後查找方便。

有趣題目

  • 演算法
  • Python
  • SDN / NFV
  • OPTEE / ATF

時間複雜度

  • 溫故知新
    • log n = x 的意思是 n = 2^x
    • 當 n = 4 時，程式會在 2 個步驟完成（4 = 2²）
    • 當 n = 16 時，程式會在 4 個步驟完成（16 = 2⁴）
  • 常見的六種時間複雜度與演算法
    1. O(1)：陣列讀取
    2. O(n)：簡易搜尋
    3. O(log n)：二分搜尋
    4. O(n²)：選擇排序法、插入排序法
    5. O(n logn)：合併排序法
    6. O(2^n)：費波那契數列

資料結構

Array

優點

  1. Random access 存取資料只需要O(1)時間。
  2. 相較pointer節省記憶體空間

缺點

  1. 新增/修改資料時很麻煩，花費O(N)時間在搬動資料。

適用

  1. 快速存取。
  2. 已知資料數量。
  3. 記憶體有限。

Linked List

優點

  1. 新增、修改較Array簡單，只需對O(1)個節點調整pointer、無需搬動其餘元素。
  2. 資料量為動態，無需像Array般resize。

缺點

  1. 搜尋的時間複雜度為O(N)。
  2. 需要額外記憶體儲存pointer。

適用

  1. 資料量無法預期。
  2. 需頻繁新增刪除資料。
  3. 無需快速查詢。

Stack

Last-In-First-Out
LinkedList: pop_front(), push_front()

Queue

First-In-First-Out
LinkedList: pop_front(), push_back()

Heap

Binary Search Trees

Hash Tables

Graphs

Set

Uniqu values without any particular order.

Search

Merge Sort

Quick Sort – Pivot

Heap Sort

Binary Search

嵌入式

Concurrency – Multi-thread 把同個任務拆成數個子任務，同時運行。
Parallelism – Load balancing 把存取網頁的訪客，分配到不同多個伺服器。

學校學習

陽明交通大學 | 電機/資工在職專班

參考資料

初學者學演算法｜從時間複雜度認識常見演算法 程式麻瓜的程式知識課（四）
初學者學演算法｜排序法入門：選擇排序與插入排序法 程式麻瓜的程式知識課（五）
初學者學演算法 | 排序法進階 : 合併排序法 程式麻瓜的程式知識課（六）
Second Round – 初學者寫給初學者的演算法教學