[解決済み] Big O - O(log(n))のコード例

質問

ビッグ・オー表記(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))が記述できるコードとは？

もう一つ質問です。

• Big O問題(大量のデータを入力する場合の対処法)について、どのような解決策がありますか？

解決方法は？

古典的な例です。

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)