O(Log N)到底是什么意思？

Question

O(Log N)到底是什么意思？

我目前正在学习大O符号运行时间和摊销时间。我理解O(N)线性时间，这意味着输入的大小成比例地影响算法的增长.同样的情况也是如此，例如，二次时间O(N)²)等.甚至算法，如置换生成器，与O(n！)时间的增长是因式分解的。

例如，以下函数是O(N)因为该算法与其输入量成比例增长。n:

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

类似地，如果存在嵌套循环，则时间为O(N)²).

但究竟什么是O(原木n)？例如，说一个完整二叉树的高度是什么意思？O(原木n)?

我确实知道(也许不是很详细)什么是对数，从这个意义上说：日志。₁₀100=2，但我不知道如何识别具有对数时间的函数。

Answer 1

O(log N)基本上意味着时间线性上升，而n指数上升。所以如果需要1第二次计算10元素，它将需要2计算秒100元素，3计算秒1000元素等等。是O(log n)当我们进行分而治之的算法时，例如二进制搜索。另一个例子是快速排序，每次我们将数组分成两个部分，每次O(N)是时候找一个枢轴元素了。因此它N O(log N)