大 O - O(log(n)) 代码示例

Question

就像大 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)) 可以描述什么代码？

另一个问题：

• “大 O 问题”有哪些解决方案（当获取大量数据作为输入时该怎么办）？

原文由 Langkiller 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

经典例子：

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

这将是：

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

2 k = x → 对两边应用对数 → k = log(x)

原文由 Maroun 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

带有用于表示的 for 循环的最简单代码：

O（1）：

 function O_1(i) {
    // console.log(i);
    return 1
}

上）：

 function O_N(n) {
    count = 0;
    for (i = 0; i < n; i++) {
        // console.log(i);
        count++;
    }
    return count
}

O(n²):

 function O_N2(n) {
    count = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            // console.log(i, j);
            count++;
        }
    }
    return count
}

O(日志2 (n)):

 function O_LOG_2(n) {
    count = 0;
    for (var i = 1; i < n; i = i * 2) {

        count++;
    }
    return count
}

O（平方（n））：

 function O_SQRT(n) {
    count = 0;
    for (var i = 1; i * i < n; i++) {
        // console.log(i);
        count++;
    }
    return count
}

原文由 costargc 发布，翻译遵循 CC BY-SA 4.0 许可协议