遞推公式求演算法的時間復雜度

⑴ 這個演算法的時間復雜度是如何計算出來的

如果題目允許優化程序的話，計算X的多次冪時可以保留中間結果，比如你已經有了X^3，計算X^4的時候就不用從頭乘一遍，也不用二分著來，直接X^3在乘X就可以了。如果採用這樣的策略，這題是可以以O(N)實現的。

如果不考慮上面所說，復雜度是NlogN，你的計算過程可行。另外也可估算，即單次求冪是logN，求N次就是NlogN，這樣估出來的是上界。但是在不保留中間結果的演算法下，是無法達成O（N）的，故可以不嚴謹地「直覺」知道下界也是NlogN。

⑵ 如何計算一個演算法的時間復雜度

求解演算法的時間復雜度的具體步驟是：

1、找出演算法中的基本語句：

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

2、計算基本語句的執行次數的數量級：

（1）只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。

（2）這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

3、用大Ο記號表示演算法的時間性能：

（1）將基本語句執行次數的數量級放入大Ο記號中。

（2）如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如：

for(i=1;i<=n;i++)x++;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)x++;

（3）第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。

⑶ 演算法的時間復雜度的計算

n的平方*2
1.比較次數：
i:n-1約等於n
j:1+2+3+……+(n-1)=(n方-n)/2
總：n+(n方-n)/2=（n方+n）/2
2.加法運算次數
i：約為n
j：(n方-n)/2
x：(n方-n)/2
總：相加得n方
3.賦值運算次數
a[i][j]：(n方-n)/2

總的時間復雜度約為
（n方+n）/2+n方+(n方-n)/2=2n方

⑷ 快速排序時間復雜度遞推式求通項公式~

兩邊同除以n(n+1)得到
C(n)/(n+1) = 2/(n+1) + C(n-1)/n
然後取n=1,2,...求和得到
C(n)/(n+1) = 2(1/2+...+1/(n+1)) + O(1) = 2lnn + O(1)
所以C(n)=2nlnn + O(n)

⑸ 設某演算法的計算時間表示位遞推關系式T(n)=T(n-1)+n(n位正整數)及T(0)=1,則該演算法的時間復雜度為

選擇D.

T(n)
=T(n-1)+n
=T(n-2)+(n-1)+n
=T(n-3)+(n-2)+(n-1)+n
...
=T(0)+1+2+...+(n-2)+(n-1)+n
=1+1+2+...+(n-2)+(n-1)+n
=1+(n+1)*n/2
所以為 O(n²)，選D。

⑹ 根據遞推公式求演算法時間復雜度

這題還有另一種，可以參考MIT 演算法導論，你們圖書館肯定有的，網上可以找到電子版。

或者搜索演算法導論的PPT也可以。

⑺ 求演算法的時間復雜度，要詳細推導過程，循環次數

⑻ 若某演算法的計算時間表示為遞推關系式:T(N)=2T(N/2)+NlogN T(1)=1則該演算法的時間復雜度為

利用分叉樹來做，根結點nlogn，每次下分兩個子樹，結點為n/2logn/2，一直做到最後，發現最後的log裡面的真數為1，也就是0。對每一層加和，第一層nlogn，第二層nlogn/2也就是nlogn-nlog2，以此類推，nlogn-nlog4，nlogn-nlog8，....,nlogn-nlogn。樹高以2為底logn，乘進去為nlogn*logn - n/2*logn -n/2*(logn)^2,就是O（n（logn）^2）。（手機網路回答不會插入圖片，我是這么做的，有錯誤還請指出）

⑼ 怎麼求演算法的時間復雜度

for( i=1; i<=n; i++)
這個語句的時間復雜度也是n， i 的值分別為 1,2,3, ..., n
但是，一般算時間復雜度這幾個都會近似地看成O(n)，常數一般會忽略不計（除非很大的情況下）

⑽ 請問遞歸演算法的時間復雜度如何計算呢

遞歸演算法的時間復雜度在演算法中，當一個演算法中包含遞歸調用時，其時間復雜度的分析會轉化為一個遞歸方程求解，常用以下四種方法：

1.代入法(Substitution Method)

代入法的基本步驟是先推測遞歸方程的顯式解，然後用數學歸納法來驗證該解是否合理。

2.遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的.

3.但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省.