大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)) 描述?

另一个问题:

• 在遇到大量数据输入时，有哪些解决方案可以应对 "Big O 问题"？

- Langkiller

---

O(log n)通常用于分治算法，比如二分查找或类似的算法。 - Will

这是一个实际的（编码测试）例子 https://leetcode.com/problems/find-peak-element/ => 查看问题和解决方案 - citynorman

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

---

很棒且简单的例子，正是我所寻找的！谢谢 :) - Langkiller

我错过了你是在什么时候得到2^k = x的，之前它是x/2^k？ - Danylo Gurianov

1 是最后一次迭代。因此，我想知道在哪个点上它会被评估为 1。 - Maroun

有史以来最好的解释。非常感谢。 - Jaumzera

@DanielGurianov，x/2^k的除法最终将得到1。将其等式化将给出1=x/2^k，这相当于x=2^k，应用对数运算后可得log。当b的y次幂等于x时：b^y = x；在这种情况下2^y=x然后，x的底数为b的对数等于y：logb(x) = y；在这种情况下，k = log(x)，意味着以2为底的对数。 - Amos Kosgei

Answer 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(√n)：

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

- costargc

Answer 3

从定义上来看，log(n)（这里指以2为底的对数，但底数实际上并不重要）是你需要将2乘以自身多少次才能得到n。因此，O(log(n)) 的代码示例如下：

i = 1
while(i < n)
    i = i * 2
    // maybe doing addition O(1) code

在真实的代码示例中，O(log(n)) 可以在二分查找、平衡二叉搜索树、许多递归算法和优先队列中出现。

- pkacprzak

Answer 4

如果您想了解O(logn)，请查看任何涉及分治策略的代码。例如：归并排序和快速排序（在这些情况下，预期运行时间为O(nlogn)）。

- attaboy182

Answer 5

二分查找是一个O(log(n))的例子。http://en.wikipedia.org/wiki/Binary_search_algorithm。

- vishnu viswanath

Answer 6

值得强调的是，您所描述的低复杂度算法是高复杂度算法的子集。换句话说，

for (int i = 0; i < 10; i++) {
    // do stuff 
    a[i] = INT;
}

这个算法的时间复杂度既可以是O(1)，也可以是O(n)，O(n²)，如果你想聪明一点，还可以是O(log(n))。为什么？因为所有常数时间算法都受到某些线性、二次等函数的限制。

对于“大O问题”有哪些解决方案（当输入数据很多时该怎么办）？

这个问题对我来说没有太多意义。“很多数据”是相当任意的。但请记住，Big O并不是时间复杂度的唯一衡量标准；除了测量最坏情况下的时间复杂度外，我们还可以检查最好情况和平均情况，尽管这些可能会更加棘手一些。

- lealand

Answer 7

在二分查找中，您试图找到最大迭代次数，因此搜索空间可以被划分的最大次数。这是通过将搜索空间的大小n重复除以2来实现的，直到达到1为止。

假设您需要将n除以2的次数标记为x。由于连续x次除以2等同于除以2^x，因此您最终需要解决以下方程：

n/2^x = 1，即n = 2^x，

因此使用对数，x = log(n)，因此二分查找的BIG-O表示法为O(log(n))。

再次强调：x是您可以将大小为n的空间分成两半的次数，直到其缩小到大小1。

http://www.quora.com/How-would-you-explain-O-log-n-in-algorithms-to-1st-year-undergrad-student

- bsingh