javascript - 如果我在 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

虽然 for和其他循环结构可能会提供一些关于复杂性的基本指南，分析必须始终考虑迭代次数，而不是依赖于计算嵌套循环的数量。可以很容易地证明，任意数量的嵌套循环仍然会导致线性或恒定的时间复杂度(即 while (true) { break; })。
对于您提到的功能，sumArray和 maxResult运行 n迭代，其中 n匹配输入数组元素的计数。
对于 subArraySum然而，复杂性并没有那么简单。我们可以很容易地看到，该函数同时调用了 sumArray和 maxResult ，然而，尚不清楚这些调用与函数输入之间的关系。
调用 subArraySum对于一些数组 arr长度m和 n 的参数，我们可以看到 for循环从 n - 1 运行至 m ，即 m - n + 1次，或在复杂性方面，循环运行计数是 O(m - n + 1) 的函数= O(m - n) .出于渐近分析的目的，常数 1 被认为是微不足道的(想象一下 109 和 109 + 1 操作之间的差异 - 可能没有那么多)。
然后每个循环创建一个长度为 n - 1 的子数组.这是基于 i和 j迭代变量 - 我可能在这里错了，但我怀疑实现是错误的。无论如何，这使得 O(n)手术。
然后通过 sumArray 对切片求和(如前所述 O(n) 的复杂性)并插入到另一个数组的后面(摊销 O(1) )。
因此，每次循环运行的复杂度为 O(n) .
随着循环运行 O(m - n)次，复杂度为 O(n) ，产生的总复杂度为 O(n * (m - n)) = O(m * n - n^2) .
现在让我们考虑这个术语，m * n - n2。从函数的语义，我们可以假设，它必须始终保持 n < m(对于 n = m，复杂性是恒定的:m * n - n2 = n2 - n2 = 0 - 你可以通过精神上的经历来确认这一点算法，它只会返回 0 而没有任何循环)。如果 n 始终小于 m，则 n2 将始终小于 m * n，因此可以忽略。
我们到达 O(mn)为循环。
最后，maxResult为 O(m - n) 的和数组调用long (请记住，我们通过运行 O(m - n) 迭代来创建数组，每次向数组添加一个数字)。这给了我们 O(m - n) maxResult 的复杂性称呼。
复杂性 O(mn) + O(m - n) ，我们可以再次应用 n < m 并看到第二项总是产生比第一项小的值，因此可以认为对分析来说是微不足道的。
所以我们得出结果，算法的时间复杂度为O(mn)哪里m是输入数组的长度，n是子数组的长度。