O（log n）究竟意味着什么？-Java 学习之路

1805

我目前正在学习Big O Notation运行时间和摊销时间 . 我理解O（n）线性时间的概念，意味着输入的大小成比例地影响算法的增长...例如，二次时间O（n2）等也是如此 . 即使是算法，例如置换生成器，具有O（n！）倍，通过阶乘生长 .

例如，以下函数是O（n），因为算法与其输入n成比例增长：

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

类似地，如果存在嵌套循环，则时间将为O（n2） .

但究竟什么是O（log n）？例如，说完整二叉树的高度是O（log n）是什么意思？

我知道（也许不是非常详细）什么是对数，在某种意义上：log10 100 = 2，但我无法理解如何识别具有对数时间的函数 .

30 回答

4

您可以通过说时间与N中的位数成比例来直观地考虑O（log N） .

如果操作对输入的每个数字或位执行恒定时间工作，则整个操作将花费与输入中的位数或位数成比例的时间，而不是输入的大小;因此，O（log N）而不是O（N） .

如果一个操作做出一系列恒定时间决定，其中每一个都要减半（减少3,4,5 ......），要考虑的输入大小，整体将花费时间与log base 2（base 3）成比例，输入的大小N的基数4，基数5 ...），而不是O（N） .

等等 .

回复于 2024-04-26T16:56:47+08:00
8
我无法理解如何识别具有日志时间的函数 .

对数运行时函数最常见的属性是：
- 选择要执行某些操作的下一个元素是几种可能性之一，并且
- 只需要选择一个 .
要么
- 执行动作的元素是n的数字
这就是为什么，例如，在电话簿中查找人是O（log n） . 您无需检查电话簿中的每个人以找到合适的人;相反，您可以通过基于字母顺序查看其名称来简单地分而治之，并且在您最终找到某人的电话号码之前，您只需在每个部分中探索每个部分的子集 .

当然，更大的电话簿仍然会花费更长的时间，但它不会像额外的大小成比例增长那么快 .

我们可以扩展电话簿示例来比较其他类型的操作及其运行时间 . 我们将假设我们的电话簿有业务（"Yellow Pages"），它们具有唯一的名称和人员（"White Pages"），可能没有唯一的名称 . 电话号码最多分配给一个人或企业 . 我们还假设需要一段时间才能翻转到特定页面 .

以下是我们可能在电话簿上执行的一些操作的运行时间，从最佳到最差：
- O(1) (best case): 给定企业名称所在的页面和企业名称，找到电话号码 .
- O(1) (average case): 给定一个人姓名所在的页面及其姓名，找到电话号码 .
- O(log n): 鉴于尚未搜索到某人's name, find the phone number by picking a random point about halfway through the part of the book you haven'，然后检查该人姓名是否存在 . （这是对某个人姓名的二进制搜索 . ）
- O(n): 查找电话号码包含数字"5"的所有人 .
- O(n): 给定一个电话号码，找到具有该号码的个人或企业 .
- O(n log n): 通过查看每页上的第一个名称然后将该页面放在新的空白电话簿中的适当位置，打印机's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it'上的混音是正确的 .
对于以下示例，我们现在在打印机的办公室 . 电话簿等待邮寄给每个居民或企业，每个电话簿上都有一个标签，标明应该邮寄到哪里 . 每个人或企业都有一本电话簿 .
- O(n log n): 我们想要个性化电话簿，所以我们在他们的指定副本中输入名称，然后在书中圈出他们的名字，并为他们的赞助写一个简短的感谢信 .
- O(n2): 办公室发生错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的"0" . 取一些白色并删除每个零 .
- O(n · n!): 我们're ready to load the phonebooks onto the shipping dock. Unfortunately, the robot that was supposed to load the books has gone haywire: it'将书籍随机地放到卡车上！更糟糕的是，它将所有书籍加载到卡车上，然后检查它们是否按正确顺序排列，如果没有，则将其卸载并重新开始 . （这是可怕的 bogo sort . ）
- O(nn): 您修复了机器人，以便_584641的错误检测系统足够复杂，机器人不会被打印出来 .
有关更多数学解释，您可以在此处查看时间复杂度如何到达 log n . https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf
回复于 2024-04-26T16:56:47+08:00
4

