30

Big O 表記のように、「O(1)」は次のコードを表すことができます。

O(1):

    for (int i = 0; i < 10; i++) {
        // do stuff 
        a[i] = INT;
    }

O(n):

    for (int i = 0; i < n; i++) {
        // do stuff 
        a[i] = INT;
    }

O(n^2):
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // do stuff
            a[i][j] = INT;
        }
    }
  • O(log(n)) で記述できるコードは?

別の質問:

  • 「ビッグ オーの問題」に対してどのような解決策がありますか (入力として大量のデータを取得するときに何をすべきか)?
4

7 に答える 7

59

古典的な例:

while (x > 0) {  
   x /= 2;  
}

これは次のようになります：

Iteration |   x
----------+-------
    0     |   x
    1     |  x/2
    2     |  x/4
   ...    |  ...
   ...    |  ...
    k     |  x/2^k

2 k = x → 両辺に log を適用 → k = log(x)

于 2013-06-15T10:52:07.900 に答える
4

定義から、log(n) (ここでは基数 2 の対数を意味しますが、基数は実際には問題ではありません) は、n を取得するために 2 をそれ自体で乗算する必要がある回数です。したがって、O(log(n)) コード例は次のとおりです。

i = 1
while(i < n)
    i = i * 2
    // maybe doing addition O(1) code

実際のコード例では、二分探索、バランスの取れた二分探索ツリー、多くの再帰アルゴリズム、優先キューで O(log(n)) を満たすことができます。

于 2013-06-15T11:32:27.943 に答える
3

O(logn) については、分割統治戦略を含むコードをご覧ください。

于 2013-06-15T10:52:22.107 に答える
1

二分探索は O(log(n)) の例です。http://en.wikipedia.org/wiki/Binary_search_algorithm .

于 2013-06-15T10:53:17.213 に答える
0

二分探索の場合、反復の最大回数を見つけようとしているため、探索空間を半分に分割できる最大回数を見つけようとしています。これは、探索空間のサイズ n を 1 になるまで繰り返し 2 で割ることによって達成されます。

n を 2 で割るのに必要な回数をラベル x に与えましょう。2 で割ると、x 回は 2^x で割ることと同じになるため、次の方程式を解く必要があります。

n/2^x = 1、これは n = 2^x になります。

対数を使うと x = log(n) なので、二分探索の BIG - O は O(log(n))

繰り返しますが、x はサイズ n のスペースをサイズ 1 に縮小する前に半分に分割できる回数です。

http://www.quora.com/How-would-you-explain-O-log-n-in-algorithms-to-1st-year-undergrad-student

于 2015-04-26T06:38:11.277 に答える