算法時間復雜度：講算法中基本操作的次數作為算法時間復雜度的度量

?

void fun(int n) {int i=0;s=0;while(s<n){++i;s=s+i;}}

求算法時間復雜度首先找出基本操作，有函數看出，++i,s=s+i屬于基本操作，然后找出基本操作結束的那個點。如果假設循環執行m次結束，帶入數據求出遞推式。

?

i=0,s=0,???? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? i=1,s=1

i=1,s=1,??????????????????????????????????????? i=2,s=1+2

i=2,s=1+2,?????????????????????????????????? i=3,s=1+2+3

如果循環執行m次，則有:1+2+3.......+m+k=n(其中k為常數，用作不缺),1+2+3+....m的遞推式為s=m(m+1)/2.

求遞推式要用到：等差數列求和：s=na+dn(n-1)/2,其中a為首項，d為公差

??????????????????????????????? 求n公式：△=b^2-4ac

最后解得：T(n)=O(√n)????? ，要把n的系數變為1

?

?

void mergesort(int i,int j) {int m;if(i!=j){m=(i+j)/2;mergesort(i,m);mersort(m+1,j);merge(i,j,m);//本函數時間復雜度為O(n)}}

由函數可知：基本操作在if函數中。先研究if里面的式子，m=(i+j)/2,m的值應該位于i到j的中部，mersort(i,m)執行的式前一部分，mersort(m+1,j)執行的式后一部分。

?

函數規模為n,終止條件i!=j，也就是一直運行到i=j。

merge函數的時間復雜度為n,則基本操作的次數為cn(c為系數，只用湊合表示基本次數)。

f(n)=2f(n/2)+cn

f(n/2)=2f(n/4)+(1/2)cn??? 然后依次類推，就會得到遞推式??? f(n)=2^kf(n/(2^k))+kcn

f(1)=O(1)???? ,? 當n=2^k時(k等于log以2為底n的對數)? ,?? f(n)=O(1)*n+cnlog2n(那個2為底數)

則復雜度T(n)=O(nlog2n)??

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的分析算法时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。