我写了一个程序,用于计算给定输入数字中最大的2的幂。例如,数字26中最大的2的幂是16,因为24等于16。以下是算法:
uint power2( uint n )
{
uint i = n;
uint j = i & (i - 1);
while( j != 0 )
{
i = j;
j = i & (i - 1);
}
return i;
}
我在算法分析方面有些困难。我知道我们试图确定大写-Oh、大写-Omega或大写-Theta符号。为了分析一个算法,我们应该计算基本操作的数量吗?我的问题是我看到两行可能是基本操作。我看到while循环外面的一行uint j = i & (i - 1)
,还有while循环里面的j = i & (i - 1)
。我觉得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)
等吗?