时间戳

首页 > 解决方案 > 为 for 循环确定不同的大 O 复杂度

c++ - 为 for 循环确定不同的大 O 复杂度

问题描述

//outer for loop runs at most n times
    for (int w = 1; w < n; w++) {
        // inner for loop at most log(73550/n) times
        for (int y = w; y < 73550; y = y * 2) {
            x = x + w;
        }
        k = k * w;
    }

我真的很困惑第二个循环是否会增加大的 O 时间复杂度，因为它有一个设置的最大迭代？大 O 会是 O(n)、O(nlog(1/n)) 还是两者都不是？

        int p = 0;
        int q = 0;
        //runs at most 18n^2 times
        while (p < 18 * n * n) {
            if (p % 2 == 0) {
                q++;
            }
            p++;
        }
        //p = 18n^2 q1 = 9n^2
        //runs at most log(9n^2) times
        for (int r = 1; r < q; r = r * 3) {
            q++;
        }
        return p * q;

像这样的顺序函数的时间复杂度只是更大的时间复杂度吧？所以它将是 O(n^2) ？

//runs at most n(4n-1) times
for (int k = 2; k <= 2n(4n-1); k+=2) {
    j++;
}

即使使用-1，时间复杂度也会是 O(n^2) 对吗？

标签： c++algorithmtime-complexitybig-o

解决方案

第一种情况：O(n)，因为正如您所说，循环迭代的次数是恒定的。在循环边界上具有非常大的常数并不典型，因此在大多数自然算法中这并不是什么大问题。如果 73550 实际上是一个非常量变量，但与 n 无关，我们可以给它一个名称（例如 m），并说复杂度是O(n*log(m))。

第二种情况：是的，O(n^2)因为你给出的原因。

第三种情况：是的，O(n^2)。首先，big-O 只提供了一个上限，因此 -1 只会更容易保证上界。其次，即使你的意思是Ө(n^2)，它仍然是，因为n(4n-1) = 4n^2-n，它比k*n^2一些常数渐近地大k。在这种情况下，任何k小于 4。

推荐阅读