演算法筆記｜演算法效能分析：時間複雜度與空間複雜度

一、怎麼判斷好的演算法或不好的演算法？

  面對同樣的問題，好的演算法只要1秒就可以解決，不好的演算法可能要好幾萬年才能解決，因此我們就提出了2種分析演算法效能的方法，時間複雜度和空間複雜度。

二、時間複雜度的分析

  因為每台電腦執行同個程式所要花的時間不一樣，所以我們不會直接測量執行程式所需要的時間，相對的，我們會分析程式碼所需要花費時間的數量級數，下圖程式碼片段示範了如何進行時間複雜度的分析與計算

##第一部分
for i in range(n):    #執行n次
  for j in range(n):    #執行n次
        print("hello")

for i in range(n):    #執行n次
  for j in range(n):    #執行n次
        print("world")

##第二部分

for i in range(n): #執行n次
    print("!!!")

print("任務完成") #執行1次

上面的程式碼片段，第一部分因為執行了2個雙重 for 迴圈，所以執行次數是 

2n^2，第二部分執行了一個 for 迴圈和輸出任務完成，執行次數是 n+1。整段程式碼總共的執行次數是 2(n^2)+n+1。

  我們使用big-O 的方式分析時間複雜度，因為當n得值很大的時候 

n^2>>>n，所以我們計算big-O 只取最高項次的項並去係數，以此程式碼為例是O(n)=n^2，因此我們可以說這支程式碼的時間複雜度為 O(n)=n^2 。

  另外還有4種分析時間複雜度及更精準的計算方式留待未來有機會再寫xd，以下提供關鍵字，如果有興趣的人可以在自行搜尋。

關鍵字：small-o、big-ω、small-ω、big-θ

三、空間複雜度的分析

  空間複雜度與程式在執行的時候所需要佔用的記憶體空間有關，因為現在電腦的記憶體空間大多很充足，所以時間複雜度的重要性優於空間複雜度，在大學階段寫的程式基本上都不需要考慮空間上的問題，因此只需要大略知道即可。

  資料在記憶體中的擺放方式稱為資料結構，不同的擺放方式會影響我們存取資料或排序資料所需要花費的時間。常見的資料結構有陣列、鍊結串列、佇列、堆疊、二元樹、堆積樹、雜湊表等，會在後續的文章說明並提及相關的演算法。