这个问题已经发布了许多好的答案，但我相信我们真的错过了一个重要的答案 - 即图解答案 .

说完整二叉树的高度是O（log n）是什么意思？

下图描绘了二叉树 . 注意每个级别如何包含与上面的级别相比的节点数量的两倍（因此是二进制）：

二进制搜索是复杂度为 O(log n) 的示例 . 假设图1中树底层中的节点表示某些已排序集合中的项目 . 二进制搜索是一种分而治之的算法，该图显示了我们将如何（最多）需要4次比较来查找我们在此16项数据集中搜索的记录 .

假设我们有一个包含32个元素的数据集 . 继续在上面绘制，发现我们现在需要进行5次比较才能找到我们正在搜索的内容，因为当我们乘以数据量时，树只增长了一层 . 结果，算法的复杂性可以描述为对数阶 .

在一张普通纸上绘制 log(n) 将产生一个图形，其中曲线的上升随着 n 的增加而减速：

回复于 2024-04-26T16:56:47+08:00
54

O(log N) 基本上意味着时间呈线性上升而 n 呈指数上升 . 因此，如果计算 10 元素需要_584652秒，则计算 100 元素需要_584654秒，计算 1000 元素需要 3 秒，依此类推 .

当我们划分和征服算法类型（例如二进制搜索）时，它是 O(log n) . 另一个例子是快速排序，每次我们将数组分成两部分，每次需要 O(N) 时间来找到一个数据元素 . 因此它 N O(log N)

回复于 2024-04-26T16:56:47+08:00
128

下面的解释是使用完全 balancer 的二叉树的情况来帮助您了解我们如何获得对数时间复杂度 .

二叉树是这样一种情况，其中大小为n的问题被分成大小为n / 2的子问题，直到我们遇到大小为1的问题：

这就是你得到O（log n）的方式，这是在上面的树上需要完成的工作量才能达到解决方案 .

具有O（log n）时间复杂度的通用算法是二进制搜索，其递归关系是T（n / 2）O（1），即在树的每个后续级别，您将问题分成一半并且进行恒定量的额外工作 .

回复于 2024-04-26T16:56:47+08:00
35
Overview

其他人给出了很好的图表示例，例如树形图 . 我没有看到任何简单的代码示例 . 因此，除了我的解释之外，我还将提供一些带有简单打印语句的算法来说明不同算法类别的复杂性 .

首先，您需要了解Logarithm的一般概念，您可以从https://en.wikipedia.org/wiki/Logarithm获得 . 自然科学使用 e 和自然日志 . 工程学徒将使用log_10（log base 10），计算机科学家将使用log_2（log base 2），因为计算机是基于二进制的 . 有时您会看到自然日志的缩写为 ln() ，工程师通常会关闭_10并使用 log() 而log_2缩写为 lg() . 所有类型的对数都以类似的方式增长，这就是为什么它们共享相同类别的 log(n) .

当你看下面的代码示例时，我建议看O（1），然后是O（n），然后是O（n ^ 2） . 在你善待这些之后，再看看其他人 . 我已经包含了干净的示例和变体，以演示微妙的更改如何仍然可以导致相同的分类 .

您可以将O（1），O（n），O（logn）等视为增长的类别或类别 . 某些类别比其他类别需要更多时间 . 这些类别有助于我们为算法性能排序 . 随着输入n的增长，一些增长得更快 . 下表以数字方式说明了所述增长情况 . 在下表中，将log（n）视为log_2的上限 .

Simple Code Examples Of Various Big O Categories:

