7

私の分析によると、このアルゴリズムの実行時間はN 2である必要があります。これは、各ループがすべての要素を1回通過するためです。ifステートメントの存在が時間計算量を変えるかどうかわかりませんか？

for(int i=0; i<N; i++){
    for(int j=1; j<N; j++){

        System.out.println("Yayyyy");
        if(i<=j){
            System.out.println("Yayyy not");
        }
    }
}
4

6 に答える 6

8
  • Tp：一定のテキストを標準出力に印刷するのにかかる時間。
  • Ti：内部ループ内の他のすべての操作（述語評価など）にかかる時間。
  • To：内部ループの実行（カウンターの初期化など）を除く、外部ループ内のすべての操作にかかる時間。
  • Tc：プロセスの設定と他のすべての簿記にかかる時間

合計実行時間はTc+N x（To + NxTi + N / 2xTp）になります。

これは、Tc + NxTo +（Nx（N / 2））x（2Ti + Tp）に等しく、Nが無限大になるとK> Ti + Tp /2の値に対してKx （N ^ 2）によって制限されます。この境界により、時間計算量は依然としてO（N ^ 2）になります。

いいえ、ifステートメントはこの例の時間計算量を変更しません。

于 2012-09-01T21:46:21.110 に答える
3

いいえ。時間計算量は時間を漸近的に表すことを考慮してください。時間計算量が低いほど高いものに吸収されます。

O(n²)k × n² + cそれが非常に低いと想定されてcいるため、私たちがそれを気にしないことを意味します。

これらは、一定の効果、全体に対する一定量のオーバーヘッド（c）、および複雑さが何であれ、一定量のコストです。あるn²アルゴリズムが他のn²アルゴリズムよりも低いk場合、またはそれらが等しい場合は、より低いアルゴリズムを打ち負かしますc。また、O（n²）は、nの値が十分に低い場合はO（1）と同じです（通常は気にしませんが、kそれぞれの値が大きく異なる可能性があります。また、各m回実行すると、O（ n²m）はO（m）を上回りますが、nが低い場合、実際に比較されるものではありません）。

とにかく、これは意図的な過度の単純化です。なぜならk、c実際には一定ではなく、一定と同じくらい良いからです。したがって、何かが本当にあった場合O(n² + log(n))、私たちはそれを呼ぶでしょうO(n²)、なぜなら私たちが心配しlog(n)ているときに誰がその小さなことを気にしないのn²ですか？

それで。あなたのケースを見てください。外側のループをn何度も実行します。それらのそれぞれについて、内部ループn-1時間を実行します。これらの内部ループのそれぞれについて、最初の印刷（コストの変動はまったく関係がないnため、本質的に一定）とテストを実行します。テストは約半分の時間で成功するため、2回目の印刷のコストが頻繁に発生します。

したがって、総コストは次のようになります。

cost of setting up everything +
n × cost of looping + 
(n - 1) × cost of loop +
(n × (n - 1)) × cost of print +
(n × (n - 1)) × cost of test +
(n × (n - 1)) / 2 × cost of print.

上記の定数に値を割り当てると、次のようになります。

k +
n × a +
(n - 1) × b +
(n × (n - 1)) × c +
(n × (n - 1)) × d +
(n × (n - 1)) / 2 × e.

=

k +
n × a +
(n - 1) × b +
(n × (n - 1)) × (c + d + (e / 2))

さて、c + d + e / 2はそれ自体が一定なので、次のようになります。

n × a + (n - 1) × b + (n × (n - 1)) × c + k

または、最初に上位順に並べ替えるには、次のようにします。

(n × (n - 1)) × c + (n - 1) × b + n × a + k

nが十分に高い場合、nはn-1に比例して非常に近いため、同じと見なすことができます（時間計算量の別の側面では、nが∞に近づくため、 n²と（n×（n-1））の差は0）に近づきます。したがって：

n² × c + n × b + n × a = n² × c + n × (b + a) + k

繰り返しますが、b + aはそれ自体が定数であるため、次のようになります。

n² × k + n × c + a

そして今、私たちは、気にかけている、より低い時間の注文を吸収することについて前述したことをします、気n × cにしないでください？nが私たちがまったく気にするのに十分高い場合、それはすべて約n²です。比較すると、全体的なオーバーヘッドとの違いをノイズと見なし、次のように扱うことができます。

n² × k + c

または、言い換えると、次のようになります。

O(n²)

そうです、そもそもあなたはそれを強打していました、そしてifステートメントは複雑さに影響を与えません。

これを考慮すると、時間の複雑さが私たちが本当に気にかけていることを隠す可能性があることに注意することができます。たとえば、O（n²）アルゴリズムがあり、この種の分析で、時間コストn² × k + n × ckが200µs、cが15sであることがわかった場合、nが750000を超えるまで、実際にはnビットあたりのコストになります。 n²ごとのビットではなく。nが低いほど、O（n²）よりもO（n）に期待する値に近くなります。

時間計算量が有用である理由は、非常に大きな視差がまれであり、時間、したがって時間計算量について、nが高くなるとより多くなることの組み合わせです（恐ろしいO（n！）の怪物を隠すことができます）あなたが青い月に一度呼び出すあなたのコードでは、3つの要素があり、気にしないでください）。したがって、実際の改善をもたらすには、理想的には時間計算量を減らすか、失敗すると最高レベルの定数kが減ります（つまり、n²回ではなくn log n回実行できる場合は、それ以外の場合は実行します）。他のことをn回行うのではなく、n²回行うことのコストを削減します）。

言い換えれば、それは私たちが通常マットなものに集中するのに役立ちます。

于 2012-09-01T22:25:20.977 に答える
0

いいえ、ifは複雑さに影響しません。

于 2012-09-01T21:22:05.010 に答える
0

時間計算量は同じで、Yayyyy N^2回印刷します。

于 2012-09-01T21:22:13.730 に答える
0

簡単な答え：ランタイムはまだO（N ^ 2）です。

長い答え：条件付きチェックのコストは、println（）を1つ実行する代わりに、println（）を2つ使用する場合と同じように、println操作の重みに安全に「追加」できます。（例に関しては、printlnのようなI / O操作のコストが単純な整数の比較を大幅に上回っていることを覚えておいてください。）

おそらく、println（）呼び出しのコストは「1操作」であり、比較は「0.0001操作」であるため、合計コストはN ^ 2ではなく「（1.0001 * N）^2操作」になります。また、println（）の数を半分に減らしたので、（1.0001 * N）^ 2/2の操作であると言えます。これは、与えられた値の場合でも、O（N ^ 2）のままです。 Nエントリの半分だけを出力することで、実行時間を半分にした可能性があります。

一般に、比較のコストは、その比較の結果として生じるブランチ内の操作のコストに追加する必要があります。if（）{}とelse {}の両方が存在する場合、ランタイムの測定がより困難になる可能性があります。ここでの戦術は、最もコストのかかる操作が毎回発生するかのように実行時間を見積もることです。または、単一のブランチの実行時間が容易にわからない場合は、ループの反復ごとに両方の操作が発生するかのように見積もります。これらの操作が両方ともO（1）の場合、線形にスケーリングしているため、ランタイムの順序はO（N ^ 2）のままです。

于 2012-09-01T21:46:56.960 に答える
-1

もちろん、比較ベースのアルゴリズムを使用している場合、それは正しいと思いますか？

したがって、あなたの場合、ifステートメントがほぼn 2回実行されているため、O（n 2 ）を見ています。

非比較アルゴリズムの場合、主な操作は何でも数えます。

于 2012-09-01T21:22:04.727 に答える