利用Python來解釋時間複雜度的概念與計算

什麼是時間複雜度？

時間複雜度（Time Complexity）是用來衡量演算法執行時間隨著輸入大小變化的增長速度。通常使用 Big-O 表示法（O 記號）來描述，目的是估算最壞情況下的運行時間。

時間複雜度的計算主要基於以下幾個原則：

1. 忽略常數係數：O(2n) 與 O(n) 視為相同，因為增長趨勢相同。
2. 只考慮最高次項：O(n^2 + n) 視為 O(n^2)。
3. 巢狀迴圈計算方式： 單層迴圈 -> O(n) 雙層巢狀迴圈 -> O(n^2) 三層巢狀迴圈 -> O(n^3)
4. 遞迴關係式計算： 例如二分搜尋的遞迴關係為 T(n) = T(n/2) + O(1)，推導出 O(log n)。

Python 程式範例分析

1. O(1) - 常數時間

# 直接存取陣列元素，無論 n 多大，時間固定
arr = [1, 2, 3, 4, 5]
print(arr[2])  # O(1)

2. O(n) - 線性時間

def linear_search(arr, target):
    for num in arr:  # 迴圈運行 n 次
        if num == target:
            return True
    return False

3. O(n^2) - 平方時間

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):  # 巢狀迴圈 O(n^2)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

4. O(log n) - 對數時間（二分搜尋）

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

5. O(2^n) - 指數時間（斐波那契遞迴）

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)  # O(2^n)

不同演算法計算相同問題的時間比較

我們使用兩種不同的方法來解決相同問題，並透過 time 模組測量它們的執行時間。

例子：尋找中間值

O(n) - 線性時間（使用 for 迴圈）

import time

def find_middle_linear(arr):
    middle_index = len(arr) // 2
    for i in range(len(arr)):
        if i == middle_index:
            return arr[i]

arr = list(range(100000000))
start = time.time()
arr = find_middle_linear(arr)
end = time.time()
print(f"搜尋到{arr} O(n) 線性搜尋中間值時間: {end - start:.10f} 秒")

O(log n) - 對數時間（二分搜尋法改進版）

import time

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

arr = list(range(100000000))
target = arr[len(arr) // 2]  # 目標為中間值

start = time.time()
binary_search(arr, target)
end = time.time()
print(f"O(log n) 真正二分搜尋時間: {end - start:.10f} ")

1. 線性搜尋（O(n)）每次都需遍歷整個列表，效率較低。
2. 內建 max 方法 通常使用最佳化策略，使其效率接近 O(log n) 或更快。
3. 透過測試時間，我們可以看到不同時間複雜度的演算法在相同問題上的效能差異。

時間複雜度 O(log n) 和 O(n) 之間的理論運行時間差異主要來自增長速率的不同。以數學方式來表示：

• O(n)：運行時間與輸入大小 n 成正比，例如 T(n) ≈ k * n。
• O(log n)：運行時間與 log₂(n) 成正比，例如 T(n) ≈ k * log₂(n)。

1. 數值比較

假設 n = 1,000,000：

• O(n) → 1,000,000 步
• O(log₂(n)) → log₂(1,000,000) ≈ 20 步

這表示在這例子上 O(n) 的方法理論上會比 O(log n) 慢 約 50,000 倍。

程式範例 相除約等於1923倍

Python 的 for 迴圈和 list 操作由 C 語言實作，並且可能經過最佳化，使得線性搜尋的實際運行時間比單純的理論計算要短。

總結

• 時間複雜度能幫助我們估算演算法的效率。
• 使用 Big-O 記號來表示增長趨勢。
• 常見的時間複雜度包括 O(1)、O(n)、O(n^2)、O(log n) 等。
• 設計演算法時應考慮降低時間複雜度，提高效能。

希望這篇文章能幫助你理解 Python 中的時間複雜度概念及計算方式！