O(1) - Constant Time Examples:
- Algorithm 1:
算法1打印hello一次并且它不依赖于n，因此它将始终以恒定时间运行，因此它是 O(1) .
```
print "hello";
```
- Algorithm 2:
算法2打印hello 3次，但不依赖于输入大小 . 即使n增长，该算法也将始终只打印3次hello . 那说3，是一个常数，所以这个算法也是 O(1) .
```
print "hello";
print "hello";
print "hello";
```
O(log(n)) - Logarithmic Examples:
- Algorithm 3 - This acts like "log_2"
算法3演示了一个在log_2（n）中运行的算法 . 注意for循环的post操作将i的当前值乘以2，所以 i 从1变为2到4到8到16到32 ......
```
for(int i = 1; i <= n; i = i * 2)
  print "hello";
```
- Algorithm 4 - This acts like "log_3"
算法4演示了log_3 . 注意 i 从1到3到9到27 ......
```
for(int i = 1; i <= n; i = i * 3)
  print "hello";
```
- Algorithm 5 - This acts like "log_1.02"
算法5很重要，因为它有助于表明只要数字大于1并且结果重复地与自身相乘，您就会看到对数算法 .
```
for(double i = 1; i < n; i = i * 1.02)
  print "hello";
```
O(n) - Linear Time Examples:
- Algorithm 6
这个算法很简单，打印你好n次 .
```
for(int i = 0; i < n; i++)
  print "hello";
```
- Algorithm 7
此算法显示一个变体，它将打印hello n / 2次 . n / 2 = 1/2 * n . 我们忽略1/2常数并看到该算法是O（n） .
```
for(int i = 0; i < n; i = i + 2)
  print "hello";
```
O(n*log(n)) - nlog(n) Examples:
- Algorithm 8
将此视为 O(log(n)) 和 O(n) 的组合 . for循环的嵌套有助于我们获得 O(n*log(n))
```
for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
```
- Algorithm 9
算法9与算法8类似，但每个循环都允许变化，这仍然导致最终结果为 O(n*log(n))
```
for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";
```
O(n^2) - n squared Examples:
- Algorithm 10
通过嵌套循环标准可以轻松获得 O(n^2) .
```
for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
```
- Algorithm 11
与算法10类似，但有一些变化 .
```
for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";
```
O(n^3) - n cubed Examples:
- Algorithm 12
这类似于算法10，但有3个循环而不是2个循环 .
```
for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
```
- Algorithm 13
像算法一样12，但有一些变化仍然产生 O(n^3) .
```
for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";
```
Summary

上面给出了几个直接的例子和变体，以帮助证明可以引入哪些微妙的变化，实际上不会改变分析 . 希望它能给你足够的洞察力 .
回复于 2024-04-26T16:56:47+08:00

如果你有一个功能：

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

然后它需要log2（n）时间 . 松散地说，Big O notation意味着只有大n的关系才需要，并且可以忽略常数因子和较小项 .

回复于 2024-04-26T16:56:47+08:00

9

对数运行时间（ O(log n) ）实质上意味着运行时间与输入大小的对数成比例增长 - 例如，如果10个项目最多花费一些时间 x ，最多100个项目，例如 2x ，并且10,000件物品最多需要 4x ，然后它看起来像 O(log n) 时间复杂度 .

回复于 2024-04-26T16:56:47+08:00
2
The logarithm

好吧，让我们试着完全理解对数实际上是什么 .

想象一下，我们有一根绳子，我们把它绑在一匹马上 . 如果绳子直接绑在马上，那么马需要拉开的力量（例如，从一个人身上拉开）直接是1 .

现在想象一下绳子环绕着一根杆子 . 逃跑的马现在必须更加努力 . 时间量取决于绳索的粗糙度和杆的大小，但我们假设它会将一个人的力量乘以10（当绳子完全转弯时） .

现在，如果绳索一圈，马将需要拉10倍 . 如果人类决定让这匹马变得非常困难，他可能会再次将绳子绕在杆子上，使其强度再增加10倍 . 第三个循环将再次将强度增加10倍 .

