0

私はいくつかの質問をしていますが、答えが提供されていないので、私の答えが正しいかどうか疑問に思っていました

a) a[i....j] が n 個の要素を持つ整数配列であり、x が整数である場合

int front, back;

while(i <= j) {

    front = (i + j) / 3; 
    back = 2 * (i + j) / 3;

    if(a[front] == x)
        return front;
    if (a[back] ==x)
        return back;

    if(x < a[front])
        j = front - 1;
    else if(x > a[back])
        i = back+1;
    else {
        j = back-1;
        i = front + 1;
    }
}

私の答えは O(1) ですが、私は間違っていると感じています。

B)

public static void whatIs(int n) {
    if (n > 0)
        System.out.print(n+" "+whatIs(n/2)+" "+whatIs(n/2));
}

ans: 再帰が 2 回発生するため、log4n なのか logn なのかわかりません。

4

3 に答える 3

4

A) はい。 O(1)間違っている。、、...、および配列の内容に応じてi、何度もループを回っています。最良のケースと最悪のケースで、ループを何回回るか計算してください。jx

B) (基本的な高校の数学)log(4*n)を使用して簡略化し、ビッグ O の定義を適用します。log(a*b) -> log(a) + log(b)

しかし、それも正しい答えではありません。もう一度、最初の原則に戻って、 parameter の特定の値に対してメソッドが呼び出される回数をカウントする必要がありますn。そして、帰納法による証明を行います。

于 2012-04-10T06:49:59.840 に答える
0

どちらの答えも正しくありません。

各反復の最初の例では、数値を見つけるか、間隔の長さを 1/3 縮小します。つまり、以前の長さが n だった場合、(2/3)*n にします。最悪の場合、最後の反復で x が見つかります - 間隔の長さが 1 の場合です。したがって、二分探索と同様に、ログを介して複雑さが計算されます。複雑さは O(log 3/2 (n)) であり、これは実際にはは単純に O(log(n))

与えられた数 n の 2 番目の例では、n/2 に必要な演算数の 2 倍を実行します。n = 0 および n = 1 から開始し、帰納法を使用して複雑さが実際に O(n) であることを証明します。

お役に立てれば。

于 2012-04-10T06:49:28.877 に答える
0

A) このアルゴリズムは黄金分割探索に似ているようです。複雑さを分析する場合、データ構造を縮小するよりも拡張するとどうなるかを想像しやすい場合があります。次のように考えてください: すべてのループは、検索間隔から 3 分の 1 を削除します。つまり、特定の長さにかかる時間が正確にわかっている場合、もう一度ループできるようになれば、さらに 50% 追加できるということです。これは指数関数的な増加です。したがって、検索アルゴリズムの複雑さは O(log n )でなければなりません。

B) 関数呼び出しの「レイヤー」を追加するたびに、それらの数を 2 倍にする必要があります (関数は常に自分自身を 2 回呼び出すため)。言い換えれば、特定の長さと時間消費が与えられた場合、nを 2 倍にすると、最後の層で 2 倍の関数呼び出しが必要になります。アルゴリズムは O( n ) です。

于 2012-04-10T07:10:07.167 に答える