algorithm - 被3整除

Question

我正在阅读关于 Writing an Efficient Method to Check if a Number is Multiple of 3 的文章.

这里讲解的方法是取二进制表示的数的oddsum和evensum之差。如果差值可以被 3 整除，那么数字也可以被 3 整除。我明白我们为什么要这样做，但我无法理解为什么时间复杂度是 O(log n)。

Answer 1

递归之前的操作数受 O(log n) 的限制，因为这是表示 n 所需的位数以及随后转换任何 所需的移位操作数n 为零。下面的递归接收一个n，最多为log n/2，所以它的循环复杂度为O(log (log n/2))。由于此项小于初始循环复杂度(并且所有后续递归甚至更少)，因此可以省略。准确地说，所有递归的总和必须小于初始循环才能保持，但我非常有信心(尽管我缺乏确切的证据)这里就是这种情况。