【隨堂筆記】基礎演算法概論

• 演算法：一種有輸入、輸出的解決問題步驟，且具有明確、有限步驟、有效的特性
• 演算法必須符合：
  輸入（Input）：0 或多個輸入
  輸出（Output）：至少有一個回傳結果（有可能回傳 0 或是 null）
  明確性（Definiteness）：每一個指令步驟必須明確
  有限性（Finiteness）：在有限步驟後一定會結束不會進入無窮迴圈
  有效性（Effectiveness）：步驟清楚可行，能使用紙筆計算求解
• 一般使用時間複雜度與空間複雜度來判斷演算法的好壞，較常使用時間複雜度來進行判斷
  (1) 時間複雜度（Time complexity）：使用運用概量（漸近分析 asymptotic analysis），非絕對時間。通常使用big O notation 表示時間複雜度（Time complexity），我們將其時間複雜度表示為 O(f(n))。f(n) 又稱為執行時間的成長率，是影響速度最大的變數。
  ex. O(1) -> 執行步驟固定，與輸入的值無關

  # 不管 n 輸入為多少，這個程式永遠只會執行一次
  def print_num(num):
    print(num)
  print_num(10)
  

  ex. O(n) -> 時間複雜度跟輸入的次數有關，線性時間成長。f(n) = n，所以 O(f(n)) = O(n)

  def sum_number(num):
    total = 0
    for n in num:
        total += num
    return total
  sum_number(10)
  

  一般常見的時間複雜度：
  花費時間

  O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2) < O(2^n) < O(!n)
  

  
  來源：第 12 期電腦科學概論 & 程式設計思維入門共學營
  (2) 空間複雜度：演算法所需消耗的記憶體資源。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示（asymptotic analysis）。
  ex. 空間複雜度 O(1) -> 無論程式跑多少遍，都不會影響變數數量

  def sum_number(num):
    total = 0
    for n in num:
        total += num
    return total
  sum_number(10)
  

  ex. 空間複雜度 O(n) -> 變數數量會隨程式所跑的次數影響

  def sum_number(num):
    total = []
    for n in num:
        total.append(num)
  sum_number(10)
  

• 遞迴演算法（Recursion）：函式中自己呼叫自己的函式，但設計上需要有終止條件 並回傳結果，不然會無窮無盡的執行下去。
  ex. 費式數列（斐波那契數）：定義由 0和 1 開始，之後的費式數列就是由之前的兩數相加而得出（注意：fibonacci 0 是第 0 項，類似 index 從 0 開始）

  N = 6
  費氏數列：
  0, 1, 1, 2, 3, 5, 8
  

  def fibonacci(n):
    """
    定義一個費式數列函式，回傳第 N 時的值
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
  # N = 6: 0, 1, 1, 2, 3, 5, 8（注意：fibonacci 0 是第 0 個）
  result = fibonacci(6)
  print(result)
  

  輸出：

  8
  

• 排序演算法（sort）：一種能將一串資料依照特定排序方式排列的演算法。最常用到的排序方式是數值順序以及字典順序。
  (1) 泡沫排序（bubble sort）：

  1. 比較相鄰的兩個元素。如果第一個比第二個大，就交換（swap）他們兩個。
  2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素就會是最大的數。
  3. 針對所有的元素重複以上的步驟，除了最後一個。
  4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較，就代表排序完成了。

(來源：第 12 期電腦科學概論 & 程式設計思維入門共學營)
假設長度為 n，由於所需執行次數為：(n - 1) + (n - 2) + .... + 1 次（外層和內層迴圈執行次數加總），所以運算的次數為 n (n-1) / 2次，等於 1/2 (n^2 - n)
在時間複雜度中，最高次方影響力最大，在這邊一次方變數 n 和常數乘法 1/2 可以忽略。因此時間複雜度為：O(n^2) -> horrible
(2) 選擇排序（Selection sort）：從尚未排序的序列中找出最大or最小的數並放到頭尾，再將剩餘的數字依照最大or最小放到頭尾兩端，直到排序完成

• 循序搜尋（Sequential Search）：從未排序資料中找特定值的搜尋方式
• 二分搜尋（Binary Search）：由於資料已排序，因此會在每次搜尋時取中間的元素做比較。
  -> 若搜尋值比較大則最小 index 更新為 mid_index + 1，若搜尋值比較小則最大 index 更新為 mid_index - 1，就不用重頭開始搜尋比較有效率。