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


  • 演算法:一種有輸入、輸出的解決問題步驟,且具有明確、有限步驟、有效的特性
  • 演算法必須符合:
    輸入(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. 費式數列(斐波那契數):定義由 01 開始,之後的費式數列就是由之前的兩數相加而得出(注意: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,就不用重頭開始搜尋比較有效率。






你可能感興趣的文章

CS50 Internet Primer

CS50 Internet Primer

fs_cli後台指令集

fs_cli後台指令集

Jest - mock read-only data

Jest - mock read-only data






留言討論