## 演算法筆記｜演算法效能分析

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

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

#### 二、時間複雜度的分析

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

##第一部分
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次

&emsp;&emsp;上面的程式碼片段，第一部分因為執行了2個雙重 for 迴圈，所以執行次數是 $2n^2$，第二部分執行了一個 for 迴圈和輸出任務完成，執行次數是 $n+1$。整段程式碼總共的執行次數是 $2n^2+n+1$。

&emsp;&emsp;我們使用big-O 的方式分析時間複雜度，因為當n得值很大的時候 $n^2>>>n$，所以我們計算big-O 只取<font color="#f00">最高項次的項並去係數</font>，以此程式碼為例是$O(n)=n^2$，因此我們可以說這支程式碼的時間複雜度為 $O(n)=n^2$ 。

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

關鍵字：small-o、big-$\omega$、small-$\omega$、big-$\theta$

#### 三、空間複雜度的分析

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

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