0 
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これらの実行時間を見つける方法について誰か教えてください。については、 2 回の再帰呼び出しによるものfooだと思います。O(n^2)それΘ(n^2)もあるでしょうか？

についてbarは、無限再帰なのでわかりません。

4

2 に答える 2

0

機能について

          _________  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

プログラムを完了するために電話をかけましょう。

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は入力サイズです。xをnに置き換えると、複雑さはO（2 ^ n）になります。

2番目の質問

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

t（n）をbar（a、b）の時間関数とします。ここで、bは終了の決定要因であるため、nはbに比例します。

再発の拡大

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  .

私の知る限り、無限大の制限がないため（下限も上限もありません。したがって、シータ表記も、オメガ表記のようなビッグオー表記もありません）、複雑度関数も測定できません（iの場合は修正してください）私は間違っています）

しかし、b <0の場合、O（1）時間で実行されます...

于 2012-11-29T09:17:02.973 に答える
0

明らか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-29T08:53:09.750 に答える