6

このメソッドは、 の配列内の少なくとも 2 つの値が である場合にhasTwoTrueValues戻ります。提案された 3 つの実装すべてについて、Big-O の実行時間を提供します。truebooleantrue

//バージョン 1

public boolean hasTwoTrueValues(boolean[] arr) {
    int count = 0;
    for(int i = 0; i < arr.length; i++)
        if(arr[i])
            count++;
        return count >= 2;
}

//バージョン 2

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < arr.length; i++)
        for(int j = i + 1; j < arr.length; j++ )
            if(arr[i] && arr[j])
                return true;
}

//バージョン 3

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < arr.length; i++)
        if(arr[i])
            for(int j = i + 1; j < arr.length; j++)
                if(arr[j])
                    return true;
                        return false;
}

これらは私の答えです：

  • バージョン1はO(n)
  • バージョン2はO(n^2)
  • バージョン3はO(n^2)

私はこの Big-O 記法に本当に慣れていないので、答えが正しいか間違っているかについてのガイダンスが必要です。もし私が間違っていたら、説明して、私が学ぶのを手伝ってくれませんか?

4

2 に答える 2

4

バージョン 1 は非常に単純で線形に実行されるため、その実行時間は平均で O(n) です。

バージョン 2 はもう少し興味深いものです。平均n(n-1) で実行されます。これは O(n 2 ) です。このループには早い段階returnがあるため、最初の 2 つの要素で中断する可能性は間違いありません。

バージョン 3 はよりトリッキーです。これには注意が必要です。arr[i]2 番目のループは、 isの場合にのみ実行されますtrue。その場合、実行時間は個別のカテゴリに分類する必要があります。

  • 配列のすべての要素が false の場合、ランタイムは O(n) になります。
  • 配列の要素の半分が true の場合、(n(n-1))/2、つまり O(n 2 ) の条件で 2 番目のループを実行します。
  • 配列のすべての要素が true の場合、O(n 2 )で実行されます。また、最初の 2 つの要素の後ですぐに終了しますが、まだ 2 つのループを使用してアクションを実行しています。

したがって、バージョン 3 の平均および最悪の実行時間は O(n 2 )であると言っても過言ではありません。その最善の方法は O(n) であり、これは間違いなく可能です。

于 2012-10-01T03:52:49.180 に答える
0

つまり、最悪の場合の実行時間は次のとおりです。 バージョン 1:O(n)
バージョン 2:O(n^2)
バージョン 3:O(n)

詳しい分析は・・・

このアルゴリズムでは、意味のある比較を行うために、最良のケース、最悪のケース、および平均的なケースのランタイムを考慮する必要があります。

それらのそれぞれについて、以下はこれらを例示する必要があります。

bestCase = [ true, true, ...] // the first two are true
worstCase = [ false, false, ..., false] // all are false
averageCase = [ true, ..., true, ..., false // second true value is found about half-way

すべてのアルゴリズムについて、最良の実行時間はO(2)であり、一定時間を意味します。

最悪の場合、最初のアルゴリズムはO(n)、線形ランタイムを意味します。ただし、最悪の場合、各ステップでチェックする要素が 1 つ少なくなるため、2 番目のアルゴリズムは非常に具体的に劣化します。これは、あなたが正しく言ったように、にn + (n-1) + (n-2) + ...評価され、二次的に成長します。n(n-1)/2O(n^2)

すべてが false である「最悪のケース」では (後でわかるように、これは実際にはバージョン 3の最悪のケースではありません)、3 番目のアルゴリズムは実際には線形時間で実行されます。これは、ifステートメントが 2 番目のループの実行を妨げるためです。 .

判明したように、バージョン 3は二次時間で実行されることはありません: 最初の を線形にスキャンし、それを見つけた後にのみtrue残りを線形にスキャンするため、平均と最悪の場合は線形になりますが、そうではありません。trueうまくいかない！内側の for ループには 2 つの戻り値があるため、最初の値が検出されると、次の直近のtrue値が である場合に戻ります。ただし、次の隣接がである場合は、すぐに返され、他の値はチェックされません。これは、入力で次のことを意味します。truetruefalsefalse

[ true, false, true ]

バージョン 3は、2 番目の false 値を確認するとすぐに false を返します。return false(技術的には、これを for ループ内で実行することを想定しています。その場合、 も追加する必要があり{ }、最初のバージョンでも同様です。常に必要というわけではありませんが、正確に何が起こっているのかを明確にするのに役立ちます。これは現在のインデントと一致しません. 存在しない場合は、直後のステートメントのみがループ/if 本体に含まれます.) 正しく実装されていても、*バージョン 3は線形である最悪のケースの実行時間を持つと思われます. 、入力時:

[true, false, false, ..., false]

最初の true は内側のループで時間をスキャンnしますが、外側のループは内側のループを再度実行せずに n まで実行し続けるため、合計で 2n-1 の操作が行われます。これはもちろんO(n).

あなた{ }が正しく、それが単にあなたのインデントが間違っている場合、これらの分析を少し変更する必要があるかもしれませんが、これはビッグオーの問題 (および一般的な漸近分析) に適用する必要がある種類の考え方です。

于 2012-10-01T04:23:27.890 に答える