演算法筆記|演算法效能分析:時間複雜度與空間複雜度

更新 發佈閱讀 2 分鐘

一、怎麼判斷好的演算法或不好的演算法?


  面對同樣的問題,好的演算法只要1秒就可以解決,不好的演算法可能要好幾萬年才能解決,因此我們就提出了2種分析演算法效能的方法,時間複雜度和空間複雜度。



二、時間複雜度的分析


  因為每台電腦執行同個程式所要花的時間不一樣,所以我們不會直接測量執行程式所需要的時間,相對的,我們會分析程式碼所需要花費時間的數量級數,下圖程式碼片段示範了如何進行時間複雜度的分析與計算


##第一部分
for i in range(n): #執行n次
for j in range(n): #執行n次
print("hello")

for i in range(n): #執行n次
for j in range(n): #執行n次
print("world")

##第二部分

for i in range(n): #執行n次
print("!!!")

print("任務完成") #執行1


上面的程式碼片段,第一部分因為執行了2個雙重 for 迴圈,所以執行次數是 

2n^2,第二部分執行了一個 for 迴圈和輸出任務完成,執行次數是 n+1。整段程式碼總共的執行次數是 2(n^2)+n+1。


  我們使用big-O 的方式分析時間複雜度,因為當n得值很大的時候 

n^2>>>n,所以我們計算big-O 只取最高項次的項並去係數,以此程式碼為例是O(n)=n^2,因此我們可以說這支程式碼的時間複雜度為 O(n)=n^2 。


  另外還有4種分析時間複雜度及更精準的計算方式留待未來有機會再寫xd,以下提供關鍵字,如果有興趣的人可以在自行搜尋。

關鍵字:small-o、big-ω、small-ω、big-θ



三、空間複雜度的分析


  空間複雜度與程式在執行的時候所需要佔用的記憶體空間有關,因為現在電腦的記憶體空間大多很充足,所以時間複雜度的重要性優於空間複雜度,在大學階段寫的程式基本上都不需要考慮空間上的問題,因此只需要大略知道即可。


  資料在記憶體中的擺放方式稱為資料結構,不同的擺放方式會影響我們存取資料或排序資料所需要花費的時間。常見的資料結構有陣列、鍊結串列、佇列、堆疊、二元樹、堆積樹、雜湊表等,會在後續的文章說明並提及相關的演算法。

