這是演算法的靈魂，也是衡量工程師內功深淺的重要指標。

要判斷程式是否有效率則要考慮兩點

• 程式運行時間少

• 程式所占用的空間少

演算法的複雜度分為以下兩種

1.時間複雜度(Time Complexity) :執行演算法所花費的時間。

• 計算每個Function所執行的次數。
• 將總次數加起來求時間複雜度Big-O。

2.空間複雜度(Space Complexity):執行演算法所占用的空間。

• 計算每個Function中變數所佔用的空間。

Big-O

Big-O 用來表示演算法的複雜度的執行效率，只看最壞情況並且忽略常數、忽略低階項，在一個多項式中，我們只關心對整體結果影響最大的那一項。

舉例

def example(n):
    for i in range(n):
        for j in range(n):
            total += 1
    for k in range(n):
        total += 1

    total += 1  
    total += 1  

這個函式先執行一個巢狀迴圈計算次數，接著一個for迴圈計算，最後再計算兩次，所以這個函數的執行次數為:
n^2+n+2次，依照我們上述所說的計算Big-O可得這個函式的時間複雜度為O(n^2)。

時間複雜度

Python

n = n + 1

說明：執行時間不隨輸入資料 n 的大小而改變。
此程式只會執行一遍，所以時間複雜度是O(1)。

for i in range(n):
    x += 1

此程式會執行 n次，時間複雜度是O(n)。

for i in range(n):
    for j in range(n):
        x += 1

此程式會執行 n^2次，時間複雜度是O(n^2)。

接著我們拿二分搜尋法來分析O(log n)

    def binary_search(arr, k):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == k:
                return mid
            elif arr[mid] < k:
                left = mid + 1
            else:
                right = mid - 1

首先先把 k 當作基準，每一次的搜尋，都是一次「猜數字」的過程。

它的核心精神是：每一次都從搜尋範圍的正中間切入，然後根據比較結果，果斷地丟棄掉沒有用的一半範圍。

總結來說，在處理海量資料時，依然能保持極高的效率，這就是它時間複雜度為O(log n) 的原因。

空間複雜度

計算方式與時間複雜度相似，也使用 Big-O 來表示複雜度。差別在於是計算演算法所佔用的記憶體空間成本。
值得注意的是我們通常不計算輸入資料本身佔用的空間，而是計算為了完成演算法而新開闢的空間。

Python

範例一

def example(numbers):
    total = 0  
    for num in numbers:
        total += num

• 無論 numbers 列表的長度 n 是 10 還是 1,000,000，這個函式內部只需要固定幾個變數total來儲存臨時值。

• 它沒有創建任何新的、長度與 n 相關的資料結構。

• 因此，它額外使用的空間是一個常數。我們表示為 O(1)。

範例二

def create_list(numbers):

    ans = [] 
    for num in numbers:
        ans.append(num*num)

• 此演算法建立了一個新的List來儲存接收numbers的平方值

• for 迴圈每執行一次，就會向 ans 中添加一個新元素。

• 當函式執行完畢時，如果輸入的 numbers 列表長度為 n，那麼 ans 列表的長度也將為 n。

• 這個新List佔用的記憶體空間與 n 呈線性關係。因此，空間複雜度為 O(n)。

以上就是演算法中Big-O與複雜度的簡單介紹!
有任何問題都可以留言，有誤的地方歡迎討論。
下篇見!