一尘不染

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

algorithm

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

另一个问题:

  • 对于“大O问题”有什么解决方案(当获取大量数据作为输入时该怎么办)?

阅读 251

收藏
2020-07-28

共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)

2020-07-28