java - for循环内while循环的时间复杂度

Question

我正在编写一个算法，需要找到其总和大于给定 k 参数的最小子数组的长度。

这是我到目前为止编写的函数:

    public static int smallestSub (int [] a, int k) {
        int currSum = a[0];
        int start = 0;
        int minLen = a.length + 1;
        int currLen = 1;
        
        for (int i = 1; i < a.length; i++) {
            currSum += a[i];
            currLen++;

            while (currSum - a[start] > k && start < i) {
                currSum -= a[start];
                start++;
                currLen--;
            }

            if (currSum > k) {
                minLen = Math.min(currLen, minLen);
            }
        }

        return minLen;
    }

我的问题是:这个算法的复杂度是O(n^2)吗？ 我问是因为 while 循环依赖于 for 循环。

Answer 1

is the complexity of this algorithm is O(n^2)?

不，不是。

首先，让我们注意 i来自1至n (我想 a.length 就是你所说的 n )。

内循环增量start直到达到i ，但它不会从 0 重新启动。因此，对于外循环的每次迭代，您都从某个 start' 开始。然后你达到了某个start'' (即最多为 i 的当前值)。请注意 start'等于 start'' 上一步。

让我们调用delta_i区别(start'' - start')_i ，即 i 的迭代次数-第一个内循环。

算法的成本是内部循环的总体迭代次数。这可以计算为:

Σ_(i=1)^n {delta_i} = delta_1 + ... + delta_n
                    = (start'' - start')_1 + ... + (start'' - start')_n
                    = start''_1 - start'_1 + ... + start''_n - start')_n
                    = -start'_1 + start''_n

最后一步是因为每start'_i等于下一个start'_(i+1) (例如 start''_1 = start'_2 )，因此可以简化它们。但是start'_1 = 0 ，所以我们最终得到 start''_n ，最多为 n .

因此，总复杂度为 O(n) .

Q.E.D.