algorithm - 雹のシーケンスのバリエーションの時間の複雑さは?

Question

次のコード セグメントを検討してください。

    Looping(n) 
      {
       while (true) {
         if (n <= 1) then return;
          else if (n mod 3 = 0) then n = n * 5 + 1;
         else n = n/9; // integer division
      }

このコード セグメントの最悪の場合の時間の複雑さは? `

Answer 1

O(log(n))です。5n+1 を実行するたびに、9 で除算します (n=0 mod 3 の場合、5n+1=1 mod 3 なので)、最悪の場合、2 ステップごとに (5n+1)/9 を実行します。 、2 ステップごとに 2n/3 未満です。これは O(log(n)) です。n mod 3 が 0 にならない場合は、各ステップを 9 で割ります。これは O(log(n)) であり、定数が異なります。

したがって、n が何であれ、1 または 0 に到達するには O(log(n)) ステップを実行する必要があります。