HI! 我是Maple 剛滿20歲沒多久的小朋友 請ㄅ要欺負窩QAQ

今日資料結構上課筆記

1. 資料結構

• 線性DS(矩陣、串列、有序串列) VS. 非線性DS(tree、graph)
• 連續(array)或不連續(pointer)的儲存空間

2. 關鍵字

• binary search

3. 宣告

• 宣告函式指令不算一個步驟
• 宣告變數沒給初值不算一個步驟

4. Big-Oh(Ο)

• Big-Ο代表演算法時間函式的上限(Upper bound)
• 在最壞的狀況下，演算法的執行時間不會超過Big-Ο
• f(n) = Ο(g(n)) iff ∃正常數c和n0，使得f(n) ≤ c × g(n), ∀ n >= n0
  • n：輸入資料大小
  • f(n)：理想狀況下，程式在電腦中實際執行指令次數
  • g(n)：執行時間的成長率
• 時間函式的Big-O Notation導出步驟

  • 係數設為1

  • 保留最大項，刪除其它項

  • 範例1:

    T(n) = 3 ⇒ O(1)
    T(n) = 2n + 3 ⇒ 1n + 1 ⇒ O(n)
    T(n) = 3n^2 + 4n + 5 ⇒ 1n^2 + 1n + 1 ⇒ O(n^2)
    

  • 範例2:

     f(n) = 5n + 3 ⇒ f(n) = Ο(n) 
     ⇒ 由f(n) = Ο(g(n))可知g(n) = n
     令c為最大項的常數值加1
     f(n) = 5n + 3 ⇒ c = 5 + 1 = 6
     f(n) = 5n + 3 ≤ cg(n)
     ⇒ f(n) = 5n + 3 ≤ 6n --- 兩邊同減5n
     ⇒ 3 ≤ n 
     ⇒ n至少要≥3 ⇒ n0 = 3
     f(n) = Ο(g(n)) iff ∃正常數c=6和n0=3，使得f(n) ≤ c × g(n), ∀ n >= n0
    

5. Omega( Ω )

• 在最好的狀況下，演算法的執行時間不會比Omega快

• 格式：f(n) = Ω(g(n)) iff ∃正常數c和n0，使得f(n) ≥ c × g(n), ∀ n >= n0

   f(n) = 5n + 3, 求c與n0
   f(n) = 5n + 3 ⇒ f(n) = Ω(n) 
   ⇒ 由f(n) == Ω(g(n))可知g(n) = n
   令c與最大項的常數值相同
   f(n) = 5n + 3 ⇒ c = 5
   f(n) = 5n + 3 ≥ cg(n) 
   ⇒ f(n) = 5n + 3 ≥ 5n --- 兩邊同減5n
   ⇒ 3 ≥ 0 ⇒ 恆真 ⇒ n0可為任意值
   ⇒ 令n0為1
   f(n) = Ω(g(n)) iff ∃正常數c=5和n0=1，使得f(n) ≥ c × g(n), ∀ n >= n0
  

6. Theta( Θ )

• Θ代表演算法時間函式的上限與下限

• 格式：f(n) = Θ(g(n)) iff ∃正常數c1,c2和n0，使得c1 × g(n) ≤ f(n) ≤ c2 × g(n) , ∀ n ≥ n0

  • c1×g(n)：下限 ⇒ Ω
  • c2×g(n)：上限 ⇒ Ο

• 範例

   f(n) = 5n + 3, 求c1、c2與n0
   f(n) = 5n + 3 ⇒ f(n) = Θ(n) 
   ⇒ 由f(n) = Θ(g(n))可知g(n) = n
   由之前Ω和Ο的範例可得 ⇒ c1=5, c2=6
   f(n) = 5n + 3 ≥ c1 g(n), f(n) = 5n + 3 ≤ c2g(n)
   ⇒ f(n) = 5n + 3 ≥ 5n, f(n) = 5n + 3 ≤ 6n ---別各減5n
   ⇒ 3 ≥ 0, 3 ≤ n ⇒ 令n0=3
   f(n) = Θ(g(n)) iff ∃正常數c1=5,c2=6和n0=3,使得c1 × g(n) ≤ f(n) ≤ c2 × g(n), ∀ n ≥ n0