30

就像大 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 问题”（当获取大量数据作为输入时该怎么做）有哪些解决方案？
4

7 回答 7

59

经典例子：

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)

于 2013-06-15T10:52:07.900 回答
6

带有 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
}

在此处输入图像描述

于 2019-10-03T13:33:51.530 回答
4

从定义上看，log(n)（我的意思是以 2 为底的 log，但底数实际上并不重要）是您必须乘以 2 才能得到 n 的次数。因此，O(log(n)) 代码示例是：

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

在实际代码示例中，您可以在二进制搜索、平衡二进制搜索树、许多递归算法、优先级队列中遇到 O(log(n))。

于 2013-06-15T11:32:27.943 回答
3

对于 O(logn)，请查看任何涉及分而治之策略的代码示例：合并排序和快速排序（在这些情况下，预期运行时间为 O(nlogn)）

于 2013-06-15T10:52:22.107 回答
1

二分搜索就是一个例子 O(log(n))。http://en.wikipedia.org/wiki/Binary_search_algorithm。

于 2013-06-15T10:53:17.213 回答
0

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

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

在 O(1) 中，但也在 O(n)、O(n²) 中，如果你想聪明一点，在 O(log(n)) 中。为什么？因为所有恒定时间算法都受一些线性、二次等函数的限制。

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

这个问题对我来说没有多大意义。“大量数据”是相当随意的。不过，请记住，大 O 并不是时间复杂度的唯一衡量标准。除了测量最坏情况的时间复杂度外，我们还可以检查最佳情况和平均情况，尽管计算起来可能有点棘手。

于 2013-06-15T15:19:17.913 回答
0

在二分搜索的情况下，您试图找到最大的迭代次数，因此搜索空间可以分成两半的最大次数。这是通过重复将搜索空间的大小 n 除以 2 直到达到 1 来实现的。

让我们给出标签 x 需要将 n 除以 2 的次数。由于除以 2，x 次等于除以 2^x，因此您最终必须求解以下方程：

n/2^x = 1，变成n = 2^x，

所以使用对数，x = log(n)，所以二进制搜索的 BIG - O 是 O(log(n))

重申一下：x 是在缩小到大小 1 之前，您可以将大小为 n 的空间分成两半的次数。

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

于 2015-04-26T06:38:11.277 回答