3

Big-O 表記を学習しようとしていますが、再帰関数の時間計算量を計算するのが困難です。

次の例の時間の複雑さを理解するのを手伝ってもらえますか?

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(rand(n)) + 2,recursiveFunction(n - 1));
}

public int rand(int n) {
    return new Random().nextInt(n - 1);
}

ありがとう。

4

4 に答える 4

5

時間は何を返すかによって異なりrand(n)ますが、最悪のケースを取ると、これはn-2. したがって、コードは次のように簡略化されます。

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(n - 2) + 2,recursiveFunction(n - 1));
}

これは、次のものに等しい漸近的な上限を持ちます。

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    recursiveFunction(n-1);
    recursiveFunction(n-1);

    return 0;
}

これは の深さnと の分岐係数を持つ再帰である2ため、O(2^n) の時間複雑度です。

于 2013-01-02T14:18:11.010 に答える
3

再帰関数は、複雑さについて学び始めるのに適した場所ではありません。比較的単純な再帰関数でも、複雑さを判断するために非常に複雑な計算が必要になる場合があります。

For recursiveFunction(n), you call recursiveFunction(n-1)and recursiveFunction(a)where a < n-1, したがって、最悪の場合、それはrecursiveFunction(n-1)1 回とrecursiveFunction(n-2)1 回です。これはフィボナッチ数列と同じ複雑さを持ち、その複雑さは O(2^n)です。リンクのアルゴリズムがあなたのものと非常によく似ていることに気付くでしょう。

于 2013-01-02T14:14:53.890 に答える
0

ここでかなりトリッキーな問題を選択しました。Math.Max を使用した計算はあまり重要ではありません。重要なのは 2 つの再帰呼び出しです。

定義されていない Random().nextInt (0) を呼び出す rand (1) を呼び出すため、n == 1 の場合にここで問題があります。ありえない。0 が返されることを祈りましょう。そうでない場合は、困ったことになります。

recursiveFunction (n) は recursiveFunction (n - 1) を呼び出し、ランダムな i, 0 <= i <= n - 2 を使用して別の呼び出し recursiveFunction (i) を作成します。作成される呼び出しの最大数の表を作成してみましょう。最初の呼び出しでは 1 (rand (1) が 0 を返し、他のすべての呼び出しが n - 2 を返すと仮定):

n = 0: 1 calls
n = 1: 1 + 1 + 1 = 3 calls
n = 2: 1 + 1 + 3 = 5 calls
n = 3: 1 + 3 + 5 = 9 calls
n = 4: 1 + 5 + 9 = 15 calls
n = 5: 1 + 9 + 15 = 25 calls
n = 6: 1 + 15 + 25 = 41 calls
n = 7: 1 + 25 + 41 = 67 calls
n = 8: 1 + 41 + 67 = 109 calls
n = 9: 1 + 67 + 109 = 177 calls
n = 10: 1 + 109 + 177 = 287 calls

呼び出しの数は急速に増加しますが、2^n ほど速くはありません。c = sqrt (1.25) + 0.5 で O (c^n) だと思います。これは最悪のケースです。平均はかなり少ないです。

于 2014-03-23T09:10:39.243 に答える
0

コードの問題を理解していません。コードはランダムな値を作成するため、実行時の複雑さを判断できません。「+2」と「-1」のせいで、プログラムが終わらない可能性もあります。しかし、これはありそうになく可能性があるので、O(infinite) としか言いようがありません。

bigO 表記の通常のケース:

ループは 1 つだけです。

for(int k=0;k<n;++k) {}

n 回の繰り返しがあるため、これは O(n) になります。

連続する 2 つ以上のループ:

for(int k=0;k<n;++k) {}
for(int l=0;l<n;++l) {}

O(2*n)になりますが、bigOでは定数は関係ないのでO(n)です

もつれたループ:

for(int k=0;k<n;++k) {
    for(int l=0;l<n;++l) {
    }
}

はO(n²)、

for(int k=0;k<n;++k) {
    for(int l=0;l<n;++l) {
        for(int m=0;m<n;++m) {
        }
    }
}

は O(n³) など

そして、検索/比較アルゴリズムで遭遇する最も一般的な複雑さは次のとおりです。

for(int k=0;k<n;++k) {
    for(int l=k;l<n;++l) {// note here: l=k instead of l=0
    }
}

O(n*log(n)) です

詳細については、グーグルを使用してください。

于 2013-01-02T14:20:48.440 に答える