o（log n）到底是什么意思？

Question

我正在学习大o符号的运行时间和摊销时间。我了解 上） 线性时间，这意味着输入的大小会按比例地影响算法的生长……例如，二次时间也是如此 上²) 等等..甚至算法，例如置换生成器， 上！） 时代，这是通过阶乘增长的。

例如，以下功能是 上） 因为该算法与其输入成正比生长 n:

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

同样，如果有一个嵌套循环，时间将为o（n²).

但是到底是什么 o（log n）？例如，说完整的二进制树的高度是什么意思 o（log n）?

我确实知道（也许不太详细）什么是对数，从某种意义上说：日志₁₀ 100 = 2，但我不明白如何用对数时间识别功能。

Answer 1

我不明白如何用日志时间识别功能。

对数运行时函数的最常见属性是：

• 执行某个动作的下一个要素的选择是几种可能性之一，并且
• 只需要选择一个。

或者

• 执行动作的元素是N的数字

例如，这就是为什么在电话簿中查找人们的原因是O（log n）。您不需要检查 每一个 电话簿中的人找到合适的书；取而代之的是，您可以通过基于其名称在字母内的位置来简单地进行划分，并且在每个部分中，您只需要探索每个部分的子集，然后才能最终找到某人的电话号码。

当然，一本更大的电话簿仍会花费您更长的时间，但是它不会像额外尺寸的比例增加一样快地增长。

---

我们可以扩展电话簿示例以比较其他类型的操作，并 他们的 运行时间。我们将假设我们的电话簿有 企业 （“黄色页面”）具有唯一名称和 人们 （“白页”）可能没有唯一的名称。电话号码最多是一个人或企业。我们还将假设翻转到特定页面需要持续的时间。

以下是我们可能在电话簿上执行某些操作的运行时间，从最佳到最糟糕：

• o（1）（最佳情况）： 鉴于企业名称所在的页面和业务名称，请找到电话号码。

• o（1）（平均情况）： 鉴于一个人的名字及其名字的页面，请找到电话号码。

• o（log n）： 鉴于一个人的名字，通过在您尚未搜索的书的一半中选择一个随机点来找到电话号码，然后检查一下该人的名字是否在那时。然后重复该过程的一部分，该过程在该人的名字所在的地方。 （这是对一个人的名字的二进制搜索。）

• 上）： 找到所有电话号码包含数字“ 5”的人。

• 上）： 给定电话号码，找到具有该号码的人或企业。

• o（n log n）： 打印机的办公室有一个混音，我们的电话簿随机插入了所有页面。修复订单，以便通过查看每个页面上的名字，然后将该页面放在新的空电话书中的适当位置。

对于以下示例，我们现在在打印机的办公室。电话簿正在等待邮寄给每个居民或企业，并且每本电话簿上都有一个贴纸，以确定应邮寄到哪里。每个人或企业都会收到一本电话簿。

• o（n log n）： 我们想个性化电话簿，因此我们将在指定的副本中找到每个人或企业的名字，然后在书中圈出他们的名字，并写下简短的感谢信。

• 上²): 在办公室发生了一个错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的“ 0”。取出一些白色，然后删除每个零。

• o（n·n！）： 我们准备将电话簿加载到运输码头上。不幸的是，本来应该加载书籍的机器人已经变成了干草：它将书籍随机订购！更糟糕的是，它将所有书籍都加载到卡车上，然后检查它们是否处于正确的顺序，如果没有，它将卸下并重新开始。 （这是可怕的 Bogo排序.)

• 上ⁿ): 您可以修复机器人，以便正确加载东西。第二天，您的一位同事对您进行恶作剧，并将加载码头机器人固定到自动打印系统。每当机器人加载原始书籍时，工厂打印机都会重复运行所有电话簿！幸运的是，机器人的错误检测系统已经足够复杂，以至于机器人在遇到重复的书籍时不会尝试打印更多的副本，但是它仍然必须加载每本打印的原始和重复的书。

