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

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

実行時間を見つけるにはどうすればよいですか?Big O notationまた、遅延評価 (値が必要になるまで式を評価しない) はこれにどのように影響しますか?

最初のものO(n)は単一の再帰呼び出しO(n^2)によるもので、2 つ目は別の再帰呼び出し内の再帰呼び出しによるものでしょうか? 以前に見た例に基づいて推測する方法しか知りません。:(

4

1 に答える 1

3
  • foo()ですO(2^n)（interpeterによるキャッシングの最適化がないことを前提としています）。
  • bar()is O(infinity)(決して終了しない) でありO(n)、遅延評価あり

説明:
それぞれが へのfoo(n)2 つの呼び出しを呼び出すf(n-1)ため、複雑な関数が得られます。

T(n) = T(n-1) + T(n-1) = T(n-2) + T(n-2) + T(n-2) + T(n-2) = ... = 2^(n-5)*T(5)

(その部分は数学的帰納法...を使って形式的に証明できる)

- で再帰的に呼び出されると仮定するため、bar(n)は無限ループに入ります。これは制約も満たします。帰納法により、 withの余分な呼び出しがすべてあることを取得できます-これにより、の呼び出しが無限に発生します-したがってb>0b+1b>0b>0bar()b'>bbar()O(infinity)

遅延評価では、2 番目のメソッド ( bar()) は になりO(n)ます。
これは、無限再帰が評価するためだけに発生するためですa- ただし、aは実際には使用されないため、引数の式を評価する必要はなく、aすべてbの再帰呼び出しが減少するため、次のようになります。O(n)

の正式な証明T(n) = T(n-1) + T(n-1)は次のO(2^n)とおりです。

基数: T(5) = CONST
仮定:T(k) <= CONST * 2^k各k<n
証明:

T(n) = T(n-1) + T(n-1) <= (assumption) <= CONST* 2^(n-1) + CONST* 2^(n-1) = 
     = CONST*2*2^(n-1)  = CONST * 2^n

数学的帰納法から、仮定は正しくT(n)、O(2^n)

于 2012-11-29T09:10:26.903 に答える