algorithm - 如何计算给定算法的时间复杂度

Question

i, j, N, sum 都是整数类型。N是输入。

（代码1）

i = N;

while(i > 1)
{
    i = i / 2;
    for (j = 0; j < 1000000; j++)
    {
       sum = sum + j;
    }
}

（代码2）

sum = 0;
d = 1;
d = d << (N-1);
for (i = 0; i < d; i++)
{
    for (j = 0; j < 1000000; j++)
    {
        sum = sum + i;
    }
}

如何计算 Code1、Code2 的步数和时间复杂度？

score 1 · Accepted Answer

计算时间复杂度尝试了解什么需要多少时间，以及n你在计算什么。

如果我们说加法（“+”）需要 O(1) 步，那么我们可以检查它完成了多少次N。

第一个代码将i每个步骤分成 2，这意味着它正在执行 log(N) 步骤。所以时间复杂度是

 O(log(N) * 1000000)= O(log(N))

第二个代码以 n-1 的幂从 0 变为 2，因此复杂度为：

 O(s^(N-1) * 1000000)=  O(2^(N-1))

但这只是一个理论，因为 d 的最大值为 2^32/2^64 或其他数字，因此在实践中可能不是 O(2^(N-1))

1 回答 1