function - 特定の関数の複雑さ

Question

以下のコードセグメントの複雑さを分析したところ、 O(n/2)であることがわかりました。しかし、インターネットを検索しているときに、おそらくO(n)であることがわかりました。誰が正しいのか知りたいです。

void function(int n) {
    int i = 1, k = 100;
    while (i < n) {
        k++;
        i += 2;
    }
}

score 7 · Accepted Answer

上記の方法における変数 k のポイントは何ですか? とにかく、big-O 表記は極限での動作について話します (n の値が無限大に近づくにつれて)。そのため、big-O 表記は、スケーリング係数と定数の両方に依存しません。つまり、任意の定数 "c" と倍率 "s" に対して、

O(f(n)) は O(s*f(n) + c) と同等です

あなたの場合、f（n）= n、s = 1/2、およびc = 0です。だから...

O(n) = O(n/2)

score 6 · Accepted Answer

O(n) は O(n/2) と同じです

big-O 表記の考え方は、より大きな入力を与えたときにアルゴリズムがどれだけ速く実行されるかを理解することです。たとえば、入力のサイズを 2 倍にすると、プログラムの所要時間は 2 倍になるか、4 倍になります。

n と n/2 は、N の値を変更しても同じように動作するため (つまり、N を 10 倍にすると、N 自体と N/2 の両方が同じようにスケーリングされます)。

score 4 · Accepted Answer

O(n/2) = O(0.5n) = O(n) . これについて詳しくは、ウィキペディアを参照してください。

fがO(g)の場合、すべてのx > nに対して|f(x)|となるcとnが存在します。<= c * |g(x)| . つまり、入力n以降では、c * g(x)がf(x )を支配します。

O(n/2) = O(n)となります。

これを証明するために使用できるcとnの値は無数にあることに注意してください。(上記では最小化しましたが、それは必須ではありません。)

3 に答える 3