Big O - O（log（n））代码示例

algorithm java big-o

2022-09-01 11:22:13

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

另一个问题：

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

答案 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）

答案 2

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

O（1）：

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

O（n）：

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（Log₂（n））：

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

        count++;
    }
    return count
}

O（Sqrt（n））：

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

Big O - O（log（n）） 代码示例

Big O - O（log（n））代码示例