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

更新於 發佈於 閱讀時間約 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
留言分享你的想法!
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
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
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