algorithm - 一个子调用为 n/2 的递归函数的 Big Oh 表示法是什么？

Question

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

我认为时间复杂度将是对数的，即 O(log n)，但我无法弄清楚如何。谁能帮我这个？

标签： algorithmrecursiontime-complexitybig-o

Answer 1

复杂度为 O(logn)。想象一下二进制表示中的数字。然后整数除以 2 相当于从该表示中删除最低有效位。当所有位都被消耗完后，基本情况就会启动。由于数字在其二进制表示中具有 O(logn) 位，这也是此递归函数的复杂性。