algorithm - 算法的复杂度

Question

下面问题的复杂度是O(n)。不应该是 O(n^2)？那是因为外循环是O(n)，内循环也是O(n)，所以n*n = O(n^2)？

这道题的答卷上写着答案是O(n)。这怎么可能？

public static void q1d(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        count++;
        for (int j = 0; j < n; j++) {
            count++;
        }
    }
}

下面问题的复杂度是 O(n^2)，你如何得到它？有人可以详细说明吗？

public static void q1E(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        count++;
        for (int j = 0; j < n/2; j++) {
            count++;
        }
    }
}

谢谢

Answer 1

第一个例子是O(n^2)，看来他们犯了一个错误。要(非正式地)计算第二个示例，我们可以执行 n * (n/2) = (n^2)/2 = O(n^2)。如果这没有意义，您需要复习一下 O(n^k) 的含义。