如果我在 for 循环中调用一个包含 for 循环的函数，那是 O(n^2) 时间还是 O(n)？

Question

subArraySum 中的 for 循环调用 sumArray，它也包含一个 for 循环。这会被认为是 O(n^2) 时间吗？对我放轻松，因为这是我的第一个问题，正如您从我的代码中看到的那样，我是初学者。这是我的代码：

const subArraySum = (arr,n) => {
    let i = 0;
    let result = [];
    for (let j = n-1;j<arr.length;j++) {
        let li = arr.slice(i,j+1);
        result.push(sumArray(li));
        i++;
    }
    return maxResult(result);
}

function sumArray(li) {
    counter = 0;
    for (let k of li) {
        counter+=k;
    }
    return counter;
}

function maxResult(result) {
    let highest = 0;
    for (let k of result) {
        if (k>highest) {
            highest = k;
        }
    }
    return highest;
}

Answer 1

是的，这使其成为 O(n^2)，因为复杂性适用于整个算法，无论它如何拆分为函数。将一些代码移出到命名函数不会改变整体运行时间或它如何依赖于输入。

有时我们在调用语言的built-in函数或OS时可能会把它们当作复杂度未知的黑盒子，所以为了计算复杂度我们可能会忽略它们我们自己的算法。但是您通常不能忽视构成算法一部分的您自己的函数的复杂性，因为如果有更有效的方法，您可以选择重新设计它们。

Answer 2

虽然 for 和其他循环结构可能会提供一些关于复杂性的基本指南，但分析必须始终考虑迭代次数，而不是依赖于计算嵌套循环的次数。可以很容易地证明，任意数量的嵌套循环仍然可以导致线性或常数时间复杂度（即 while (true) { break; }）。

对于您提到的函数，sumArray 和 maxResult 运行 n 迭代，其中 n 匹配输入数组元素的计数。

然而，对于 subArraySum，复杂性并不那么微不足道。我们可以很容易地看到，该函数调用了 sumArray 和 maxResult，但是，这些调用与函数输入的关系并不十分清楚。

要为长度为 m 且参数为 n 的某个数组 arr 调用 subArraySum，我们可以看到 for 循环运行s 从 n - 1 到 m，即 m - n + 1 次，或者在复杂度方面，循环运行计数是 O(m - n + 1) = [ 的函数=28=]。出于渐近分析的目的，常数 1 被认为是微不足道的（想象一下 10⁹ 和 10⁹ + 1 操作之间的差异 - 可能不是那么多).

然后每个循环生成一个 sub-array 长度 n - 1。这是基于 i 和 j 迭代变量 - 我在这里可能是错的，但我怀疑实现是。无论如何，这会进行 O(n) 操作。

切片然后通过 sumArray 求和（O(n) 的复杂性，如前所述）并插入到另一个数组的后面（分摊 O(1)）。

因此，每个运行循环的复杂度为O(n)。

由于循环运行s O(m - n) 次，复杂度为 O(n)，总复杂度为 O(n * (m - n)) = O(m * n - n^2).

现在让我们考虑这一项，m * n - n²。从函数的语义来看，我们可以假设，它必须始终满足 n < m（复杂度对于 n = m: m * n - n ² = n² - n² = 0 - 你可以通过在脑子里遍历算法来确认这一点，它只是 return 0 而没有任何循环）。如果n总是小于m，那么n² 将始终小于 m * n 因此可以忽略。

我们到达 O(mn) 循环。

最后，为 O(m - n) 长的总和数组调用 maxResult（请记住，我们通过运行ning O(m - n) 次迭代创建数组，每个都向数组中添加一个数字）。这给了我们 O(m - n) 调用 maxResult 的复杂性。

复杂度 O(mn) + O(m - n)，我们可以再次应用 n < m 并查看第二项总是比第一项产生更小的值，因此对于分析来说可以认为是微不足道的。

所以我们得出结果，算法的时间复杂度为O(mn)，其中m是输入数组的长度，n是sub-arrays.

Answer 3

这完全取决于您在每个 for 循环中使用的方法。

让我们举个简单的例子：-

如果你正在使用一个线性递增的 for 循环（不断递增直到条件起作用）并且在它内部（在主体中）有一个调用函数，它的主体中还有另一个线性 for 循环。

所以，时间复杂度是O(n^2)。第二个for循环将通过第一个for循环的每次迭代对函数的每次调用迭代n。但这完全取决于你对这两个 for 循环有什么样的增量方法和条件（任何）。

如果我在 for 循环中调用一个包含 for 循环的函数，那是 O(n^2) 时间还是 O(n)？

If I call a function that contains a for loop inside a for loop, is that considered O(n^2) time or O(n)?

javascript

performance

time-complexity