logo标签列表

O(n)和O(log(n))的区别是什么 - 哪个更好，O(log(n))到底是什么？

algorithmdata-structurescomplexity-theorybig-ologarithm
89

这是我学习数据结构的第一门课程，每节课/助教讲座中我们都会谈到O(log(n))。也许这是一个愚蠢的问题，但我很希望有人能够解释一下它到底是什么意思！

4
可能会重复 https://dev59.com/-HRB5IYBdhLWcg3w3K0J#487278 的内容。 - bisarch
7个回答
121

这意味着所讨论的事物（通常是运行时间）按照其输入规模的对数比例进行缩放。

大O符号并不表示一个精确的等式，而是一个上限。例如，以下函数的输出都是O(n)：

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

因为随着x的增加，它们的输出线性增加 - 如果f(n)和g(n)之间存在6:1的比率，则f(10*n)和g(10*n)之间也将大致存在6:1的比率，以此类推。

至于O(n)或O(log n)哪个更好，考虑一下：如果n = 1000，那么log n = 3（以10为底的对数）。你希望你的算法需要多长时间才能运行：1000秒还是3秒？

37
讲得非常清楚。另外，我想为那些不知道什么是对数的人添加一些信息。在计算机科学中，log n 表示使数字 2 的幂等于 n 所需的指数。因此，想象一下，如果 n = 16，我们所需的指数将比实际的 n 值小得多得多。它将为 4。希望这有意义。在上面Amber的例子中，她给出了一个类似的例子，但是将10的3次方作为底数。 - Horse Voice
1
+1 - 用最少的话语清晰地解释。谢谢。 - techfoobar
1
值得注意的是，Big-O通常指任何限制，而不一定是最紧密的限制（即最小的g(x)，使得f(x)=O(g(x))）。f(x)、g(x)和m(x)也都是O(n^2)。但在性能分析的上下文中，我们希望得到最紧密的限制（即限制给定算法性能曲线的最小函数），以便给出算法性能的“最坏情况”想法。 - Minh Tran
@Horse Voice 在你的例子中，你使用了2 ** 4，而在Amber的代码中，例子是10 ** 3；如何确定参数？ - MadHatter
这个链接展示了一个包含所有不同复杂度的图表：https://www.bigocheatsheet.com/ - silver_mx
不反驳这个答案，因为它回答得非常好。然而，在这种情况下应该定义“更好”。确实，“更快”，但不是在所有情况下。假设你有一个时间复杂度是N/100，另一个是(log N)*100，对于较小的输入大小，后者会更慢。但当然，总会有一个点，O(log n)比O(n)更快。 - Harlin
52
简短回答是，O(log n)比O(n)更好。
那么什么是O(log n)呢？一般来说，在提到大O符号时，log n指的是以2为底的对数（同样地，ln代表以e为底的对数）。这个以2为底的对数是指数函数的反函数。指数函数增长非常快，我们可以直观地推断它的反函数将会完全相反，即增长非常缓慢。
例如：
x = O(log n)
我们可以表示n为，
n = 2^x
并且
2^10 = 1024 → lg(1024) = 10
2^20 = 1,048,576 → lg(1048576) = 20
2^30 = 1,073,741,824 → lg(1073741824) = 30
n的大幅增加只会导致log(n)的微小增加。
另一方面，对于O(n)的复杂度，我们得到一个线性关系。
任何时候都应该选择log2n的因子而不是n的因子。
为了进一步巩固这一点，我在Thomas Cormen的算法解锁中找到了一个例子。
考虑两台计算机：A和B。
两台计算机都有一个搜索值的数组任务。假设要搜索的数组有1000万个元素。
计算机A-此计算机每秒可以执行10亿条指令，并且预计使用复杂度为O(n)的算法执行上述任务。我们可以近似计算出完成任务所需的时间为
n /（每秒指令数）→ 10 ^ 7 / 10 ^ 9 = 0.01秒
计算机B-该计算机速度慢得多，每秒只能执行1000万条指令。预计计算机B将使用复杂度为O（log n）的算法执行上述任务。我们可以近似计算出完成任务所需的时间为 log（n）/（每秒指令数）→ log（10 ^ 7）/ 10 ^ 7 = 0.000002325349
通过这个例子，我们可以看到，尽管计算机A比计算机B好得多，但由于B使用的算法，它完成任务要快得多。
现在我认为O（log（n））比O（n）更快应该非常清楚了。
23
对于大小为n的输入，一个时间复杂度为O(n)的算法将执行与n成正比的步骤，而另一个时间复杂度为O(log(n))的算法将执行大约log(n)个步骤。
显然，log(n)小于n，因此时间复杂度为O(log(n))的算法更好。因为它会快得多。
8

O(logn) 表示算法的最大运行时间与输入大小的对数成比例。 O(n) 表示算法的最大运行时间与输入大小成比例。

基本上，O(something) 是算法指令数量（原子指令）的上限。因此，O(logn) 比 O(n) 更紧密，也更好地适用于算法分析。但所有 O(logn) 的算法也都是 O(n)，但反过来则不一定成立...

4
"O(n) 比 O(logn) 更紧密，并且在算法分析方面也更好"...显然O(log(n))比O(n) 更好。我想你的意思是相反的。" - LuxuryMode
5
4

正式定义:

若存在常数C和x0，对于每个x>x0, |g(x)|<= C|f(x)|，则g(x) = O(f(x))。

因此，如果你为问题P找到了复杂度为O(f(n))的算法A，那么你可以说，当n通常是输入大小时，你的算法执行步骤的数量渐近地小于或等于f(n)。(n可以是任何值)

更多信息请参考：http://en.wikipedia.org/wiki/Big_O_notation。

0

O(1)总是比O(log n)快吗？

O(1)表示算法的运行时间与输入大小无关，并受到常数'c'的限制。而O(log n)表示当输入大小'n'指数增长时，运行时间将线性增长。

需要注意的是，在某些情况下，O(log n)可能比O(1)快，但当n增长时，O(1)将优于O(log n)，因为O(1)不依赖于输入大小n。考虑这两个代码片段：

Code 1:

function show(){

    for(let i = 2; i <= 5; i++){
      console.log("Hello");
    
      }
  }



Code 2:

function showN(n){

    for(let i = 2; i <= n; i=i*2){
      console.log("Hello");
     }
  }

Code 1的运行时间为O(1)，因为它与输入大小'n'无关，而Code 2的运行时间为O(log n)。

案例：O(log n)优于O(1) 让我们假设show函数执行需要1毫秒。

当n=2时，Code 1将花费4毫秒执行，而Code 2只需1毫秒执行。在这种情况下，O(log n)优于O(1)。

案例：O(1)优于O(log n) 随着输入大小'n'增加，O(1)将优于O(log n)。让我们看一个例子，假设n = 2048，现在Code 1执行仍然需要4毫秒，但Code 2执行需要11毫秒。在这种情况下，O(1)优于O(log n)。

结论： 如上述案例所示，O(1)算法并非总是比O(log n)更快。有时，O(log n)会优于O(1)，但随着输入大小'n'的增加，O(log n)的执行时间会超过O(1)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接