循序漸進學習時間複雜度
一、淺談演算法
學習軟體開發這麼多年,常常聽到程式=資料結構+演算法,但是很多人對這句話提出質疑,因為實際專案開發的時候大部分人是做螺絲釘的角色,而且大部分甘於做螺絲釘的角色,就會認為實際專案,只是完成業務開發而已,去哪都是增刪改查,資料結構根本用不到。我認為,演算法和基本的資料結構是非常重要的,對於一個合格的程式猿來說,有時候我們沒有涉及到,只是別人把需要的事情都給我們做了,比如的java版本的hashmap,採用紅黑樹的結構,提高了更多效率,軟體開發高速發展的同時,程式設計的門檻也會越來越低,只有瞭解了最本質的才會不被技術淘汰。
演算法的五大特性:
1.有窮性:不是數學,演算法比較合理,每一步在規定時間內進行 2.確定性:每一條指令都有一個明確的含義 3.可行性:演算法可以執行 4.輸入0或者多個 5.輸出 只有一個
演算法設計的四大要求:
1.正確性
2.可讀性
3.健壯性:容錯能力,輸入資料非法的時候,不會產生的輸出結果
邊界問題 (陣列的長度的判斷,非法欄位,樹Root是否為空)
4.效率和儲存
注:1.研究演算法的複雜度,側重的是研究演算法隨著輸入規模擴大增長量的一個抽象,而不是精確定位執行多少次
2. 不關心編譯語言,不關心機器
所以我們應該用什麼方式進行演算法的度量方式呢?接下來我們聊聊時間複雜度
二、時間複雜度
1.概述
我們知道程式的效率可以稱之為程式的時間複雜度,通俗點說就是演算法執行的時間,所以將演算法中基本操作的執行次數作為演算法時間複雜度的度量。
比如:如何求1+2+..... n的結果
第一種:O(n)
int sum=0; for(int i=0;i<=n;i++){ sum=sum+i; }
第二種:O(1)
int i=0; int sum=0; sum =(1+n)*n/2;
上述的例子可以說明如果不同的策略對待同一個需求而已,時間複雜度是不一樣的,演算法的優化,時間複雜度越低也是演算法優化的目的之一。
時間複雜度:演算法中基本語句重複執行的次數是問題規模n的某個函式f(n),演算法的時間量度記作: \(T(n)=O(f(n))\) 表示隨著n的增大,演算法執行的時間的增長率和f(n)的增長率相同,稱漸近時間複雜度。
函式的漸進增長:給定兩個函式,f(n).g(n),如果存在一個整數N,使得對於所有的n>N,f(n)總是比g(n)大,那麼我們說f(n)的增長漸進快於g(n)
上面討論的時間複雜度是官方解釋,仔細可以看時間複雜度可以表示漸進函式的抽象形式即可。
2.時間複雜度的記法:
1.大O記號 (常用)
假設 \(f(n)和g(n)\) 的定義域是非負整數,存在兩個正整數c和n0,使得n>n0的時候, \(f(n)≤c*g(n)\) ,則 \(f(n)=O(g(n))\) 。可見 \(O(g(n))\) 可以表示演算法執行時間的上界。 \(O(g(n))\) 表示的函式集合的函式是階數不超過 \(g(n)\) 的函式。
例如: \(f(n)=2*n+2=O(n)\)
證明:
\(當n>3的時候,2*n +2<3n,所以可選n0=3,c=3,則n>n0的時候,f(n)<c*(n),所以f(n)=O(n)。\)
現在再證明 \(f(n)=2*n+2=O(n^2)\)
證明: \(當n>2的時候,2*n+2<2*n^2,所以可選n0=2,c=2,則n>n0的時候,f(n)<c*(n^2),所以f(n)=O(n^2)。\)
同理可證 \(f(n)=O(n^a)\) ,a>1
2.Ω記號
\(f(n) > c*g(n)\)
Ω記號與大O記號相反,他可以表示演算法執行時間的下界。
\(Ω(g(n))\)
表示的函式集合的函式是所有階數超過g(n)的函式。
例如: \(f(n)=2*n^2+3*n+2=Ω(n^2)\)
證明: \(當n>4的時候,2*n^2+3*n+2>n^2,所以可選n0=4,c=1,則n>n0的時候,f(n)>c*(n^2),所以f(n)=Ω(n^2)。\)
同理可證 \(f(n)=Ω(n),f(n)=Ω(1)\)
3.Θ記號
Θ記號介於大O記號和Ω記號之間。他表示,存在正常數c1,c2,n0,當n>n0的時候, \(c1*g(n)≤f(n)≤c2*g(n)\) ,則f \((n)=Θ(g(n))\) 。他表示所有階數與g(n)相同的函式集合。
4.小o記號
\(f(n)=o(g(n))當且僅當f(n)=O(g(n))且f(n)≠Ω(g(n))\) 。也就是說小o記號可以表示時間複雜度的上界,但是一定不等於下界。
5.例子
假設f(n)=2n^2+3n+5,
則f(n)=O(n^2)或者f(n) = O(n^3)或者f(n)=O(n^4)或者……
f(n)=Ω(n^2)或者f(n)=Ω(n)或者f(n)=Ω(1)
f(n)=Θ(n^2)
f(n) = o(n^3)或者f(n)=o(n^4)或者f(n)=o(n^5)或者……
3.時間複雜度型別
1.常數階
如上面的例子可以知道,執行次數是常數,可以定為O(1)
int i=0; int sum=0; sum =(1+n)*n/2;
2.線性階
如上述的例子可以知道,單次迴圈n,定為O(n)
int sum=0; for(int i=0;i<=n;i++){ sum=sum+i; }
3.對數階
下面程式碼就表示是 \(O(logn)\)
while (left <= right) { int mid = (left - right) / 2 + right; if (target == nums[mid]) { return mid; } else if (target > nums[mid]) { left = mid + 1; } else { right = mid - 1; } }
4.函式呼叫
main方法呼叫外部方法,兩個方法都是一層迴圈,則 \(O(n^2)\)
int main(int argc, char *argv[]) { for(int i=0;i<n;i++){ fun(n); } } void fun(int count){ for(int i=0;i<count;i++){ printf(); } }
常見時間複雜度的比較:
\(O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)...<O(n!)<O(nn)\)
4. 時間複雜度的計算
1.計算規則
1) 加法規則
\(T(n,m) = T1(n) + T2(n) = O ( max (f(n), g(m) ) \)
2) 乘法規則
\(T(n,m) = T1(n) * T2(m) = O (f(n) * g(m)) \)
\(O(n)*O(m)=O(n*m)\)
3)一個特例
在大O表示法裡面有 \(T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )\) . 一個特例,如果 \(T1(n) = O(cf(n))\) , c是一個與n無關的任意常數,$T2(n) = O ( f(n) ) $則有
總結:
1.用常數1取代所有的加法常數 t(n)=5 O(1)
-
修改後的函式中,只保留最高階數
3.如果最高階數的常數部分存在不是1,變成1。
比如:
\(T(n) = n^3 + n^2 + 29,此時時間複雜度為 O(n^3)。 T(n) = 3n^3,此時時間複雜度為 O(n^3)\)
。
2.主定理
在演算法分析中,主定理(英語:master theorem)提供了用漸近符號(大O符號)表示許多由分治法得到的遞推關係式的方法。這種方法最初由Jon Bentlery,Dorothea Haken和James B. Saxe在1980年提出,在那裡被描述為解決這種遞推的“天下無敵法”(master method)。此方法經由經典演算法教科書Cormen,Leiserson,Rivest和Stein的《演算法導論》 (introduction to algorithm) 推廣而為人熟知
解釋: 上面的主定理就是根據遞迴式,我們需要找到它的時間複雜度,這裡為了不區別其他的表示法,全部記為大O表示法,
例子1:
假設問題規模為N,某一個遞迴演算法的時間程度記T(N),已知T(1) = 0,T(N) = T(N/2) + N,求用O表示該演算法的時間複雜度?
分析:直接套用公式可知,a = 1, b = 2 ,f(n) = N , 主定理主要和 \(n^{\log_b a}\) 做比較,帶入可得 \(n^{\log_b a}= 1\) 。
所以f(n)>
\(n^{\log_b a}\)
,符合條件三,所以T(n) = O(n)。
例子2:
假設問題規模為N,某一個遞迴演算法的時間程度記T(N),已知T(1) = 0,T(N) = 2T(N/2) + N/2,求用O表示該演算法的時間複雜度?
分析:直接套用公式可知,a = 2, b = 2 ,f(n) = N/2 , 主定理主要和 \(n^{\log_b a}\) 做比較,帶入可得 \(n^{\log_b a}= n\) 。
這裡需要注意,f(n)和 \(n^{\log_b a}\)做比較 ,比較的是它們的漸近增長率,所以f(n)=
\(n^{\log_b a}\)
,符合條件二,都是一次函式,所以T(n) = O(nlogn)。
例子3:
求下面程式碼的時間複雜度:
void Hanoi(int n, char a, char b, char c)//a為原始柱,b為藉助柱,c為目標柱 { if (n == 1) { Move(a, c);//只有一個盤子時直接移 } else { Hanoi(n - 1, a, c, b);//將A柱子上n-1個盤子藉助C柱子移到B上 Move(a, c);//將A最後一個盤子移到C上 Hanoi(n - 1, b, a, c);//將B柱子藉助空A柱子移到C上 } }
分析:我們可以看出,用遞迴來解決漢諾塔問題是非常方便的選擇,最後我們來分析一下漢諾塔問題的時間複雜度。
設盤子個數為n時,需要T(n)步,把A柱子n-1個盤子移到B柱子,需要T(n-1)步,A柱子最後一個盤子移到C柱子一步,B柱子上n-1個盤子移到C柱子上T(n-1)步。 得遞推公式T(n)=2T(n-1)+1 。這個遞推式子不符合主定理,所以需要運用高中的基礎數學知識,
由遞推式可以知道,湊方法,湊成等比數列,湊成通項公式
\(O(2^n)\)
例子4:
假設問題規模為N,某一個遞迴演算法的時間程度記T(N),已知T(1) = 0,T(N) = T(N- 1) + N,求用O表示該演算法的時間複雜度?
分析:首先要看主定理的限定的條件,b > 1 才可以執行這個主定理,這裡需要 \(T(N) = T(N- 1) + N 變成 T(N) - T(N- 1) = N。 可以T(1) ,T(2) .... T(N) 疊加後可以算出T(N)的通項公式。 可以計算O(n^2)\)
三、空間複雜度
類比於時間複雜度的討論,一個演算法的空間複雜度是指該演算法所耗費的儲存空間,計算公式計作:S(n) = O(f(n))。其中 n 也為資料的規模,f(n) 在這裡指的是 n 所佔儲存空間的函式。一般情況下,我們的程式在機器上執行時,刨去需要儲存程式本身的輸入資料等之外,還需要儲存對資料操作的「儲存單元」。如果輸入資料所佔空間和演算法無關,只取決於問題本身,那麼只需要分析演算法在實現過程中所佔的「輔助單元」即可。如果所需的輔助單元是個常數,那麼空間複雜度就是 O(1)。
吐槽:我被部落格園的markdown的編輯器弄瘋了,花了我好長時間,我只是想排版好看一點,就用數學公式進行,而不是用圖片的方式,結果部落格園不支援$$ 解析,當然官方部落格也給瞭解決方案,但是沒用好嗎?對於不是整段的數學公式是不起作用的 , ofollow,noindex" target="_blank">https://www.cnblogs.com/cmt/p/markdown-latex.html
正確做法:加入這個放入文章內
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>
,MathJax可以解析Latex、MathML和ASCIIMathML的標記語言,就可以用$ 解析了,使用就是正常的。
https://blog.csdn.net/qq_33274645/article/details/52688025
https://mp.weixin.qq.com/s/9njtnqfAatjmjPh4geETqA