我们可以看到，对于每个循环，值增加10.获得任何数字所需的回合数被称为数字的对数，即我们需要3个帖子来倍增你的力量1000倍，6个帖子来增加你的力量1,000,000 .

3是1,000的对数，6是1,000,000（基数10）的对数 .

So what does O(log n) actually mean?

在上面的例子中，我们'growth rate'是 O(log n) . 对于每个额外的循环，我们的绳索可以处理的力是10倍：
```
Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n
```
现在上面的例子确实使用了基数10，但幸运的是，当我们谈论大写符号时，日志的基数是微不足道的 .

现在让我们假设您正在尝试猜测1-100之间的数字 .
```
Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!
```
现在你需要7次猜测才能做到这一点 . 但这里的关系是什么？每增加一次猜测，您可以猜出的项目数量是多少？
```
Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024
```
使用图表，我们可以看到，如果我们使用二进制搜索来猜测1-100之间的数字，那么我们将需要 at most 7次尝试 . 如果我们有128个数字，我们也可以猜测7个尝试中的数字，但129个数字将需要我们 at most 8个尝试（与对数的关系，这里我们需要7个猜测128值范围，10个猜测1024值范围 . 7是对数128，10是1024的对数（基数2）） .

请注意，我“最多”加粗 . 大写符号总是指更糟糕的情况 . 如果你很幸运，你可以在一次尝试中猜出这个数字，所以最好的情况是O（1），但这是另一个故事 .

我们可以看到，每次猜测我们的数据集都在缩小 . 识别算法是否具有对数时间的一个好的经验法则是在每次迭代后查看数据集是否按某个顺序收缩

What about O(n log n)?

