简单算法的复杂性

Question

我有以下算法，但我不知道它的复杂性。有人可以帮我吗？输入大小为 n.

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

非常感谢！

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（log in base 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).

complexity of simple algorithm