确定 Java 中的时间复杂度

Question

public class complexity {
    
    public int calc(int n) {
        int a = 2 * Math.abs(n);
        int b = Math.abs(n) - a;
        int result = n;
        for (int i = 0; i < a; i++) {
            result += i;
            for (int j = 0; j > b; j--) {
                result -= j;
            }
            for (int j = a/2; j > 1 ; j/=2) {
                System.out.println(j);
            }
        }
        int tmp = result;
        while (tmp > 0) {
            result += tmp;
            tmp--;
        }
        return result;
    }
    
    
}

我在 Java 中得到了以下程序，需要确定时间复杂度 (Tw(n))。

我检查了那些网站：

Big O, how do you calculate/approximate it? How to find time complexity of an algorithm

但是我还是有点理解不了。

这是 professor.From for 循环给出的解决方案我不明白他是如何想出不同的时间复杂度的。谁能解释一下？

Answer 1

我愿意澄清一下，即最后一个 while 循环。不幸的是，我的回答与教授的不符。而且我不肯定没有犯过严重的错误。

result starts with n 

for i from 0 upto 2|n|
    result += i

2|n|完成次数，平均 i.|n|所以结果增加了：~2n.n = 2n².

    for j from 0 downto -|n|
        result -= j

2|n|完成次数，结果增加：2n.n/2 = n²

所以结果是 n + 3n²

外部 for 循环仍然是 O(n²)，因为内部 println-for 只有 O(log n)。

最后一个 while 循环与：

for tmp from n + 3n² downto 0
    result += tmp

这和外层的for循环一样也是O(n²)，所以整个复杂度是O(n²).

result大概是3n².3n²/2 或者。 4.n⁴.

Answer 2

让我们一步步过一遍：

在for循环之前，每条指令都在恒定时间内执行

然后：

for(int i = 0; i < a; i++) 被执行 2n + 1 次 a = 2*n 所以 0=> a = 2n 步骤和附加步骤是当 i = 2n 时程序必须执行该步骤，当它发现 i = 2n 时它会跳出循环。

现在循环中的每条指令都必须执行 2n 次（因为我们从 0 循环到 2n - 1）这解释了为什么 result += i 执行了 2n 次。

下一条指令是另一个 for 循环，因此我们对该行应用相同的逻辑 for (int j = 0; j > b; j--) ：因为 b = -n 这条指令将从 0 下降到 -n 加上我在第一个 for 循环中提到的额外步骤，这意味着：0 -> -n => n steps + 1 = n+1 steps 并且由于这条指令在另一个循环中，它将被执行 2n 次因此 2n * (n+1)

这个 for 循环中的指令执行了 n 次，因此 result -= j 执行了 n 次，而循环本身执行了 2n 次 (result -= j) 将执行 n*2n 次

最后一个 for 循环也是如此，除了这里我们从 a/2 开始，即 n 作为 a = 2n 到 1，每次我们除以 2，这有点复杂，所以让我们做一些步骤首先迭代 j = n 然后 j = n/2 然后 j = n/4 直到 j <= 1 那么我们需要多少步才能达到 1 ？要达到 n/2，我们需要 1 = log(2) 步骤 n => n/2
要达到 n/4，我们需要 2 2 = log(4) 步 n => n/2 => n/4 我们在这里指出，要达到 n/x，我们需要 log(x) 步，而 1 = n/n 我们需要 log(n) 步才能达到 1 因此，此循环中的每条指令都执行了 log(n) 次，并且由于在父循环中，它必须执行 2n 次 => 2n*log(n) 次。

对于 while 循环：结果 = n + (0 + 1 + 2 + .. + 2n) + (0 + 1 + .. + 2(n^2)) 我们在 for 循环中做了这个，然后你做它给出的算术序列总和结果 = n^2 (n+1) 给你。

我希望这是清楚的，否则请不要犹豫！

确定 Java 中的时间复杂度

determine the time complexity in Java

time-complexity