[Algorithm]What is Big O

Big O 是一個漸進的數學符號， 用來描述函式的時間複雜度或空間複雜度。

通常函式的時間複雜度會直接反應此函式的效能好壞，這篇就專門討論時間複雜度的部分

一、O(1)

O(1): input參數為number，for迴圈從0 -> 10 print Hello Kitty 10次

＊input參數number 的大小並不會影響函式本身的運作次數，這種類型的時間複雜度就是典型的O(1)

二、O(n)

O(n): input參數為number，for迴圈從0 -> number， print Hello Kitty number的次數

＊input參數number 的大小會影響函式的運作次數隨著number的次數線性成長，這種類型的時間複雜度是O(n)

三、O(n²)

O(n²): input參數為number，for迴圈從0 -> number * number次， print Hello Kitty

ex: number = 1 時 i 跑一次時j也跑一次 => 1*1 = 1

number = 2時 i 跑2次，每次j跑2次 => 2* 2 = 4

number = 3時 i 跑3次，每次j跑3次 => 3* 3= 9

＊input參數number 的大小會影響函式的運作次數隨著number的次數線性指數成長，這種類型的時間複雜度是O(n²)

四、O(2n) ?

O(2n): input參數為number，for 跑兩次迴圈從0 -> number 次， print Hello Kitty，時間複雜度為O(2n)，實際上還是與O(n)一樣隨著線性變化，在Big O裡O(2n) = O(n)

＊在計算Big O 時不用考慮倍數的問題

O(n+1) ?

實際上也等於O(n)一樣隨著線性變化

＊在計算Big O 時不用考慮常數的問題

Conclusion: 初步了解認識時間複雜度與Big O，學習到了在Big O的世界裡計算Big O 時不用考慮常數和倍數，之後再練習演算法時也更能解釋與回答為什麼這個時間複雜度是如何了。

進階篇 → [Algorithm]進階 Big O

Thanks for your reading.