4

注：私はアルゴリズム分析の超初心者なので、私の断言を絶対的な真実と見なさないでください。私が述べていることは何でも（またはすべて）間違っている可能性があります.

こんにちは、アルゴリズム分析と「Big-O-Notation」について読んでいて、何かに戸惑いました。

char 配列のすべての順列を出力するように求められたとします。[a,b,c] の場合、それらは ab、ac、ba、bc、ca、および cb になります。

それを行う1つの方法は次のとおりです（Javaの場合）：

for(int i = 0; i < arr.length; i++)
    for(int q = 0; q < arr.length; q++)
        if(i != q)
            System.out.println(arr[i] + " " + arr[q]);

私が正しければ、このアルゴリズムにはO(n 2 )という表記があります。

私はそれを行う他の方法を考えました：

for(int i = 0; i < arr.length; i++)
    for(int q = i+1; q < arr.length; q++)
    {
        System.out.println(arr[i] + " " + arr[q]);
        System.out.println(arr[q] + " " + arr[i]);
    }

現在、このアルゴリズムは元の よりも 2 倍高速ですが、私が間違っていない限り、big-O 表記ではO( 2 )でもあります。

これは正しいです？おそらくそうではないので、言い換えます: どこが間違っていますか??

4

11 に答える 11

13

あなたは正しいです。O表記は、絶対速度ではなく、アルゴリズムがどのようにスケーリングするかを示します。さらに可能性を追加すると、両方のソリューションは同じようにスケーリングされますが、一方は常に他方の2倍の速度になります。

'n'が十分に小さい場合、O（n）操作はO（n ^ 2）操作よりも遅くなる可能性があります。O（n）の計算に5平方根をとることが含まれ、O（n ^ 2）の解が単一の比較であると想像してください。O（n ^ 2）演算は、データの小さなセットに対してより高速になります。しかし、n = 1000で、5000平方根を実行しているが、1000000の比較を行っている場合、O（n）の見栄えが良くなる可能性があります。

于 2009-06-30T23:49:04.737 に答える
3

ほとんどの人は最初のものがO（n ^ 2）であることに同意すると思います。外側のループはn回実行され、内側のループは外側のループが実行されるたびにn回実行されます。したがって、実行時間はO（n * n）、O（n ^ 2）です。

2番目はO（n ^ 2）です。これは、外側のループがn回実行されるためです。内側のループはn-1回実行されます。このアルゴリズムの平均では、内側のループは外側のループごとにn/2回実行されます。したがって、このアルゴリズムの実行時間はO（n * n / 2）=> O（1/2 * n ^ 2）=> O（n ^ 2）です。

于 2009-07-01T00:03:20.607 に答える
2

Big-O表記は、入力のサイズが変更されたときのアルゴリズムの速度を除いて、アルゴリズムの速度については何も示していません。

アルゴリズムはO（1）である可能性がありますが、100万年かかります。別のアルゴリズムはO（n ^ 2）である可能性がありますが、nが小さい場合はO（n）アルゴリズムよりも高速です。

この質問に対する回答のいくつかは、big-O表記のこの側面に役立つ可能性があります。この質問への回答も役立つ場合があります。

于 2009-06-30T23:52:08.833 に答える
1

プログラム出力を「順列」と呼ぶ問題を無視します。

Big-O-Notationは定数係数を省略します。そして2は一定の係数です。

したがって、元のプログラムの2倍の速度で同じO（）を持つプログラムに問題はありません。

于 2009-07-01T00:01:02.403 に答える
1

あなたは正しいです。2つのアルゴリズムは、一方が一定の時間（「AはBより5分長い」）、複数（「AはBより5倍長い」）、または両方（「A」）かかる場合、BigO表記では同等です。すべてのサイズの入力に対して、Bの2倍と30ミリ秒の追加時間がかかります。

これは、基本的に異なるアルゴリズムを使用して同様の種類の問題を実行する例です。まず、元の例によく似た遅いバージョンです。

boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
    for (int j = i; j < arr2.length(); j++) {
        if (arr1[i] == arr2[j]) {
            arraysHaveAMatch = true;
        }
    }
}

これは、元の動作と同じようにO（n ^ 2）の動作をします（0からではなくiインデックスからjインデックスを開始することで発見したのと同じショートカットを使用します）。ここに別のアプローチがあります：

boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
    set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
    if (set.contains(arr2[j])) {
        arraysHaveAMatch = true;
    }
}

