1

いくつか質問がありますので、ご容赦ください。BigOと実行時間を明確にするためにいくつかの助けが必要です。私が理解しているように、Big Oはアルゴリズムの実行時間を正しく表示する方法ですか？読んでから、私はアルゴリズムのビッグOを計算する方法を理解しようとしてきました。これまでのところ、このようなものはO（N ^ 2）の大きなOを持っていることがわかりました

for(i = 0; i < N, i++)
    for(j = 0; j < N; j++)
      //code

しかし、これである場合はどうなりますか？

for(i = 0; i < N, i++)
    for(j = 0; j < M; j++)
      //code

ここで、Nは常にMと等しくはありません。

また、これらの2つを足し合わせた場合、Big Oとは何ですか？

for(i = 0; i < N, i++)
    for(j = 0; j < N; j++)
      //code
for(i = 0; i < N, i++)
    for(j = 0; j < N; j++)
      //code

大きなOはN^2 + N ^ 2 = 2N ^ 2に等しいですか？

4

4 に答える 4

4

ここで、Nは常にMと等しくはありません。

に依存している場合、またはその逆O(NM)でない限り、それはです。それらが独立している場合、それはとであると言うことも真実です。MNO(N)O(M)

大きなOはN^2 + N ^ 2 = 2N ^ 2に等しいですか？

O(2N^2)と同等O(N^2)です。

于 2012-05-28T19:42:30.083 に答える
1

基本的にあなたは正しいです。2番目の場合はO（N * M）になります。3つ目についても正しいですが、O（N ^ 2 + N ^ 2）= O（2 * N ^ 2）= O（N ^ 2）から減らすことができます。

アルゴリズムの実行時間を概算するために、ビッグオー表記が使用されます。したがって、この場合、2の乗算係数は電力係数ほど大きくないので、それを取り除きます。

于 2012-05-28T19:44:50.403 に答える
0

2番目の例はO（N * M）です。定数係数（2）はBigOを変更しないため、3番目はまだO（N ^ 2）です。重要なのは、Nを2倍にすると、時間は4倍になります。Nを3倍にすると、時間は9倍になります。

于 2012-05-28T19:43:46.840 に答える
0

最初の 2 つのケースでは、この場合 Big-O は 2 つの変数の単なる関数であることに注意してください。私があなたに言ったら、f(x,y) = x + sin yあなたは f(x) = と言うでしょうf(x) + sin xか? いいえ、それはナンセンスです。

本当にそうですO(N*M)。M が固定定数である状況にあり、N に関してプログラムがどのように実行されるかに関心がある場合、それは N または で線形O(N)です。しかし、N=M を知っている状況にある場合があります。たとえば、正方形を扱っているとします。この場合、関数は と言えますO(N^2)。M=kしかし、一定の k や のような制約がなければM=N、正確に言えるのは だけですO(N*M)。それが 2 次式であると言われたら、リバース エンジニアリングを行って N=M か何かを期待します。

それをもっと理論的に理解したい場合は、作業している変数を指定するまで、言うことO(something)は常にナンセンス であることに注意してください。 f(N,M) = NMO(N) w.r.t. NO(NM) w.r.t N,MO(N^2) w.r.t N where M=N

もっと数学を学びたいなら...それはwikipediaかmath.stackexchange.comです:)

于 2012-05-28T19:46:58.127 に答える