什麼是時間複雜度？
時間複雜度（Time Complexity）是用來衡量演算法執行時間隨著輸入大小變化的增長速度。通常使用 Big-O 表示法（O 記號）來描述，目的是估算最壞情況下的運行時間。
時間複雜度的計算主要基於以下幾個原則：
- 忽略常數係數：
O(2n)與O(n)視為相同，因為增長趨勢相同。 - 只考慮最高次項：
O(n^2 + n)視為O(n^2)。 - 巢狀迴圈計算方式： 單層迴圈 ->
O(n)雙層巢狀迴圈 ->O(n^2)三層巢狀迴圈 ->O(n^3) - 遞迴關係式計算： 例如二分搜尋的遞迴關係為
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} ")
- 線性搜尋（O(n)）每次都需遍歷整個列表，效率較低。
- 內建
max方法 通常使用最佳化策略，使其效率接近 O(log n) 或更快。 - 透過測試時間，我們可以看到不同時間複雜度的演算法在相同問題上的效能差異。
時間複雜度 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 中的時間複雜度概念及計算方式！
