java - 一个 for 循环中的两个 for 循环的运行时间复杂度

Question

我正在编写一个java方法来查找数组的稳定性指数。我的算法运行良好，但我不确定其运行时间复杂性。我相信它是 O(n)，因为第一个循环是 O(n)，两个内部循环是 O(2n)，但我再次不确定。

int[] arr = {0, -3, 5, -4, -2, 3, 1, 0};

for(int num = 0; num < arr.length; num++){
    int sumLeft= 0;
    int sumRight = 0;
    for(int i = 0; i<num; i++){
        sumLeft= sumLeft + arr[i];
    }
    for(int i = num + 1; i < arr.length;i++){
        sumRight= sumRight + arr[i];
    }
    if(sumLeft==sumRight){
        System.out.println(num);
    }
}

输出:

0
3
7

Answer 1

我们可以做两件事:

• 我们可以给您一个答案，答案是 O(N^2)。

• 我们可以解释如何自己解决。

解决这个问题的方法是计算操作数。

当我说“计数”时，我并不是字面意思。我实际上的意思是，您需要针对某些指示性执行操作的次数计算出一个代数公式。

因此，在您的示例中，我将确定这两个语句是最重要的:

      sumLeft= sumLeft + arr[i];

      sumRight= sumRight + arr[i];

(为什么我选择这些陈述？直觉/经验!执行此操作的迂腐方法是计算所有操作。但是凭借经验，您可以选择重要的那些......其余的都不重要。)

现在计算公式:

1. 在外循环的一次迭代中，第一条语句从0到num-1执行；即 num 次。

2. 在外循环的一次迭代中，第二条语句从 num+1 到 array.length - 1 执行；即 array.length - num - 1 次。

3. 因此，在外循环的一次迭代中，这两个语句被执行 num + array.length - num - 1 次，从而减少到 array.length - 1 次。

4. 但是外部循环运行 array.length 次。因此这两条语句被执行了 array.length x (array.length - 1) 次。

最后，根据 Big Oh 的定义，array.length x (array.length - 1) 属于复杂度类 O(N^2)，其中 N 是数组大小。