LeetCode學習筆記 - 寫程式非常重要的概念 - 時間複雜度與空間複雜度

Github連結

1. 時間複雜度與空間複雜度是什麼

時間複雜度 Time Complexity

• 為一個函式，定性描述了演算法執行所需的時間
• 常用Big-O符號(ex. O())來表示，只考慮函式的最高項，而不考慮包含這個函式的係數

空間複雜度 Space Complexity

• 演算法計算過程中所消耗的內存空間
• 常用Big-O符號(ex. O())來表示

Big-O 符號 (Big O notation)

• 或稱為漸近符號，描述漸近行為的數學符號
• 使用另一個函式來說明函式數量級的漸近上界，也就是函式中的最高項
• 在Computer Science中，用在分析演算法複雜度上，也就是描述演算法複雜度的執行效率
• 它只會顯示演算法執行函式的最大指數、最高次方項或是常數(1)

舉例: 執行的演算法如果是6x^2+2x+8，那它會表示為O(n^2)

觀念:為什麼Big-O不表示為完整的函式呢?

拿前面的例子最高項係數6要被省略來說明，當n很大的時候，係數就顯得很小，也就是係數的影響力根本為不足道，同理其它項跟常數也是，所以決定複雜度的通常就是最高項而已

2. 為什麼需要知道時間複雜度與空間複雜度?

疑惑

當然之前有教過大家使用%timeit來計算一下執行時間不就好了? 幹嘛這麼麻煩呢? 但是大家可能會發現每次重新計算執行時間都會有點不同，更不用說換台電腦試試了，每台電腦的效能並不一樣，執行同一段程式，有的電腦快，有的電腦慢，所以當然不能只憑這個方法去決定演算法寫的好壞

答案

兩位工程師寫的程式都是做到同一件事，但是為什麼只有一個被人家說比較高端呢xd 我們要怎麼去評斷一位工程師程式寫的好壞呢? 當然就要透過時間複雜度與空間複雜度了喔，這樣我們就能瞭解到執行這個演算法，我們的執行效率跟空間的利用度

3. 實作: 計算時間與空間複雜度

• 範例一

def example_1(x):
  total = 0
  for i in range(x):
    total += i*i
  return total
example_1(10)

時間複雜度

一個for迴圈去執行x次，經過迴圈計算後做了x次的加法和x次的乘法，所以函式的時間複雜度為O(n)

空間複雜度

使用了一個變數total，和一個變數i，函式不會因為x變大了，需要多宣告變數，所以空間複雜度為O(1)

• 範例二

def example_2(x):
  total = 0
  for i in range(x):
    if i > 6:
      break
    else:
      total += i * i
  return total
example_2(10)

時間複雜度

不管x多大只要超過第七次，程式就會break，因為不會隨著x改變，所以時間複雜度為O(1)

空間複雜度

使用了一個變數total，和一個變數i，函式不會因為x變大了，需要多宣告變數，所以空間複雜度為O(1)

• 範例3

def example_3(x):
  total = 0
  for i in range(x):
    for j in range(i, x):
      total += i * j
  return total
example_3(10)

時間複雜度

雙重迴圈

i = 0的時候，j會執行x次加法和x次乘法

i = 1的時候，j會執行x-1次加法和x-1次乘法

...

總共會執行幾次加法跟乘法? (x+x-1+...+1)次加法和乘法

套用梯形公式: 上底加下底乘與高除以2

(x+1)x/2 = (x^2 +x) /2

取最高項扣掉係數

就會得到結果: O(N^2)

空間複雜度

使用了一個變數total，一個變數i和一個變數j，函式不會因為x變大了，需要多宣告變數，所以空間複雜度為O(1)

Reference

由於這篇是參考我所學習的課程加上網路資源，再經過自己的消化而來，如果有地方原作者覺得不妥，都請馬上與我聯繫喔，我會馬上移除，感謝

https://hiskio.com/packages/1vyM4lw7p

https://ithelp.ithome.com.tw/articles/10216436

https://zh.wikipedia.org/wiki/时间复杂度