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

我正在学习大O符号的运行时间和摊销时间。我理解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，但我不知道如何识别具有对数时间的函数。

当前回答

对数

好的，让我们试着完全理解对数到底是什么。

想象一下，我们有一根绳子，把它拴在一匹马身上。如果绳子直接系在马身上，那么马拉离（例如，从人身上）所需的力直接为1。

现在想象绳子绕在一根杆子上。要想脱身的马现在必须用力拉很多倍。次数取决于绳索的粗糙度和杆的大小，但我们假设它会将一个人的力量乘以10（当绳索完全转弯时）。

现在，如果绳子绕一圈，马需要用力拉10倍。如果人类决定让马变得很困难，他可以再次将绳子绕在一根杆子上，使它的力量增加10倍。第三个循环将再次将强度增加10倍。

我们可以看到，对于每个循环，值增加10。获得任何数字所需的圈数称为数字的对数，即我们需要3个柱将你的力量乘以1000倍，需要6个柱将力量乘以1000000。

3是1000的对数，6是1000000的对数（以10为底）。

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

在上面的例子中，我们的“增长率”是O（logn）。每增加一圈，我们的绳子所能承受的力就会增加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次尝试中猜出数字，但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（logn）），因此整个算法为=O（n logn）。

免责声明：绳对数示例摘自W.Sawyer的《数学家的喜悦》一书。

2016-10-08 14:27:54

其他回答

O（logn）指的是一个函数（或算法，或算法中的步骤），其工作时间与输入大小的对数成正比（大多数情况下通常以2为基数，但并不总是以2为底，在任何情况下，通过big-O符号*，这都是无关紧要的）。

对数函数是指数函数的倒数。换句话说，如果您的输入呈指数增长（而不是通常认为的线性增长），则函数呈线性增长。

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

二进制搜索的运行时间复杂性是O（logn）的一个例子。这是因为在二进制搜索中，通过将数组分成两半，并且每一步只关注一半，您总是忽略后面每一步的一半输入。每一步都是恒定的时间，因为在二进制搜索中，您只需要将一个元素与关键字进行比较，就可以确定下一步要做什么，而不管您考虑的数组在任何时候都有多大。因此，大约执行log（n）/log（2）步。

合并排序的运行时间复杂性是O（n log n）的一个例子。这是因为每一步都将阵列一分为二，总共约为log（n）/log（2）步。然而，在每一步中，您都需要对所有元素执行合并操作（无论是对n/2个元素的两个子列表执行一次合并操作，还是对n/4个元素的四个子列表执行两次合并操作都是无关紧要的，因为这增加了每一步对n个元素执行合并的必要性）。因此，总复杂度为O（n log n）。

*记住，根据定义，big-O表示法并不重要。同样，通过改变对数的基数规则，不同基数的对数之间的唯一差异是一个常数因子。

2010-02-21 20:19:05

O（logn）是衡量任何代码运行时性能的多项式时间复杂度之一。

我希望你已经听说过二进制搜索算法。

假设您必须在大小为N的数组中找到一个元素。

基本上，代码执行如下N不适用于2不适用于4N/8…等

如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）

2019-05-30 12:05:21

O（logN）基本上意味着时间线性上升，而N指数上升。因此，如果计算10个元素需要1秒，则计算100个元素需要2秒，计算1000个元素需要3秒，依此类推。

当我们进行分而治之的算法（如二进制搜索）时，它是O（logn）。另一个例子是快速排序，每次我们将数组分成两部分，每次都需要O（N）时间才能找到一个枢轴元素。因此，N O（log N）

2010-02-21 20:18:24

下面的解释是使用完全平衡的二叉树来帮助您理解我们如何获得对数时间复杂度。