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.

for循环内部while循环的时间复杂度

Time complexity of while loop inside for loop

java

time-complexity