java - 単純なアルゴリズムの複雑さ

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 (基数 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)になります。