有关更多数学解释，您可以检查时间复杂性如何到达 log n 这里。 https://hackernoon.com/what-does-time-complexity-o-log-n-actally-mean-45f94bb5bfbf

Answer 2

这个问题已经发布了许多好的答案，但是我相信我们确实缺少一个重要的答案 - 即说明的答案。

说完整的二进制树的高度是o（log n）意味着什么？

以下图形描绘了一棵二进制树。请注意，与上述级别相比，每个级别的含量含量是节点数量的两倍（因此 二进制):

二进制搜索是一个复杂性的示例 O(log n). 。假设图1中树底部的节点表示某些排序集合中的项目。二进制搜索是一种划分和争议算法，该图显示了我们将如何（最多）4个比较来找到我们在此16个项目数据集中搜索的记录。

假设我们有一个具有32个元素的数据集。继续上面的图纸，以发现我们现在需要5个比较来查找我们正在搜索的内容，因为当我们乘以数据量时，这棵树只会更深一个水平。结果，算法的复杂性可以描述为对数顺序。

绘图 log(n) 在平淡的纸上，将导致曲线的上升减速为图 n 增加：

Answer 3

O(log N) 基本上意味着时间线性上升，而 n 呈指数级上。所以如果需要 1 第二要计算 10 元素，它将需要 2 秒计算 100 元素， 3 秒计算 1000 元素，等等。

是 O(log n) 当我们进行划分并征服算法类型时，例如二进制搜索。另一个示例是快速排序，每次我们将数组分为两个部分，每次需要 O(N) 是时候找到一个枢轴元素了。因此 N O(log N)

Answer 4

下面的解释使用了完全的情况 均衡 二进制树可帮助您了解我们如何获得对数时间复杂性。

二进制树是大小N的问题分为N/2的子问题，直到我们达到1尺寸的问题：

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

具有O（log n）时间复杂性的常见算法是二进制搜索，其递归关系为t（n/2） + o（1）IE在树的每个后续级别，您将问题分为一半，并进行持续数量的其他工作。

Answer 5

概述

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

首先，您需要有一个对数的一般想法，您可以从中得到 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的天花板。

各种大型类别的简单代码示例：

o（1） - 恒定时间示例：

• 算法1：

算法1打印Hello一次，并且不取决于n，因此它将始终在恒定时间内运行，所以它是 O(1).

print "hello";

• 算法2：

算法2打印Hello 3次，但是它不取决于输入大小。即使N成长，此算法也总是只打印3次。就是说3是一个常数，所以该算法也是 O(1).

print "hello";
print "hello";
print "hello";

o（log（n）） - 对数示例：

• 算法3-类似于“ log_2”

算法3演示了在log_2（n）中运行的算法。请注意，for循环的后操作将i的当前值乘以2，因此 i 从1到2到4到8至16到32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• 算法4-这类似于“ log_3”

算法4演示了log_3。注意 i 从1到3到9到27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• 算法5-这类似于“ log_1.02”

算法5很重要，因为它有助于表明只要数字大于1，并且结果反复乘以自身，那么您正在查看对数算法。

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

o（n） - 线性时间示例：

• 算法6

该算法很简单，它打印了Hello n次。

for(int i = 0; i < n; i++)
  print "hello";

• 算法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）示例：

• 算法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";

• 算法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平方示例：

• 算法10

O(n^2) 通过循环的嵌套标准轻松获得。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

• 算法11

像算法10一样，但有一些变化。

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

o（n^3） - n立方体示例：

• 算法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";

• 算法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";

概括

上面给出了几个直接的示例，以及有助于证明可以引入哪些微妙变化的变化，这些变化确实不会改变分析。希望它能为您提供足够的见识。

Answer 6

如果您有一个功能：

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.

然后进行日志₂（n）时间。这 大o符号, 宽松地说，这意味着这种关系对于大n只需要真实，并且可以忽略不断的因素和较小的术语。