さて、これらを実行しようとすると、おそらく最初のバージョンがより高速に実行されることがわかります。少なくとも長さ10の配列を試してみる場合、2番目のバージョンはHashSetオブジェクトとそのすべての内部データ構造の作成を処理する必要があり、すべての整数のハッシュコードを計算する必要があるためです。ただし、長さが10,000,000の配列で試してみると、まったく異なるストーリーが見つかります。最初のバージョンでは、約50,000,000,000,000ペアの数（約（N * N）/ 2）を調べる必要があります。2番目のバージョンでは、約20,000,000個の数値（約2 * N）に対してハッシュ関数の計算を実行する必要があります。この場合、あなたは確かに2番目のバージョンが欲しいです!!

Big O計算の背後にある基本的な考え方は、（1）計算がかなり簡単であり（CPUの速度やL2キャッシュの種類などの詳細について心配する必要はありません）、（2）誰が気にするかです。小さな問題...とにかく十分に速いです：あなたを殺すのは大きな問題です！これらは常に当てはまるわけではありませんが（キャッシュの種類が重要な場合もあれば、小さなデータセットでのパフォーマンスが重要な場合もあります）、BigOが役立つほど頻繁にtrueに近い場合があります。

于 2009-07-01T00:08:06.493 に答える
0

Big Oについて考える1つの方法は、実際に不公平な状況でも、さまざまなアルゴリズムがどれだけうまくいくかを検討することです。たとえば、一方が非常に強力なスーパーコンピューターで実行され、もう一方が腕時計で実行されている場合です。スーパーコンピューターでより悪いアルゴリズムが実行されている場合でも、腕時計が最初に終了する可能性があるほど大きいNを選択できる場合は、BigOの複雑さが異なります。一方、選択したアルゴリズムやNの大きさに関係なく、スーパーコンピューターが常に勝つことがわかる場合は、定義上、両方のアルゴリズムの複雑さが同じである必要があります。

あなたのアルゴリズムでは、より速いアルゴリズムは最初のアルゴリズムの2倍しか速かった。これは、腕時計がスーパーコンピューターを打ち負かすのに十分な利点ではありません。たとえNが非常に高く、100万、1兆、さらにはグラハム数であったとしても、懐中時計はそのアルゴリズムでスーパーコンピューターを打ち負かすことはできません。彼らがアルゴリズムを交換した場合も同じことが言えます。したがって、Big Oの定義によれば、両方のアルゴリズムの複雑さは同じです。

于 2009-07-01T00:00:08.553 に答える
0

あなたはそれらが両方とも大きいことについて正しいです-Onの二乗、そしてあなたが「今このアルゴリズムは元のアルゴリズムの2倍速い」と言ったときあなたはあなたの質問で真実であることを実際に証明しました。2倍の速さは、定数である1/2を掛けることを意味するため、定義上、これらは同じbig-Oセットに含まれます。

于 2009-07-01T00:05:39.510 に答える
0

O（n）時間で同じことをするアルゴリズムがあったとしましょう。ここで、10000文字の配列を提供したとします。アルゴリズムにはn ^2と（1/2）n ^ 2の時間がかかります。これは、100,000,000と50,000,000です。私のアルゴリズムは10,000かかります。私の方がはるかに速いので、明らかにその1/2の係数は違いを生んでいません。n ^ 2項は、nや1/2のようなより少ない項を支配すると言われ、本質的にそれらを無視できるようにします。

于 2009-07-01T00:06:37.137 に答える
0

big-oh 表記は関数のファミリーを表すので、「これは O(n²) です」と言っても意味はありません。

これは衒学者ではありません。これらのことを理解するための唯一の正しい方法です。

O(f) = { g | すべての x > x_0 に対して、g(x) <= f(x) * c } となるような x_0 と c が存在します。

ここで、最悪の場合、入力のサイズに関してアルゴリズムが実行するステップをカウントしているとします。その関数 f を呼び出します。f \in O(n²) の場合、アルゴリズムの最悪のケースは O(n²) (ただし、O(n³) または O(2^n)) であると言えます。定数の無意味性は、定義から導かれます (c? を参照)。

于 2009-07-01T00:11:50.633 に答える
-1

Big O 表記は「最悪の場合」のシナリオを表すことに注意してください。あなたの例では、最初のアルゴリズムには完全な外側ループ * 完全な内側ループの平均的なケースがあるため、もちろん n^2 です。2 番目のケースには、ほぼ完全な外側ループ * 完全な内側ループであるインスタンスが 1 つあるため、これは最悪のケースであるため、同じ n^2 の山にまとめなければなりません。そこからは良くなるだけで、最初の関数と比較した平均ははるかに低くなります。いずれにせよ、n が大きくなるにつれて、関数の時間は指数関数的に増加します。Big O が実際に伝えているのはそれだけです。指数曲線は大きく異なる可能性がありますが、結局のところ、それらはすべて同じタイプです。

于 2016-05-26T00:50:35.237 に答える