python - 2 つの単純な再帰関数の Big-O 表記

Question

Python には 2 つの再帰関数があり、それらの Big O 表記法を知りたいだけです。これらのそれぞれの Big O は何ですか?

def cost(n):
    if n == 0:
        return 1
    else:
        return cost(n-1) + cost(n-1)

def cost(n):
    if n == 0:
        return 1
    else:
        return 2*cost(n-1)

Answer 1

再帰関係を使って解決しよう！最初の関数の実行時間は、次のように再帰的に記述できます。

T(0) = 1

T(n + 1) = 2T(n) + 1

つまり、基本ケースは完了するのに 1 時間単位かかります。それ以外の場合は、問題の小さなインスタンスに対して 2 回の再帰呼び出しを行い、ある程度のセットアップとクリーンアップ作業を行います。この再帰のいくつかの項を展開すると、次のようになります。

• T(0) = 1
• T(1) = 2T(0) + 1 = 2 + 1 = 3
• T(2) = 2T(1) + 1 = 2 × 3 + 1 = 7
• T(3) = 2T(2) + 1 = 2 × 7 + 1 = 15

^{この級数 1, 3, 7, 15, ... は 2 1} - 1, 2 ² - 1, 2 ³ - 1 などなので、見覚えがあるかもしれません。より一般的に、次のことを証明できます。

T(n) = 2 ⁿ⁺¹ - 1

これは誘導によって行うことができます。基本ケースとして、T(0) = 1 = 2 ¹ - 1 であるため、この主張は n = 0 についても成り立ちます。ここで、ある n について T(n) = 2 ⁿ⁺¹ - 1であると仮定します。

T(n + 1) = 2T(n) + 1 = 2(2 ⁿ⁺¹ - 1) + 1 = 2 ⁿ⁺² - 2 + 1 = 2 ⁿ⁺² - 1

これで完了です。この再帰は 2 ⁿ⁺¹ - 1 = 2(2 ⁿ ) - 1 になるので、実行時間は Θ(2 ⁿ ) になります。

2 番目の関数の実行時間は、次のように再帰的に記述できます。

T(0) = 1

T(n + 1) = T(n) + 1

いくつかの用語を展開します:

• T(0) = 1
• T(1) = T(0) + 1 = 1 + 1 = 2
• T(2) = T(1) + 1 = 2 + 1 = 3
• T(3) = T(2) + 1 = 3 + 1 = 4

これにより、1、2、3、4、... が得られるため、より一般的には次のように推測できます。

T(n) = n + 1

これを再び帰納的に証明できます。基本的なケースとして、n = 0 の場合、T(0) = 1 = 0 + 1 となります。帰納的ステップでは、いくつかの n について T(n) = n + 1 であると仮定します。

T(n + 1) = T(n) + 1 = n + 1 + 1 = n + 2

これで完了です。実行時間は n + 1 なので、実行時間は Θ(n) です。

お役に立てれば！