分析運行時間

def foo(x): 
    if x > 5: 
     return foo(x–1) – foo(x-1) 
    else: 
     return 77 

def bar(a,b): 
    if (b > 0): 
     return bar(bar(a, b+1) , b-1) 
    else: 
     return 0

是否有人walk me through如何找到這些的運行時間？對於foo，我的猜測是由於2次遞歸調用，它是O(n^2)。它可能是Θ(n^2)以及？分析運行時間

對於bar，我沒有線索，因爲它是無限遞歸。

來源

2012-11-29 Leon Kingston

停止猜測，並比較了運行時間'foo（x）'和'foo（x-1）'。 – Henrik

你確定'bar'是否正確？看起來它永遠不會終止'b'的正值。至於'O（n^2）'：不，這是不正確的。 – phant0m

[大O表示法和懶惰評估中的運行時間]的可能重複（http://stackoverflow.com/questions/13620069/running-time-in-big-o-notation-and-lazy-evaluation） – amit

對於函數

  _________ 77 if(x<=5) 
     /
     /
foo(x)- 
     \ 
     \_________ foo(x-1) - foo(x-1) if(x>5) 


let f(x) be time function for foo(x) 

f(x) = f(x-1) - f(x-1) // 2 (2^1)calls of f(x-2) happened for 1 level depth 
f(x) = [f(x-2) - f(x-2)] - [ f(x-2) - f(x-2)] (expanding f(x-1)) // 4(2^2) calls of f(x-2) happened for 2nd level depth 
f(x)={[ f(x-3) - f(x-3)]-[ f(x-3) - f(x-3)]} - {[ f(x-3) - f(x-3)]-[ f(x-3) - f(x-3)]} // 8(2^3) calls of f(x-2) happened for 3rd level depth

永不結束個

設I呼叫發生在完成程序....

but program terminates when x<=5, 
so program terminates in call f(x-i) when x-i<=5 
that means i>=x-5 , 
at level i there are 2power(i) calls 
==> 2^i calls of f(x-i). 
since f(<=5)=1(1 is unit of measure) for i>=x-5

所以F（N）= 2 ^（X-5）*（1）=> O（2^x），其中x是輸入大小。如果我們用n代替x，則複雜度爲O（2^n）。

對於第二個問題

  _________ 0 if(b<=0) 
     /
     /
bar(a,b) 
     \ 
     \_________ foo(bar(a,b+1) ,b-1) if(b>0)

令t（n）是用於酒吧時間功能（A，B）其中n爲比例至b爲b是決定終止因子。

擴大reccurence

t(a,b) = t(t(a,b+1), b-1) . 
first t(a,b+1) is executed it inturn calls t(a,b+2) and so on.... 
it will be infinite recursion ..... for b > 0 .

據我所知，因爲我們不具備長焦界限（沒有下限，也沒有上限，所以沒有THETA符號和無大哦符號，從而歐米茄符號），我們傾斜測量複雜功能爲好。（請糾正我，如果我錯了）

但是，若b < 0，那麼它會在O完成（1）時間...

來源

2012-11-29 09:17:02 Imposter

顯然foo(n)不是在多項式時間：

T(n) = 2T(n-1) , if n > 5 
    = Theta(1) , otherwise

因此

T(n) = Theta(2^n)

bar(a,b)只要b > 0

來源

2012-11-29 08:53:09 xiaoyi

分析運行時間

回答

相關問題