相关疑难解决方法(0)

我目前正在学习Big O Notation运行时间和摊销时间.我理解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(log n)？例如,说完整二叉树的高度是O(log n)是什么意思？

我知道(可能不是非常详细)什么是对数,在这个意义上:log ₁₀ 100 = 2,但我无法理解如何识别具有对数时间的函数.