因此,我真的没有得到Big O标记。我的任务是为此代码段确定“O值”。
for (int count =1; count < n; count++) // Runs n times, so linear, or O(N)
{
int count2 = 1; // Declares an integer, so constant, O(1)
while (count2 < count) // Here's where I get confused. I recognize that it is a nested loop, but does that make it O(N^2)?
{
count2 = count2 * 2; // I would expect this to be constant as well, O(N)
}
}
最佳答案
O(f(n))=g(n)
这意味着对于某些值
k
,f(n)>g(n)
其中n>k
。这给出了函数g(n)
的上限。当系统要求您为某些代码查找
Big O
时,1)尝试计算根据
n
执行的计算数量,从而获得g(n)
。2)现在尝试估计
g(n)
的上限函数。那就是你的答案。让我们将此过程应用于您的代码。
让我们计算进行的计算数量。语句
declaring
和multiply by 2
花费O(1)
时间。但是这些被重复执行。我们需要找到它们执行了多少次。外循环执行
n
次。因此,第一条语句执行了n
次。现在,执行内部循环的次数取决于n
的值。对于给定的n
值,它将执行logn
次。现在让我们计算执行的总数,
log(1) + log(2) + log(3) +.... log(n) + n
请注意,最后一个
n
用于第一个语句。简化以上系列,我们得到:= log(1*2*3*...n) + n
= log(n!) + n
我们有
g(n)=log(n!) + n
让我们猜测
log(n!)
的上限。以来,
1.2.3.4...n < n.n.n...(n times)
因此,
log(n!) < log(n^n) for n>1
这意味着
log(n!) = O(nlogn).
如果您需要正式证明,请检查this。由于
nlogn
比n
增长更快,因此,我们有:O(nlogn + n) = O(nlogn)
因此,您的最终答案是
O(nlogn)
。