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

更新於 發佈於 閱讀時間約 7 分鐘

什麼是時間複雜度?

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

raw-image

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

  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} 秒")
raw-image

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} ")
raw-image
  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 中的時間複雜度概念及計算方式!

avatar-img
132會員
219內容數
本業是影像辨識軟體開發,閒暇時間進修AI相關內容,將學習到的內容寫成文章分享。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
螃蟹_crab的沙龍 的其他內容
Python 程式在電腦上的執行流程 當我們在電腦上執行 Python 程式時,主要經歷以下幾個步驟: 1. 編寫 Python 程式碼 開發者使用文字編輯器或 IDE(如 VS Code、PyCharm)撰寫 Python 程式,並將其存為 .py 檔案。 例如,一個簡單的 Python
用 PyInstaller 打包一個簡單計算機應用 (GUI 使用 PyQt5) 本教學將帶您使用 PyQt5 建立一個簡單的計算機應用,並透過 PyInstaller 將其打包成執行檔(EXE)。 1. 安裝所需環境 在開始之前,請確保您已安裝以下工具: 必要套件 Python: 建
使用 Selenium 自動滾動網頁並抓取文章連結 在網頁爬蟲開發中,我們經常遇到需要自動滾動頁面以加載新內容的場景,特別是在一些無限滾動的頁面中(例如新聞網站或社交媒體)。 本文將介紹如何使用 Python 的 Selenium 庫來實現這一需求,並抓取頁面中的VCC自己文章的連結。
有時候總是會需要將兩個PDF檔或多個來做合併。 在 Python 中,您可以使用 PyPDF2 或 PyPDF4 等庫來合併多個 PDF 文件。 以下是使用 PyPDF2 的範例步驟: 我利用word另存兩個pdf來做示範: 完成合併 1. 安裝 PyPDF2 如果還未安裝,您可以
最近來越南出差,遇到要將自己學習心得轉換成越南文給越南同事看。就研究了一下如何用Python來翻譯整個Word的文件,具越南同事說他有比對中文跟越南文意思差不多。 本文將教您如何使用 Python 的 python-docx 與 googletrans 套件,快速完成 Word 文件的自動翻譯。
在一個典型的程式專案中,UI、Controller 和 Main 的分工通常遵循 MVC 模型(Model-View-Controller) 的架構,這是一種常見的設計模式,能夠將應用程式的邏輯和界面進行分離。 大部分典型的程式專案設計: UI (View):專注於用戶界面,展示數據,並將用
Python 程式在電腦上的執行流程 當我們在電腦上執行 Python 程式時,主要經歷以下幾個步驟: 1. 編寫 Python 程式碼 開發者使用文字編輯器或 IDE(如 VS Code、PyCharm)撰寫 Python 程式,並將其存為 .py 檔案。 例如,一個簡單的 Python
用 PyInstaller 打包一個簡單計算機應用 (GUI 使用 PyQt5) 本教學將帶您使用 PyQt5 建立一個簡單的計算機應用,並透過 PyInstaller 將其打包成執行檔(EXE)。 1. 安裝所需環境 在開始之前,請確保您已安裝以下工具: 必要套件 Python: 建
使用 Selenium 自動滾動網頁並抓取文章連結 在網頁爬蟲開發中,我們經常遇到需要自動滾動頁面以加載新內容的場景,特別是在一些無限滾動的頁面中(例如新聞網站或社交媒體)。 本文將介紹如何使用 Python 的 Selenium 庫來實現這一需求,並抓取頁面中的VCC自己文章的連結。
有時候總是會需要將兩個PDF檔或多個來做合併。 在 Python 中,您可以使用 PyPDF2 或 PyPDF4 等庫來合併多個 PDF 文件。 以下是使用 PyPDF2 的範例步驟: 我利用word另存兩個pdf來做示範: 完成合併 1. 安裝 PyPDF2 如果還未安裝,您可以
最近來越南出差,遇到要將自己學習心得轉換成越南文給越南同事看。就研究了一下如何用Python來翻譯整個Word的文件,具越南同事說他有比對中文跟越南文意思差不多。 本文將教您如何使用 Python 的 python-docx 與 googletrans 套件,快速完成 Word 文件的自動翻譯。
在一個典型的程式專案中,UI、Controller 和 Main 的分工通常遵循 MVC 模型(Model-View-Controller) 的架構,這是一種常見的設計模式,能夠將應用程式的邏輯和界面進行分離。 大部分典型的程式專案設計: UI (View):專注於用戶界面,展示數據,並將用
你可能也想看
Google News 追蹤
Thumbnail
/ 大家現在出門買東西還會帶錢包嗎 鴨鴨發現自己好像快一個禮拜沒帶錢包出門 還是可以天天買滿買好回家(? 因此為了記錄手機消費跟各種紅利優惠 鴨鴨都會特別注意銀行的App好不好用! 像是介面設計就是會很在意的地方 很多銀行通常會為了要滿足不同客群 會推出很多App讓使用者下載 每次
介紹如何在模擬物體運動時,引入加速度這個物理量。
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 1.2.6 熱的傳導 1.2.7 十九世紀的尾聲 三 必須說一下波希米亞數學家/邏輯學家/哲學家/神學
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 1.2.6 熱的傳導 1.2.7 十九世紀的尾聲 一 函數概念的發展不可能終結,踏入公元廿一世紀,數學
Thumbnail
這一節談的是向量的定義,以及如何運用向量來建立模擬物體運動時,關於位置和速度間的關係式。
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 1.2.6 熱的傳導 一 偏微分方程始於公元十八世紀,在十九世紀茁長壯大。 隨著物理科學擴展越深 (理
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 五 特朗貝爾依循當時數學界對函數的普遍理解,視「函數」為任一分析式。 但這時的歐拉宣稱函數不必是正常意義下的
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 三 1755年,歐拉改變了主意,在《微分學原理》(Institutiones calculi differen
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法  三 有些讀者大概都知道,微積分學有兩個分科﹕一為微分學 (differential calculus),一為積分學 (integ
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法  二 前面說過,牛頓關心的不是抽象的數學問題,他要解決的是天體運動的問題。他知道,假如他擁有該天體在任何一刻的瞬速數據,他便能夠從質量
Thumbnail
直觀理解 導數:考慮的是單一變數的函數,描述的是函數在某點的斜率或變化率。 偏導數:考慮的是多變數函數,描述的是函數在某個變數變化時的變化率,其他變數保持不變。  (針對各維度的調整 或者稱變化 你要調多少) 應用 導數:在物理學中應用廣泛,例如描述速度和加速度。 偏導數:在多變量分析、優
Thumbnail
/ 大家現在出門買東西還會帶錢包嗎 鴨鴨發現自己好像快一個禮拜沒帶錢包出門 還是可以天天買滿買好回家(? 因此為了記錄手機消費跟各種紅利優惠 鴨鴨都會特別注意銀行的App好不好用! 像是介面設計就是會很在意的地方 很多銀行通常會為了要滿足不同客群 會推出很多App讓使用者下載 每次
介紹如何在模擬物體運動時,引入加速度這個物理量。
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 1.2.6 熱的傳導 1.2.7 十九世紀的尾聲 三 必須說一下波希米亞數學家/邏輯學家/哲學家/神學
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 1.2.6 熱的傳導 1.2.7 十九世紀的尾聲 一 函數概念的發展不可能終結,踏入公元廿一世紀,數學
Thumbnail
這一節談的是向量的定義,以及如何運用向量來建立模擬物體運動時,關於位置和速度間的關係式。
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 1.2.6 熱的傳導 一 偏微分方程始於公元十八世紀,在十九世紀茁長壯大。 隨著物理科學擴展越深 (理
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 五 特朗貝爾依循當時數學界對函數的普遍理解,視「函數」為任一分析式。 但這時的歐拉宣稱函數不必是正常意義下的
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法 1.2.5 弦的振動 三 1755年,歐拉改變了主意,在《微分學原理》(Institutiones calculi differen
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法  三 有些讀者大概都知道,微積分學有兩個分科﹕一為微分學 (differential calculus),一為積分學 (integ
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法  二 前面說過,牛頓關心的不是抽象的數學問題,他要解決的是天體運動的問題。他知道,假如他擁有該天體在任何一刻的瞬速數據,他便能夠從質量
Thumbnail
直觀理解 導數:考慮的是單一變數的函數,描述的是函數在某點的斜率或變化率。 偏導數:考慮的是多變數函數,描述的是函數在某個變數變化時的變化率,其他變數保持不變。  (針對各維度的調整 或者稱變化 你要調多少) 應用 導數:在物理學中應用廣泛,例如描述速度和加速度。 偏導數:在多變量分析、優