我正在学习大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)是什么意思?
我确实知道(也许不是很详细)什么是对数,即:log10100=2,但我无法理解如何识别一个具有对数时间的函数。