我将如何使用 "Big Oh" 符号来分析该算法以及如何改进该算法的运行时间？

Question

算法解释为：

代码：

public static int g(int n)
{
    if (n==1)
        return 1;
    else if (n%2==0)
        return 1 + g(n/2);
    else
        return 1 + g(n-1);
}

Answer 1

复杂度：log (n)

解释：

如果你看一下 n 和 g(n) 的二进制表示法。

*****0 => ***** (left shift)
*****1 => ****0 (change last 1 to 0) => **** (left shift)

因此，在最坏的情况下，每 2 次迭代减少一位运行次。

所以总操作数：2*log₂(n) = O( log₂(n)).

Answer 2

当一个数字在其二进制表示中即使是最右边的位也是 0。将数字除以 2 会删除此零。

N = 16       => 8       => 4      => 2     => 1
    (10000)2 => (1000)2 => (100)2 => (10)2 => 1

当一个数字是奇数时，其二进制表示中最右边的位是 1。该算法在收到奇数时递减数字。递减奇数将导致最右边的位从 1 更改为 0。所以数字变成偶数，然后算法将这个数字除以 2，所以最右边的位将被删除。

所以当数字的二进制表示由所有 1 组成时，算法的最坏情况发生：

1111111111111

发生这种情况时，算法会分两步删除每个 1

1111111111111 decrement it because it is odd
1111111111110 divide it by two because it even 
111111111111

所以在最坏的情况下，需要 2* 个 1 才能达到 1。 1的个数与log₂N成正比。所以算法属于O(logN).

Answer 3

O(lg(n))：如果输入是2的幂，每次调用都除以2，显然是lg(n)。对于任何其他输入，至少每第二个操作除以 2（如果一个操作减去一个，输入之前是关闭的，现在是偶数）。所以最多有2*log(n)次操作，也就是O(lg(n)).

How would I go about analyzing this algorithm using "Big Oh" notation and how could I improve the run time of this algorithm?