如何计算该算法的大O符号的时间复杂度
我需要帮助找到这个函数的时间复杂度大O表示法：
int myfunction(bool exists)
{
int var=0; int k,j,n;
if (exists)
for(k=1; k<=n; k*=2)
for(j=1; j<=k; j++)
var++;
else
for(k=1; k<=n; k*=2)
for(j=1; j<=n; j++)
var++;
return var;
}
从我从书中理解的情况来看，在这种情况下，当我们有if-else块时，算法的整体复杂性是两个块的最坏情况，所以我计算了else块的复杂度，其复杂度为O （log2（n）），纠正我，如果我错了，但我很难找出if块的时间复杂性，似乎它需要更少的时间，但我无法确定多少。
正式的答案是将IF块和ELSE块分开：
在其他情况下，你循环n * floor（log 2（n））次。 因为我们想要big-O，所以我们采取最坏的情况，其中floor（log 2（n））== log2（n）。 因此，else循环是O（n log2（n））。 实际上，我通常在这里写O（n log（n）） - 在大O表示法中，你不会放入常量因子，比如日志基数的变化。
在if情况下，内部循环运行1，2，4，...，2 ^ x次，其中x是floor（log2（n））。 循环的总数是这些数字的总和，即2 ^（x + 1）-1。 如果你看不到这一点，注意1,2,4等只是二进制数字。 如果你填写这些数字，总数是多少？ 你会发现它是一个像11111这样的二进制数字。
因此，if循环需要2 ^（floor（log 2（n））+ 1） - 1步; 在最糟糕的情况下，这是2 ^（log 2（n）+ 1） - 1 = 2n - 1。保持最大的项，并删除常数，这是O（n）。
链接地址: http://www.djcxy.com/p/39913.html上一篇: how to calculate time complexity in big O notation of this algorithm