6

1) 

  x = 25;
    for (int i = 0; i < myArray.length; i++)
    {
        if (myArray[i] == x)
            System.out.println("found!");
    }

これはO(n)だと思います。

2)

for (int r = 0; r < 10000; r++)
    for (int c = 0; c < 10000; c++)
        if (c % r == 0)
            System.out.println("blah!");

入力 n に対して 10000 * 10000 回実行されるため、これは O(1) だと思います。これが正しいかどうかはわかりません。

3)

a = 0
for (int i = 0; i < k; i++)
{
    for (int j = 0; j < i; j++)
        a++;
}

これは O(i * k) だと思います。外側のループでインクリメントされる変数によって内側のループが影響を受ける、このような問題にアプローチする方法がよくわかりません。ここでいくつかの重要な洞察をいただければ幸いです。外側のループは k 回実行され、内側のループは 1 + 2 + 3 + ... + k 回実行されます。したがって、その合計は (k/2) * (k+1) で、k^2 の順序になります。では、実際には O(k^3) でしょうか? それは大きすぎるようです。繰り返しますが、これにアプローチする方法がわかりません。

4)

int key = 0;    //key may be any value
int first = 0;
int last = intArray.length-1;;
int mid = 0;
boolean found = false;

while( (!found) && (first <= last) )
{
    mid = (first + last) / 2;

    if(key == intArray[mid]) 
        found = true;
    if(key < intArray[mid])
        last = mid - 1;
    if(key > intArray[mid]) 
        first = mid + 1;
}

これは、O(log n) だと思います。しかし、私はそれが二分探索であると信じており、ランタイムが O(log n) であることを読んで知っているので、この結論に達しました。ループの反復ごとに入力サイズを 2 で除算するためだと思います。しかし、これが正しい推論なのか、それとも私が見たことのない同様のアルゴリズムにアプローチする方法なのか、それらが対数時間でより検証可能または正式な方法で実行されると推測できるのかはわかりません。

5)

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

私はこれについて混乱しています。外側のループは n 回実行されます。内側の for ループは n + (n-1) + (n-2) + ... (n - k) + 1 回実行されますか? それはO(n^3)ですか??

4

3 に答える 3

2

多かれ少なかれ、はい。

1 は正しいです。ソートされていないコレクションであると想定している特定の要素を検索しているようです。その場合、最悪のケースは、要素がリストの最後にあることです。つまり、O(n) です。

2 は正しいですが、少し奇妙です。これは O(1)rでありc、定数であり、境界は変数ではありません。それらが定数の場合、入力するものが何もないため、はい O(1) です。

3 まだ O(n^2) と見なされていると思います。k * n^2 のような定数係数があり、定数を削除すると O(n^2) が得られます。

4 は、ソートされたコレクションのバイナリ検索アルゴリズムによく似ています。O(logn) は正しいです。各反復で、探している要素が含まれる可能性のある選択肢の数を本質的に半分にしているため、ログです。

5 は 3 と同様の理由でバブル ソート O(n^2) のように見えます。

于 2012-07-13T19:39:16.777 に答える
1

O() はそれ自体では何の意味もありません。「最悪のケース」の O をカウントするか、平均的なケースの O をカウントするかを指定する必要があります。一部のソート アルゴリズムでは、平均で O(n log n) になります。ただし、最悪の場合は O(n^2) です。

基本的に、最も内側のループの反復の総数を数え、定数なしで結果の最大コンポーネントを取得する必要があります (たとえば、k*(k+1)/2 = 1/2 k^2 + 1/2 k、最大のコンポーネントは 1/2 k^2 なので、O(k^2)) です。

たとえば、アイテム 4) は O(log(n)) にあります。これは、サイズ n の配列で作業する場合、この配列で 1 回の反復を実行し、次の反復がサイズ n の配列で実行されるためです。 /2、次に n/4、...、このサイズが 1 に達するまで。つまり、log(n) 回の反復です。

于 2012-07-13T19:43:17.800 に答える
1

あなたの質問は主に O() の定義に関するものです。

このアルゴリズムが O(log(n)) であると誰かが言うとき、あなたは読む必要があります:

入力パラメーター n が非常に大きくなると、アルゴリズムによって実行される操作の数は最大でも log(n) で増加します。

さて、これは次の 2 つのことを意味します。

  1. 少なくとも 1 つの入力パラメーター n が必要です。O() について話すのは意味がありません (ケース 2 のように)。
  2. カウントする操作を定義する必要があります。これらは加算、2 つの要素間の比較、割り当てられたバイト数、関数呼び出しの数ですが、決定する必要があります。通常、最もコストのかかる操作、または何度も実行するとコストが高くなる操作を実行します。

したがって、これを念頭に置いて、問題に戻ります。

  1. n は myArray.Length で、数えている操作の数は「==」です。その場合、答えは正確に n であり、これは O(n) です。

  2. n は指定できません

  3. n は k のみであり、カウントする操作の数は ++ です。あなたが言うように、正確に k*(k+1)/2 である O(n2) があります

  4. 今回も n は配列の長さであり、カウントする操作は == です。この場合、操作の数はデータによって異なります。通常、「最悪のシナリオ」について話します。つまり、考えられるすべての結果のうち、最も時間がかかるものを調べます。せいぜい、アルゴリズムは 1 回の比較しか行いません。最悪のケースとして、例を挙げてみましょう。配列が [[1,2,3,4,5,6,7,8,9]] で、4 を探している場合、intArray[mid] は連続して 5、3、4 のようになります。比較を 3 回行ったことになります。実際、サイズが 2^k + 1 の配列の場合、最大比較回数は k 回です (確認できます)。したがって、n = 2^k + 1 => k = ln(n-1)/ln(2) です。この結果を n = 2^k + 1 でない場合に拡張すると、複雑さ = O(ln(n)) が得られます。

いずれにしても、O(n) の意味を正確に理解していないため、混乱していると思います。これが始まりであることを願っています。

于 2012-07-13T21:54:15.393 に答える