您最终会遇到一个线性时间 O(n log(n) 算法 . 上面的经验法则再次适用，但这次对数函数必须运行n次，例如减少列表 n times 的大小，这种算法发生在像mergesort这样的算法中 .

您可以轻松识别算法时间是否为n log n . 寻找一个循环遍历列表的外循环（O（n）） . 然后看看是否有内环 . 如果内部循环是每次迭代的数据集，则该循环为（O（log n），因此整个算法= O(n log n) .

免责声明：绳索对数的例子来自优秀的Mathematician's Delight book by W.Sawyer .
回复于 2024-04-26T16:56:47+08:00
48

我总是必须在心理上可视化在O（log n）中运行的算法的最佳方法如下：

如果您将问题大小增加一个乘法量（即将其大小乘以10），则工作量仅增加添加量 .

将此应用于您的二叉树问题，以便您有一个好的应用程序：如果您将二叉树中的节点数加倍，则高度仅增加1（附加量） . 如果再次加倍，它仍然只增加1.（显然我认为它保持 balancer 等） . 这样，当问题大小成倍增加时，你的工作量不会增加一倍，而是只做更多的工作 . 这就是为什么O（log n）算法很棒的原因 .

回复于 2024-04-26T16:56:47+08:00
2

什么是logb（n）？

它是在到达大小为1的部分之前，可以将长度为n的对数重复切换为b等份的次数 .

回复于 2024-04-26T16:56:47+08:00
489

首先，我建议你阅读以下书籍;

Algorithms (4th Edition)

这是一些功能及其预期的复杂性 . 数字表示 statement execution frequencies .

以下 Big-O Complexity Chart 也取自bigocheatsheet

最后非常简单的展示展示了如何计算;

解剖程序的语句执行频率 .

分析程序的运行时间（示例） .

回复于 2024-04-26T16:56:47+08:00
5

划分和征服算法通常具有运行时间的 logn 组件 . 这来自重复减半的输入 .

在二进制搜索的情况下，每次迭代都会丢弃一半的输入 . 应该注意，在Big-O表示法中，log是log base 2 .

编辑：如上所述，日志库无关紧要，但在导出算法的Big-O性能时，日志因子将来自减半，因此我将其视为基数2 .

回复于 2024-04-26T16:56:47+08:00
88

但究竟什么是O（log n）？例如，说>完整二叉树的高度是O（log n）是什么意思？

我将其改写为“完整二叉树的高度为log n” . 如果您逐步向下遍历，则确定完整二叉树的高度将为O（log n） .

我无法理解如何识别具有对数时间的函数 .

对数基本上是取幂的倒数 . 因此，如果您的函数的每个'step'正在从原始项集中消除 factor 元素，那么这是一个对数时间算法 .

对于树示例，您可以轻松地看到，当您继续遍历时，降低节点级别会减少指数数量的元素 . 查看名称排序电话簿的流行示例基本上等同于遍历二进制搜索树（中间页面是根元素，您可以在每个步骤推断出是向左还是向右） .

回复于 2024-04-26T16:56:47+08:00
15

O(log n) 指的是在与对数成比例的时间内工作的函数（或算法，或算法中的步骤）（在大多数情况下通常为2，但并非总是如此，并且无论如何，这通过big-O表示法无关紧要* ）输入的大小 .

对数函数是指数函数的倒数 . 换句话说，如果您的输入呈指数级增长（而非线性增长，正如您通常所认为的那样），则您的函数会线性增长 .

O(log n) 运行时间在任何一种分而治之的应用程序中都很常见，因为你（理想情况下）每次都将工作量削减了一半 . 如果在每个分区或征服步骤中，你正在做恒定的时间工作（或工作不是恒定时间，但随着时间的增长比 O(log n) 慢），那么你的整个函数是 O(log n) . 每个步骤在输入上需要线性时间是相当普遍的;这相当于 O(n log n) 的总时间复杂度 .

二进制搜索的运行时复杂度是 O(log n) 的一个例子 . 这是因为在二进制搜索中，通过将数组分成两半并且仅关注每一步的一半，您总是在每个后续步骤中忽略输入的一半 . 每个步骤都是常量时间，因为在二进制搜索中，您只需要将一个元素与您的键进行比较，以便在不考虑您在任何时候考虑的数组大小的情况下确定下一步该做什么 . 所以你做了大约log（n）/ log（2）步骤 .

合并排序的运行时复杂性是 O(n log n) 的一个示例 . 这是因为您将每个步骤将数组分成两半，从而导致总共大约log（n）/ log（2）步骤 . 但是，在每个步骤中，您需要对所有元素执行合并操作（无论是对n / 2个元素的两个子列表进行合并操作，还是对n / 4个元素的四个子列表进行两次合并操作，都是无关紧要的，因为它增加了必须为每个步骤中的n个元素执行此操作） . 因此，总的复杂性是 O(n log n) .

*记住，大O符号，by definition，常数无所谓 . 对于对数，change of base rule，不同碱基的对数之间的唯一差异是常数因子 .

回复于 2024-04-26T16:56:47+08:00
8

简单地说：在算法的每一步，您都可以将工作量减半 . （渐近相当于第三，第四，......）

回复于 2024-04-26T16:56:47+08:00
4

O（log n）有点误导，更准确地说它是O（log2 n），即（与基数2的对数） .

balancer 二叉树的高度为O（log2 n），因为每个节点都有两个（注意"two"与log2中的子节点一样 . 因此，具有n个节点的树具有log2 n的高度 .

另一个例子是二进制搜索，它的运行时间为O（log2 n），因为在每一步你将搜索空间除以2 .

回复于 2024-04-26T16:56:47+08:00
8

它只是意味着这个任务所需的时间随着log（n）而增长（例如：n = 10时为2s，n = 100时为4s，......） . 阅读Binary Search Algorithm和Big O Notation上的维基百科文章，了解更多精确内容 .

回复于 2024-04-26T16:56:47+08:00
7

如果你在图形计算器或类似的东西上绘制对数函数，你会发现它上升得非常慢 - 甚至比线性函数更慢 .

这就是为什么具有对数时间复杂度的算法备受追捧的原因：即使对于非常大的n（例如，n = 10 ^ 8），它们的表现也超过了可接受的程度 .

回复于 2024-04-26T16:56:47+08:00

这两种情况需要O（log n）时间

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

回复于 2024-04-26T16:56:47+08:00

124
完整的二进制示例是O（ln n），因为搜索如下所示：
```
1 2 3 4 5 6 7 8 9 10 11 12
```
搜索4个产生3个命中：6,3然后4个 . 然后log2 12 = 3，这对于需要多少命中是一个很好的选择 .
回复于 2024-04-26T16:56:47+08:00
3

但究竟什么是O（log n）

这恰恰意味着“因为 n 倾向于 infinity ， time 倾向于 a*log(n) ，其中 a 是一个恒定的比例因子” .

或者实际上，它并不意味着;更可能意味着“ time 除以 a*log(n) 趋于 1 ” .

"Tends towards"具有'analysis'中通常的数学含义：例如，“如果你选择任意小的非零常数 k ，那么我可以找到相应的值 X ，使 ((time/(a*log(n))) - 1) 小于 k ， n 的所有值都大于 X . “

用非专业术语来说，这意味着时间等式可能还有其他一些组成部分：它可能有一些不断的启动时间;但是对于大的n值，这些其他成分显得微不足道，而a * log（n）是大n的主要术语 .

请注意，如果等式是，例如......

time（n）=博客（n）cn dnn

...那么这将是O（n平方）因为，无论常数a，b，c和非零d的值是什么， d*n*n 术语总是占据其他任何足够大的n值 .

这就是O符号的含义：它意味着“任何足够大的n的主导项的顺序是什么” .

回复于 2024-04-26T16:56:47+08:00
64

我可以添加一些有趣的东西，很久以前我在Kormen等书中读过 . 现在，想象一个问题，我们必须在问题空间中找到解决方案 . 这个问题空间应该是有限的 .

现在，如果你可以证明，在你的算法的每次迭代中，你切断了这个空间的一小部分，这不小于某个限制，这意味着你的算法在O（logN）时间内运行 .

我应该指出，我们在这里谈的是相对分数限制，而不是绝对限制 . 二分搜索是一个经典的例子 . 在每一步，我们都会抛弃1/2的问题空间 . 但二元搜索并不是唯一的例子 . 假设，你以某种方式证明，在每一步你丢失至少1/128的问题空间 . 这意味着，您的程序仍在O（logN）时间运行，但速度明显慢于二进制搜索 . 这是分析递归算法的一个非常好的暗示 . 通常可以证明，在每个步骤中递归都不会使用多个变量，这会导致问题空间中某些部分的截止 .

回复于 2024-04-26T16:56:47+08:00
524
log x to base b = y 是 b^y = x 的倒数

如果你有一个深度为d且大小为n的M-ary树，那么：
- 遍历整棵树~O（M ^ d）= O（n）
- 在树中走一条路径~O（d）= O（log n到基数M）
回复于 2024-04-26T16:56:47+08:00
9
我可以给出一个for循环的例子，也许一旦掌握了概念，也许在不同的环境中理解起来会更简单 .

这意味着在循环中，步骤呈指数增长 . 例如 .
```
for (i=1; i<=n; i=i*2) {;}
```
该程序的O符号的复杂度为O（log（n）） . 让我们尝试手动循环（n介于512和1023之间（不包括1024）：
```
step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512
```
虽然n介于512和1023之间，但只发生了10次迭代 . 这是因为循环中的步骤呈指数增长，因此只需10次迭代即可达到终止 .

x的对数（到a的基数）是^ x的反函数 . 这就像说对数是指数的倒数 .

现在试着这样看，如果指数增长得非常快，那么对数增长（反向）非常慢 .

O（n）和O（log（n））之间的差异很大，类似于O（n）和O（a ^ n）之间的差异（a是常数） .
回复于 2024-04-26T16:56:47+08:00
2296
在信息技术中，它意味着：
```
f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.
```
Ant 似乎这种符号主要来自数学 .

在本文中有一个引用：D.E. Knuth, "BIG OMICRON AND BIG OMEGA AND BIG THETA", 1976：

根据这里讨论的问题，我建议SIGACT的成员以及计算机科学和数学期刊的编辑采用上述定义的符号，除非可以很快找到更好的替代方案 .

今天是2016年，但我们今天仍然使用它 .

在数学分析中，它意味着：
```
lim (f(n)/g(n))=Constant; where n goes to +infinity
```
但即使在数学分析中，有时这个符号也用于意义“C * g（n）> f（n）> 0” .

正如我从大学所知，这个符号是由德国数学家Landau（1877-1938）引入的 .
回复于 2024-04-26T16:56:47+08:00
7

实际上，如果你有一个n个元素的列表，并从该列表中创建一个二叉树（比如分而治之算法），你将继续除以2直到达到大小为1的列表（叶子） .

在第一步，你除以2.你有2个列表（2 ^ 1），你每个除以2，所以你有4个列表（2 ^ 2），再划分，你有8个列表（2 ^ 3））等等，直到你的列表大小为1

这给了你等式：

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

（你拿每边的lg，lg是原木底座2）

回复于 2024-04-26T16:56:47+08:00
212
每次我们编写算法或代码时，我们都会尝试分析它的渐近复杂性 . 它与 time complexity 不同 .

渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间 . 但是有些人可以互换使用这些术语 .

因为时间复杂性取决于各种参数即 .
1.物理系统
2.编程语言
编码风格
还有更多......

The actual execution time is not a good measure for analysis.

相反，我们将输入大小作为参数，因为无论代码是什么，输入都是相同的 . So the execution time is a function of input size.

以下是线性时间算法的示例

Linear Search
给定n个输入元素，要搜索数组中的元素，您需要 at most 'n' comparisons . 换句话说，无论您使用何种编程语言，您喜欢哪种编码风格，执行它的系统 . 在最坏的情况下，它只需要n次比较 . 执行时间与输入大小成线性比例 .

它不仅仅是搜索，无论是工作（增量，比较还是任何操作），它都是输入大小的函数 .

因此，当您说任何算法都是O（log n）时，它意味着执行时间是日志乘以输入大小n .

随着输入大小的增加，完成的工作（这里是执行时间）增加 . （因此比例）
```
n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work
```
随着输入尺寸的增加，工作量增加，并且它独立于任何机器 . 如果你试图找出工作单元的 Value 它实际上依赖于那些上面指定的参数 . 它将根据系统和所有变化 .
回复于 2024-04-26T16:56:47+08:00
28
如果您正在寻找基于直觉的答案，我想为您提出两种解释 .
- 想象一座非常高的山丘，底部也很宽阔 . 到达山顶有两种方式：一种是围绕山顶螺旋形地穿过顶部的专用通道，另一种是用于雕刻的小露台，以提供楼梯 . 现在，如果第一种方式达到线性时间O（n），则第二种方式是O（log n） .
- 想象一个算法，它接受一个整数， n 作为输入，并按照与 n 成比例的时间完成，然后它是O（n）或theta（n），但如果它与 number of digits or the number of bits in the binary representation on number 的时间比例运行，那么算法在O中运行（log n）或theta（log n）时间 .
回复于 2024-04-26T16:56:47+08:00
17

我想补充一点，树的高度是从根到叶子的最长路径的长度，并且节点的高度是从该节点到叶子的最长路径的长度 . 路径表示在两个节点之间遍历树时遇到的节点数 . 为了实现O（log n）时间复杂度，树应该是 balancer 的，这意味着任何节点的子节点之间的高度差应该小于或等于1.因此，树并不总是保证时间复杂度O（log n），除非它们是 balancer 的 . 实际上在某些情况下，在最坏情况下，在树中搜索的时间复杂度可以是O（n） .

您可以查看余额树，例如 AVL tree . 这个用于在插入数据时 balancer 树，以便在树中搜索时保持（log n）的时间复杂度 .

回复于 2024-04-26T16:56:47+08:00

O（log n）究竟意味着什么？

30 回答

相关问题