algorithm - 一个基本示例的时间复杂度

Question

我遇到了一个例子，想计算这段代码的顺序(时间复杂度)。有人可以帮助我了解如何计算此代码的顺序:

f(n)
{
    i=0;
    while (n>0) {
        n=n/10;
        i=i+1;
    }
    return (i);
}

其实我觉得顺序是O(n/10)。有高手可以帮帮我吗？

Answer 1

时间复杂度为 O(log n)，因为在每次迭代中 n 除以 10。

用 Master theorem 证明:在你的情况下，a = 1，b = 10，c = log(a) = 0，k = 0，所以 T(n)=O(log n)