留言
avatar-img
資治通艦的沙龍
3會員
45內容數
人生中有的時候你會感知到,現在就是那個命運的分歧點,如果我不挽起袖子努力的話,我這一輩子大概就這樣了,所以我決定開始這個部落格,記錄我每天的努力,也希望可以分享學習的筆記與心得,大家可以一起交流學習。
資治通艦的沙龍的其他內容
2025/04/08
請使用 C 或 Java 語言寫一副程式,此副程式對一個長度為 10 的整數陣列 A[0:9],最多花費 15 次的數值比較運算,尋找陣列中的最小值及最大值,並分別存入 Min 及 Max。(注意:請加註解說明程式碼寫法) 【103.關務】
Thumbnail
2025/04/08
請使用 C 或 Java 語言寫一副程式,此副程式對一個長度為 10 的整數陣列 A[0:9],最多花費 15 次的數值比較運算,尋找陣列中的最小值及最大值,並分別存入 Min 及 Max。(注意:請加註解說明程式碼寫法) 【103.關務】
Thumbnail
2025/04/07
第 1 題 題目 設有一三維陣列(three dimensional matrix) A[1...u₁, 1...u₂, 1...u₃],請問其中一元素(element)A[i,j,k] 之儲存位置為何?其中 1 ≤ i ≤ u₁,1 ≤ j ≤ u₂,1 ≤ k ≤ u₃,請列出推導過程。
Thumbnail
2025/04/07
第 1 題 題目 設有一三維陣列(three dimensional matrix) A[1...u₁, 1...u₂, 1...u₃],請問其中一元素(element)A[i,j,k] 之儲存位置為何?其中 1 ≤ i ≤ u₁,1 ≤ j ≤ u₂,1 ≤ k ≤ u₃,請列出推導過程。
Thumbnail
2025/04/07
陣列和鏈結串列的比較以及陣列位址的計算方式
Thumbnail
2025/04/07
陣列和鏈結串列的比較以及陣列位址的計算方式
Thumbnail
看更多
你可能也想看
Thumbnail
在 vocus 與你一起探索內容、發掘靈感的路上,我們又將啟動新的冒險——vocus App 正式推出! 現在起,你可以在 iOS App Store 下載全新上架的 vocus App。 無論是在通勤路上、日常空檔,或一天結束後的放鬆時刻,都能自在沈浸在內容宇宙中。
Thumbnail
在 vocus 與你一起探索內容、發掘靈感的路上,我們又將啟動新的冒險——vocus App 正式推出! 現在起,你可以在 iOS App Store 下載全新上架的 vocus App。 無論是在通勤路上、日常空檔,或一天結束後的放鬆時刻,都能自在沈浸在內容宇宙中。
Thumbnail
vocus 慶祝推出 App,舉辦 2026 全站慶。推出精選內容與數位商品折扣,訂單免費與紅包抽獎、新註冊會員專屬活動、Boba Boost 贊助抽紅包,以及全站徵文,並邀請你一起來回顧過去的一年, vocus 與創作者共同留下了哪些精彩創作。
Thumbnail
vocus 慶祝推出 App,舉辦 2026 全站慶。推出精選內容與數位商品折扣,訂單免費與紅包抽獎、新註冊會員專屬活動、Boba Boost 贊助抽紅包,以及全站徵文,並邀請你一起來回顧過去的一年, vocus 與創作者共同留下了哪些精彩創作。
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
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弦的振動  七 雖然論爭沒有得出任何定論,但對函數概念的演化卻影嚮頗深。 在這次歷時多年的論爭中,函數概念得以擴大而包括
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 弦的振動 五 特朗貝爾依循當時數學界對函數的普遍理解,視「函數」為任一分析式。 但這時的歐拉宣稱函數不必是正常意義下的
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 微積分的記法 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 微積分的記法  三 有些讀者大概都知道,微積分學有兩個分科﹕一為微分學 (differential calculus),一為積分學 (integ
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法  二 前面說過,牛頓關心的不是抽象的數學問題,他要解決的是天體運動的問題。他知道,假如他擁有該天體在任何一刻的瞬速數據,他便能夠從質量
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 1.2.3 幾何的方法 1.2.4 微積分的記法  二 前面說過,牛頓關心的不是抽象的數學問題,他要解決的是天體運動的問題。他知道,假如他擁有該天體在任何一刻的瞬速數據,他便能夠從質量
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 函數是數學分析的一大基石,所以從巴比倫﹑古印度﹑古中國到古希臘的數學文獻都有函數的影子,雖然函數概念還不備可供鑒辨的輪廓,其中一個原因是數學的語言還沒有成熟。文字的描述或簡單的算術圖表很
Thumbnail
1.0 從函數到函算語法 1.2 函數概念小史 1.2.1 中譯的來源 1.2.2 一個速度問題 函數是數學分析的一大基石,所以從巴比倫﹑古印度﹑古中國到古希臘的數學文獻都有函數的影子,雖然函數概念還不備可供鑒辨的輪廓,其中一個原因是數學的語言還沒有成熟。文字的描述或簡單的算術圖表很
Thumbnail
目錄 序 導論: 一個西方觀點的評述 1.0 從函數到函數算法 ......1.1 句子成份
Thumbnail
目錄 序 導論: 一個西方觀點的評述 1.0 從函數到函數算法 ......1.1 句子成份
Thumbnail
這篇文章,會帶著大家複習以前學過的前綴和框架, 並且以區間和的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 前綴和 prefix sum框架 與 區間和計算的關係式 接下來,我們會用這個上面這種框架,貫穿一些同類型,有關聯的題目 (請讀者、或觀眾
Thumbnail
這篇文章,會帶著大家複習以前學過的前綴和框架, 並且以區間和的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 前綴和 prefix sum框架 與 區間和計算的關係式 接下來,我們會用這個上面這種框架,貫穿一些同類型,有關聯的題目 (請讀者、或觀眾
Thumbnail
上篇進一步認識基本的圖形架構與三大 Graph 算法,那首先從 shortest path 開始,我們會陸續去理解這些算法,以及可能的應用,如果還沒有看過上一篇的,可以點以下連結~那我們就開始吧! 【圖論Graph】Part1:初探圖形與圖形演算法之應用
Thumbnail
上篇進一步認識基本的圖形架構與三大 Graph 算法,那首先從 shortest path 開始,我們會陸續去理解這些算法,以及可能的應用,如果還沒有看過上一篇的,可以點以下連結~那我們就開始吧! 【圖論Graph】Part1:初探圖形與圖形演算法之應用
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News