算法的复杂性

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).

Answer 2

两个代码的复杂性是O(n*n)

第一

外循环运行n时间,内循环随0 to n-1时间变化

所以

total = 1 + 2 + 3 + 4 ... + n

其中如果添加算术级数是n * ( n + 1 ) / 2被O(n*n)

第二

外循环运行n时间,内循环随0 to n-1/2时间变化

所以

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

如果你添加算术级数n * ( n + 1 ) / 4也是O(n*n)