java - complexity of simple algorithm

Question

I have the following algorithm but I dont know its' complexity. Could someone help me? Input size is n.

int x = n;
while (x > 0)
{
    System.out.println("Value is" + x);
    x = x/5;
}

Thanks a lot!

Answer 1

在每次迭代中，x 除以 5。x 需要多少次迭代才能低于 1（因此为 0）？

答案是log5(n)（以 n 为底的 5 的对数），即O(log(n))。

Answer 2

令 T(n) 为对输入 n 执行的操作数。

每次迭代执行 O(1) 操作。所以：

T(n) = O(1) + T(n/5)
     = O(1) + O(1) + T(n/25) = 2*O(1) + T(n/25)
     = 2*O(1) + O(1) + T(n/125) = 3*O(1) + T(n/125)

每次迭代都会将 O(1) 添加到复杂性中，并且您将运行直到 n/(5^a) < 1 其中 a 是执行的迭代次数（因为您的输入是整数）。

条件什么时候能成立？只需在不等式两边取 log5（以 5 为底数）并得到：

log5(n/(5^a)) < log5(1) = 0
log5(n) - log5(5^a) = 0
log5(n) = a*log5(5)       [because log(b^c) = c*log(b)]
log5(n) = a

因此，您将需要 log5(n) 迭代，每次都增加 O(1) ，因此您的复杂度为log5(n)。