時間複雜度的概念

概念

我們假設一個完美的電腦，對任何變數或陣列裡的元素使用如：加減乘除模、位元運算這類簡單操作所需的時間都需要 1 單位的時間。

我們可以計算出一個程式碼在執行一個特定的輸入需要多少單位的時間，假設叫做 $t$ 。

對於輸入的不同，這個 $t$ 有可能會不一樣，而我們想要估算 $t$ 和輸入大小的關係，這裡要介紹的是 Big-O 的觀念。

我們要找一個函式，而我們的演算法的計算時間一定不會超過這個函式乘上某個常數，這個函式就是 Big-O。

簡單來說，Big-O 就是要找一個函式，能夠描述該演算法在最壞情況下的執行時間。

更詳細的定義

我們說一個演算法是 $f(n) = O(g(n))$ 的，其中，如果對於所有正整數 $n$ ， $f(n)$ 是他需要的計算單位時間，滿足 $f(n) \leq c \cdot g(n)$ ，其中 $c$ 是一個常數，不會和 $n$ 有任何關係。

接下來的章節，我們會更詳細的介紹如何分析一個演算法的時間複雜度。