java - Java 代码复杂度

Question

int n=3;
int sum = 0;  
for (int i = 0; i < n; i++) {  
    for (int j = n - 1; j >= i; j = j - 2) {  
        sum = i + j;  
        System.out.println(sum);  
    }  
}

我一直试图找出这段代码的复杂性（O（？）等）
有什么想法吗？

Answer 1

我将解释只是为了澄清我自己的理解。第一个循环运行n时间。现在，让我们讨论一下内循环。

第一次迭代，它将运行 fromn-1到0inclusive，增量为 2，导致n/2迭代。第二次迭代，它将运行从n-1到1包含，增量为2，导致(n-1)/2迭代。以此类推，最后一次迭代将是 fromn-1到n-1inclusive，这将是1迭代。

计算所有迭代，它将是[n/2 + (n-1)/2 + .... 1] ≈ n2

Answer 2

嗯，常数，对于固定的 n... :-) 但是如果你想要 n 的复杂性，它是 O(n^2) - 如果内部循环从 n 变为 0，它将是 o(n^2)，但事实上，我们只通过在 i 结束（想象一个正方形；j >= i 的区域是一个三角形）将时间减少一半，然后通过将 j 步长 2 来减少另一半，这只是一个常数乘法因子 1/4（IOW 不改变渐近复杂度）。