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

我们可以对这段代码做出的一个重要观察是，在执行任意两个步骤之后，n 的大小将减少（大约）2/3 倍。这就是为什么。考虑 n 的任何初始值并查看余数模三。

• 如果余数是 1 或 2，我们将 n 除以 9 并向下取整。
• 否则，余数为 0。设置 n = 5n + 1 现在使 n 的余数为 1，因此在下一次迭代中，我们将其除以 9。n 的新值是 (5n + 1) / 9 的下限，即（粗略地说）原始值的 5/9。肯定不超过原值的2/3s。

因此，我们知道这将在 O(log n) 步后终止，因为每次迭代都会将 n 减少某个常数因子。

希望这可以帮助！

Answer 2

它是 O(log(n))。每次你做 5n+1 时，你都跟着除以 9（因为 5n+1=1 mod 3 如果 n=0 mod 3），所以最坏的情况是你每两步做 (5n+1)/9 , 每两步小于 2n/3。这是 O(log(n))。如果碰巧 n mod 3 永远不会为 0，那么您将每步除以 9，这也是 O(log(n))，只是常数不同。

所以无论 n 是什么，你都将采取 O(log(n)) 步骤来达到 1 或 0。