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

Question

算法解释如下:

1. 如果n是偶数:返回1 + g(n/2)。
2. 如果n是奇数:返回1 + g(n-1)。
3. 如果n = 1:返回1.

代码:

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

当一个数字是偶数时，其二进制表示的最右位为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* 个数的1s才能到达1。1 的个数与log₂N成正比。所以算法属于O(logN)

Answer 2

复杂性:log (n)

解释:

如果你看n和g(n)的二进制符号。

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

因此，在最坏的情况下，它每2次迭代减少1位。

操作:总数 2 *日志<子> (n) = O (log <子> 2子>

Answer 3

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