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

演算法：一種有輸入、輸出的解決問題步驟，且具有明確、有限步驟、有效的特性
演算法必須符合：
輸入（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，就不用重頭開始搜尋比較有效率。