2

So I have a loop embedded inside a loop here:

int a,b,n;
for (a = 1; a <=n; a++) {
    for (b = 0; b < n; b+=a)
        cout << "hey" << endl;
}

n is a power of 2

I'm trying to understand how to calculate the Time complexity of this however I'm having trouble figuring out the Big-theta notation for this.

I know that the the outter loop runs in O(n) time, but I'm not sure about the inner loop due to the b+=a. I know that If I had the time for both loops, I could multiply them to get the Big-theta time of the function, but I'm not sure what the inner loop is running at.

When I plug in sample n's (ie. 2, 4, 8, 16), then the inner loop is looped 3, 9, 24, 61 times, respectively. I don't see how these values correlate.

Edit:

Ok I see what you are saying, but I'm trying to compare it to this function. What would the time for this function be? Then i can compare the speed of the two:

int a,b,n;
int z = 1;
for (a = 0; a <n; a++) {
    for (b = 0; b < n; b=b+z)
        cout << "hey" << endl;
    z = z * 2;
}
4

1 回答 1

3

可以看到内循环运行了 a 包含在 n 中的次数，即满足的最大整数 k：

它对应于天花板函数。所以内循环的总迭代次数为：

第二个和是除数求和函数，可以写成：

所以整个代码的时间复杂度是O(nlogn)。

编辑

关于您发布的第二段代码，计算更简单。如果n=2^k，迭代次数为：

所以第二个更快，因为它是 O(n)。

于 2014-09-17T00:45:37.030 回答