分析一个涉及按位运算和两个幂的算法？

Question

我写了一个程序,计算给定输入数字中最大的2的幂.例如,26中最大的2的幂是16,因为2 ⁴是16.这是算法:

uint power2( uint n )
{
   uint i = n;
   uint j = i & (i - 1);
   while( j != 0 )
   {
      i = j;
      j = i & (i - 1);
   }
   return i;
}

我对算法的分析有点挣扎.我知道我们正试图找出Big-Oh,Big-Omega或Big-Theta符号.为了分析算法,我们应该计算基本操作的数量？我的问题是我看到两行可能是基本操作.我看到uint j = i & (i - 1)while循环外面的行,我也看到j = i & (i - 1)while循环内部.我觉得while循环中的那个是肯定的基本操作,但是while循环之外的那个呢？

我努力解决的另一个问题是确定while循环体的执行次数.例如,如果我们有一个for循环,for(int i = 0; i < n; i++) {...}我们知道这个循环将执行n时间.或者甚至在while循环中while(i < n * n) {... i++}我们知道这个循环会运行n * n一次.但是对于这个while循环,它会根据输入而变化.例如,如果您传入的数字是直接击球的2,则while循环将永远不会执行.但是,如果传入一个非常大的数字,它将执行多次.我不知道它会执行多少次才能说实话.这就是我想弄清楚的.谁能帮助我了解什么是在这个算法,它运行的次数正在进行,如O(n)还是O(n^2)等？

Answer 1

这是一个很好的算法示例,当您对其正在做的事情有一个很好的直观理解而不仅仅是通过查看代码本身时,它更容易推理它.

对于初学者来说,做i & (i - 1)什么？如果你用二进制写的数字并从中减去一个,它的效果是

• 清除最不重要的1位,和
• 将之后的所有位设置为1.

例如,如果我们取二进制数1001000(72)并减去一,我们得到1000111(71).注意如何清除最低有效1位并将其下面的所有位设置为1.

当你和一个i带号码的号码时会发生什么i - 1？好了,以上两个最低显著1位所有位i,并i - 1保持不变,但i并i - 1等于或低于在最低显著1位在所有位置不以为然i.这意味着i & (i - 1)具有清除数字中最低1位的效果i.

那么让我们回到代码.请注意,while循环的每次迭代都使用此技术从数字中清除一点j.这意味着while循环的迭代次数与数字中设置的1位数成正比n.因此,如果我们b设置表示设置的1位数n,则该算法的运行时间为Θ(b).

为了了解该算法的最佳和最坏情况行为,正如您所指出的,如果n是2的完美幂,则运行时为O(1).这就好了.对于最坏的情况,数字n可以是全1位,在这种情况下,将在数字n中设置Θ(log n)1位(因为,在二进制中,数字n需要Θ(log n)位写出).因此,最坏情况的运行时间是Θ(log n).

总之,我们看到了这一点

• 最好的运行时是O(1),
• 最坏情况的运行时是Θ(log n),和
• 确切的运行时间是Θ(b),其中b是n中设置的位数.