6 
int num = n/4;
for (int i = 1; i <= num; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++) {
            int count = 1;
        }
    }
}

私が読んだ本によると、このコードはO（（n ^ 3）/ 4）であるはずです。しかし、明らかにそうではありません。ネストされたループのBig-Oを見つけるために、境界を乗算することになっていますか？したがって、これはnum * n*nまたはn/4 * n*nである必要があります。

4

4 に答える 4

15

O((n^3)/4)引数の比率として複雑さを測定することを目的としているため、big-O表記では意味がありません。4で割っても、比率の値は変わりますが、その性質は変わらないため、効果はありません。

これらはすべて同等です。

O(n^3)
O(n^3/4)
O(n^3*1e6)

他の用語は、n次のような用語が含まれている場合にのみ意味があります。

O(n^3 / log(n))
O(n^3 * 10^n)

アンソニー・カナゴが正しく指摘しているように、それは次のような慣習です。

  • 合計の成長率が最も高い項のみを保持しますO(n^2+n) = O(n^2)。
  • 製品の定数を削除しますO(n^2/4) = O(n^2)。

余談ですが、私はすべての場合にその最初のルールに常に同意するわけではありません。関数の最大成長率を決定するための良いルールですが、入力パラメーターにインテリジェントに制限を設定できるアルゴリズム比較（a）O(n^4+n^3+n^2+n)のようなものでは、のようなものは単なる。よりも著しく悪いですO(n^4)。

その場合、入力パラメータに依存する用語を含める必要があります。実際、定数項でさえそこで役立つかもしれません。たとえばO(n+1e100)、と比較してください。後者は、一定の期間に影響を与えるのに十分な大きさになるO(n^2)まで、かなり長い間前者を上回ります。n

（a）もちろん、そのような方法で使用すべきではないと言う人もいますが、現実世界では実用主義が独断主義を克服することがよくあります:-)

于 2009-04-20T04:57:07.553 に答える
1

http://en.wikipedia.org/wiki/Big_O_notationから、1/4のような定数がBig-O表記を決定する役割を果たしていないことがわかります。唯一の興味深い事実は、それがn ^ 3、つまりO（N ^ 3）であるということです。

于 2009-04-20T05:02:54.623 に答える
0

正式には、時間計算量は次のように推定できます。

ここに画像の説明を入力

于 2014-03-17T21:54:07.180 に答える
-1

小さな技術。Big O表記は、数値ではなく、入力の「サイズ」の観点から複雑さを説明することを目的としています。入力が数値の場合、入力のサイズは数値の桁数です。残念ながら、アルゴリズムはO（2 ^ N ^ 3）で、Nは桁数です。

このトピックの詳細

于 2009-04-20T05:41:29.443 に答える