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

Question

//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)对吗？

Answer 1

第一种情况: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。