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

Lan*_*ler 18 java algorithm big-o

像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;
        }
    }
Run Code Online (Sandbox Code Playgroud)
  • O(log(n))可以描述什么代码?

另一个问题:

  • "大O问题"有什么解决方案(当把大量数据作为输入时该怎么做)?

Mar*_*oun 41

经典例子:

while (x > 0) {  
   x /= 2;  
}  
Run Code Online (Sandbox Code Playgroud)

这将会:

Iteration |   x
----------+-------
    0     |   x
    1     |  x/2
    2     |  x/4
   ...    |  ...
   ...    |  ...
    k     |  x/2^k 
Run Code Online (Sandbox Code Playgroud)

2 k = x→将日志应用于双方→k = log(x)

  • 伟大而简单的例子,正是我所寻找的!你好:) (2认同)
  • 我错过了在哪一刻得到2 ^ k = x的信息,而以前是x / 2 ^ k吗? (2认同)

小智 7

带有 for 循环的最简单代码,您可以用它来表示:

\n

O(1):

\n
function O_1(i) {\n    // console.log(i);\n    return 1\n}\n
Run Code Online (Sandbox Code Playgroud)\n

在):

\n
function O_N(n) {\n    count = 0;\n    for (i = 0; i < n; i++) {\n        // console.log(i);\n        count++;\n    }\n    return count\n}\n
Run Code Online (Sandbox Code Playgroud)\n

O(n\xc2\xb2):

\n
function O_N2(n) {\n    count = 0;\n    for (i = 0; i < n; i++) {\n        for (j = 0; j < n; j++) {\n            // console.log(i, j);\n            count++;\n        }\n    }\n    return count\n}\n
Run Code Online (Sandbox Code Playgroud)\n

O(Log 2 (n)):

\n
function O_LOG_2(n) {\n    count = 0;\n    for (var i = 1; i < n; i = i * 2) {\n\n        count++;\n    }\n    return count\n}\n
Run Code Online (Sandbox Code Playgroud)\n

O(平方(n)):

\n
function O_SQRT(n) {\n    count = 0;\n    for (var i = 1; i * i < n; i++) {\n        // console.log(i);\n        count++;\n    }\n    return count\n}\n
Run Code Online (Sandbox Code Playgroud)\n

在此输入图像描述

\n