Answer 7

对数跑步时间（O(log n)）本质上意味着运行时间与 对数 输入大小 - 例如，如果10个项目最多需要一段时间 x, 和100个物品最多占用，例如 2x, ，最多有10,000个物品 4x, ，然后看起来像个 O(log n) 时间复杂性。

Answer 8

对数

好的，让我们尝试完全了解对数的实际是什么。

想象一下，我们有一根绳子，我们将其绑在一匹马上。如果绳索直接与马匹绑在一起，那么马将需要拉开的力（例如，从男人那里）直接1。

现在想象一下绳索被绕杆绕。现在要逃脱的马将不得不更努力地拉动很多次。时间的数量将取决于绳索的粗糙度和杆的尺寸，但假设它会将其强度乘以10（当绳索完全转弯时）。

现在，如果绳索循环一次，马将需要更艰难地拉10倍。如果人类决定使马真正困难，他可能会再次将绳子绕杆绕，从而增加了强度的10次。第三个循环将再次增加10倍。

我们可以看到，对于每个循环，值增加10个。获取任何数字所需的回合数称为数字的对数，即我们需要3个帖子，将3个帖子多于您的强度乘以1000倍，6个帖子以将您的强度乘以乘以1,000,000。

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

那么o（log n）实际上是什么意思？

在上面的示例中，我们的“增长率”是 o（log n）. 。对于每一个额外的循环，我们的绳索可以处理的力是10倍：

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

现在，上面的示例确实使用了基本10，但幸运的是，当我们谈论大o符号时，日志的底数微不足道。

现在，让我们想象您正在尝试猜测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之间的数字，它将带我们 最多 7尝试。如果我们有128个数字，我们也可以猜测7个Attemps中的数字，但129个数字将带我们 最多 8尝试（与对数关系中，在这里我们需要7个猜测，即128个值范围，10个猜测1024值范围。7是他的对数为128，10是1024（基数2）的对数。

请注意，我最多加了“最多”。大o符号总是指更糟糕的情况。如果幸运的话，您可以一次尝试猜测这个数字，因此最好的情况是O（1），但这是另一个故事。

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

那o（n log n）呢？

您最终会遇到一个衬里时间 o（n log（n） 算法。上面的经验法则再次适用，但是这次对数函数必须运行n次，例如减少列表的大小 n次, ，它发生在算法中。

您可以轻松识别算法时间是否为n log n。寻找通过列表（O（n））迭代的外循环。然后查看是否有内部循环。如果内部循环是 切割/还原 每次迭代的数据集，循环为（o（log n），因此总体算法为= o（n log n）.

免责声明：从优秀的绳子上示例 W.Sawyer的数学家Delight Book.

Answer 9

您可以通过说出时间与N。

如果操作在每个数字或输入的位上执行恒定的时间工作，则整个操作将花费时间与输入中的数字或位数成正比，而不是输入的大小。因此，o（log n）而不是o（n）。

如果操作做出一系列恒定的时间决策，每半（减少3、4、5。 ，底座4，底座5 ...）的大小为n，而不是o（n）。

等等。

Answer 10

我一直在心理上可视化在O（log n）中运行的算法的最好方法是：

如果将问题的大小增加乘以乘以（即将其大小乘以10），则该工作仅增加了添加量。

将其应用于您的二进制树问题，因此您有一个很好的应用：如果将二进制树中的节点数量增加一倍，则高度仅增加1（添加量）。如果您再次加倍，它仍然只增加1。（显然我假设它保持平衡等）。这样一来，您的工作倍增时就不会使您的工作增加一倍，而是做更多的工作。这就是为什么O（log n）算法很棒的原因。

Answer 11

首先，我建议您阅读以下书；

算法（第四版）

这是一些功能及其预期的复杂性。数字指示 语句执行频率.

下列的 Big-O复杂性图 也取自 BigocheatSheet

最后，非常简单的展示显示了如何计算它。

