有n/2子调用的递归函数的大Oh符号是什么?

Question

public static int div(int numItems)
{
if (numItems == 0)
return 0;
else
return numItems%2 + div(numItems/2);
}

我认为时间复杂度将是对数的，即O(log n)，但我无法弄清楚如何。有人能帮我一下吗?

Answer 1

复杂度为O(logn)。想象一下这个数字的二进制表示。那么整数除以2就等于从这个表示中去掉最低有效位。当所有的比特都被消耗掉时，基本情况就开始生效了。因为一个数字的二进制表示有O(logn)位，这也是这个递归函数的复杂度。