我正在尝试使用 Big O 表示法计算 for 循环的复杂性。我之前在我的其他类(class)中也这样做过,但是这个比其他类(class)更严格,因为它是在实际算法上。代码如下:
for(i=n ; i>1 ; i/=2) //for any size n
{
for(j = 1; j < i; j++)
{
x+=a
}
}
和
for(i=1 ; i<=n;i++,x=1) //for any size n
{
for(j = 1; j <= i; j++)
{
for(k = 1; k <= j; x+=a,k*=a)
{
}
}
}
我发现第一个循环的复杂度为 O(n),因为它要遍历列表 n 次。至于第二个循环我有点迷茫!
感谢您对分析的帮助。每个循环都在自己的空间中,它们不在一起。
最佳答案
考虑第一个代码片段,
for(i=n ; i>1 ; i/=2) //for any size n
{
for(j = 1; j < i; j++)
{
x+=a
}
}
指令
x+=a
总共执行了 n + n/2 + n/4 + ... + 1
次。G.P. 的第一个 log2n 项的总和起始期限
n
和公比1/2
是, (n (1-(1/2)log2n))/(1/2) .因此第一个代码片段的复杂度是 O(n) .现在考虑第二个代码片段,
for(i=1 ; i<=n; i++,x=1)
{
for(j = 1; j <= i; j++)
{
for(k = 1; k <= j; x+=a,k*=a)
{
}
}
}
两个外循环一起调用最内循环一共
n(n+1)/2
次。最里面的循环最多执行 log<sub>a</sub>n
次。因此,第二个代码片段的总时间复杂度为 O(n2logan) .
关于loops - 嵌套循环的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16743395/