程序声明执行频率的解剖学。

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

Answer 12

什么是日志_b（n）？

这是您可以在达到尺寸1的一部分之前反复将长度n的日志缩短为B等份的次数。

Answer 13

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

在二进制搜索的情况下，您丢弃了一半输入的每一次迭代。应该注意的是，在Big-O符号中，日志是LOG BASE 2。

编辑：如前所述，日志库并不重要，但是当得出算法的BIG-O性能时，日志因子将来自减半，因此我为什么将其视为基础2。

Answer 14

但是O（log n）到底是什么？例如，说完整的二进制树的高度是o（log n）意味着什么？

我会将其重新为“完整的二进制树的高度为log n”。如果您逐步逐步穿越，则确定完整的二进制树的高度将为O（log n）。

我不明白如何用对数时间识别功能。

对数实质上是凸起的倒数。因此，如果您的功能的每个“步骤”消除了 因素 原始项目集中的元素，即对数时间算法。

对于树的示例，您可以轻松地看到，在继续穿越时，逐步降低一级节点会减少指数数量的元素。浏览名称分数的流行示例本质上等同于沿二进制搜索树（中页是根元素），您可以在每个步骤中推断出是向左还是向右）。

Answer 15

这2个情况将花费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);
    }

Answer 16

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符号， 根据定义, ，常数无关紧要。也是 基本规则的改变 对于对数，不同基础的对数之间的唯一差异是一个恒定因素。

Answer 17

o（log n）有点误导，更确切地说是o（log₂ n），IE（对数为2）。

平衡二进制树的高度为o（日志₂ n），因为每个节点都有两个（请注意“两个”，如日志中₂ n）儿童节点。因此，带有N节点的树具有日志高度₂ n。

另一个示例是二进制搜索，其运行时间为o（日志₂ n），因为在每个步骤中，您将搜索空间除以2。

Answer 18

这仅表示此任务所需的时间随log（n）而生长（示例：n = 10，4s for n = 100，...）。阅读有关Wikipedia文章 二进制搜索算法 和 大o符号 有关更精确的。

Answer 19

简而言之：在算法的每个步骤中，您都可以将工作切成两半。 （渐近等同于第三，第四，...）

Answer 20

如果您在图形计算器上绘制对数函数或类似的内容，您会发现它的升高非常慢 - 甚至比线性函数更慢。

这就是为什么具有对数时间复杂性的算法受到高度追捧的原因：即使对于真正的n（例如，n = 10^8），它们的表现胜于接受。

Answer 21

但是o（log n）到底是什么

精确的含义是“ n 倾向于 infinity, ， 这 time 倾向于 a*log(n) 在哪里 a 是一个恒定的缩放因素”。

或者实际上，这并不意味着这一点；更有可能的意思是像time 除以 a*log(n) 倾向于 1".

“倾向于”具有'分析'的通常数学含义：例如，如果您选择 任何 任意小的非零常数 k, ，然后我可以找到一个相应的值 X 这样 ((time/(a*log(n))) - 1) 小于 k 对于所有值 n 比...更棒 X."

---

简而言之，这意味着时间的方程可能还有其他一些组件：例如，它可能具有一定恒定的启动时间；但是，对于大n值，这些其他组件对大量值呈微不足道，而a*log（n）是大n的主导项。

请注意，如果方程是...

时间（n）= a + blog（n） + cn + dnn

...那么这将是o（n平方），因为无论常数A，B，C和非零D的值如何 d*n*n 对于任何足够大的n价值，术语始终将主导其他术语。

这就是o符号的含义：它的意思是“任何足够大的n的占主导地位的顺序是什么”。

Answer 22

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

现在，如果您可以证明，在算法的每一次迭代中，您都会切断该空间的一小部分，这不低于某些限制，这意味着您的算法在O（logn）时间内运行。

