計算程序運行時間？

我試圖找出我的分裂程序的運行時間，計算程序運行時間？

void splitX(int x) { 
    if (x<=1) {return x;}; 
    splitX(n/2); 
    System.out.println("splitting in progress"); 
    splitX(n/2); 
    splitX(n/2); 
    splitX(n/2); 
}

我是相當新的這個，這是到目前爲止什麼都做;

T(n) = 4T(n/2) 
    = 4^2T(n/2^2) 
    = 4^3T(n/2^3) 
    = 4^kT(n/2^k) 
    = O(log n)

我在正確的軌道上，即時通訊有點困惑，您是否也要考慮印刷線？

來源

2012-02-19 Lunar

的analyzis是真的，直到最後，解決的辦法是T(n) = O(n^2)

注意4^kT(n/2^k) != O(log n)因爲4^k不是一個常數。
看一看的analyzis：

T(n) = 4T(n/2) = 
    = 4^2T(n/2^2) 
    = 4^3T(n/2^3) 
    = 4^kT(n/2^k) 
    = 4^log(n)*T(1) = 
    = 4^log(n) * 1 = 
    = (2^log(n))^2 = 
    = n^2 
    = O(n^2)

要正式地證明這一點：我們用induction
基地：T(1) = 1 = 1^2
假設T(n) = n^2每個k <= n
T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2

因此歸納假設是真實的， T(n) = n^2

Yo ü也可以檢查wolfram alpha

來源

2012-02-19 13:40:04 amit

非常感謝，你能解釋一下前面的4是如何改變的嗎？會改變它爲3例如改變運行時間？ – Lunar 2012-02-19 16:27:04

@月球：是的。「4在前面」導致公式成爲「力量」。請注意，你的分析得到了'T（n）= 4^k * T（n/2^k）'m，這導致你達到'4 * 4 * ... * 4' [logn times]。如果它是「3在前面」 - 它會是'3 * 3 * ... * 3' [logn次數]，它是'3^logn'[大於n'，小於'n^2' ] – amit 2012-02-19 16:32:05

正如我所看到的，您可以對您的遞歸函數進行日誌（N）調用。乘以一個常數 - 4不會改變複雜性，印刷線也不會改變（對於所有與家庭作業有關的需求）。

來源

2012-02-19 12:14:18 WeaselFox

這是完全錯誤的，因爲「恆定」是4^k，這不是一個常數。答案是'T（n）= O（n^2）'。您可以在我的答案或[wolfram alpha]中查看結果（http://www.wolframalpha.com/input/?i=T%28n%29+%3D+4T%28n%2F2%29%2C+T ％281％29 +％3D + 1） – amit 2012-02-19 13:44:13

@amit，當然，對不對。 – WeaselFox 2012-02-21 09:21:09

是的，在Big-O表示法中，它是O（log n）通過不變來完成。

來源

2012-02-19 12:17:41 mishadoff

這顯然是錯誤的，因爲「常數」是4^k，這不是一個常數。答案是'T（n）= O（n^2）'。您可以在我的答案或[wolfram alpha]中查看結果（http://www.wolframalpha.com/input/?i=T%28n%29+%3D+4T%28n%2F2%29%2C+T ％281％29 +％3D + 1） – amit 2012-02-19 13:44:45

是我的錯，謝謝！ – mishadoff 2012-02-19 13:47:28

表達這一結果是形式的

T（N）= 4T（N/2）+ C

現在用的是= 4，B應用主theorum = 2和f（n）= c;

T（N）= O（N ^洛嘎）//基座2

T（N）= N^2

來源

2012-02-19 16:09:20 pawan

計算程序運行時間？

回答

相關問題