我应该指出的是，我们在这里谈论相对分数限制，而不是绝对的限制。二进制搜索是一个古典示例。在每个步骤中，我们丢弃了问题空间的1/2。但是二进制搜索并不是唯一的示例。假设您以某种方式证明，在每个步骤中，您至少要扔掉1/128的问题空间。这意味着，您的程序仍在o（logn）时间运行，尽管比二进制搜索要慢得多。这是分析递归算法的很好的提示。通常可以证明，在每个步骤中，递归不会使用多种变体，这导致问题空间中某些分数的截止。

Answer 23

我可以举个循环的示例，也许一旦掌握了这个概念，也许在不同的情况下更容易理解。

这意味着在循环中，步骤呈指数增长。例如

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的底部）是A^X的反向函数。

这就像说对数是指数的倒数。

现在尝试以这种方式看到它，如果指数增长很快，那么对数增长（成反比）非常慢。

O（n）和O（log（n））之间的差异很大，类似于O（n）和O（a^n）之间的差异（一个是常数）。

Answer 24

每次我们编写算法或代码时，我们都会尝试分析其渐近复杂性。它与它的不同 时间复杂性.

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

因为时间复杂性取决于各种参数。
1.物理系统
2.编程语言
3.编码样式
4.还有更多......

实际执行时间不是分析的好方法。

取而代之的是，我们将输入大小作为参数，因为无论代码是什么，输入都是相同的。因此，执行时间是输入大小的函数。

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

线性搜索
给定n个输入元素，要在您需要的数组中搜索一个元素 最多是“ n”比较. 。换句话说，无论您使用哪种编程语言，您喜欢哪种编码样式，都可以执行什么系统。在最坏的情况下，仅需要n比较。执行时间与输入大小成正比。

而且它不仅是搜索，无论是工作（增量，比较或任何操作）的任何输入大小的函数。

因此，当您说任何算法为o（log n）时，这意味着执行时间是log times输入大小n。

随着输入大小的增加（此处执行时间）的工作增加。（因此比例）

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

看到输入尺寸增加，完成的工作增加了，并且与任何机器无关。而且，如果您尝试找出工作单位的值，它实际上取决于上述指定参数。它将根据系统和所有内容进行更改。

Answer 25

log x to base b = y 是 b^y = x

如果您有深度D和尺寸的M-ary树，则：

• 穿越整个树〜O（m^d）= o（n）

• 在树上行走一条路径〜O（d）= o（log n到基础m）

Answer 26

在信息技术中，这意味着：

  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.

蚂蚁看来这种符号主要是从数学中获取的。

在本文中有一句话：de Knuth，“大欧米龙和大欧米茄和大塔塔”，1976年:

在此处讨论的问题的基础上，我建议Sigact的成员和计算机科学和数学期刊的编辑采用上述符号，除非 很快就可以合理地找到更好的选择.

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

---

在数学分析中，这意味着：

  lim (f(n)/g(n))=Constant; where n goes to +infinity

但是，即使在数学分析中，有时此符号在含义“ c*g（n）> f（n）> 0”中使用。

从大学中我知道，该符号是由德国数学家Landau（1877-1938）探讨的

Answer 27

实际上，如果您有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）

Answer 28

如果您正在寻找基于直觉的答案，我想为您提出两个解释。

1. 想象一个非常宽阔的基地的高山丘。要到达山顶有两种方法：一种是一条专门的道路，围绕着山顶的山顶旋转，另一个是：小露台（如雕刻雕刻），切出楼梯。现在，如果第一种方法是在线性时间O（n）中达到的，则第二个是O（log n）。

2. 想象一种接受整数的算法， 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）时间中运行。

Answer 29

完整的二进制示例是o（ln n），因为搜索看起来像这样：

1 2 3 4 5 6 7 8 9 10 11 12

搜索4次产量3次命中：6、3，然后4.和log2 12 = 3，这对需要多少命中是一个很好的适应性。

Answer 30

划分和征服范式中的算法具有复杂性o（logn）。一个示例，计算您自己的电源功能，

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

从 http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/