假设 Below Node JS 具有 O(n*n) 的复杂度是否正确，即 O(N) Square for 2 For loops

Question

对于下面的代码，因为有 2 loops，所以说时间复杂度是 O(N) Square 是否正确，因为代码的形式是 do this (which is second for loop ) each time for each element in first loop，因此乘以运行次

理解正确吗？

            const arr = [{ key1: 2 }, { key1: 7 }, { key1: 11 }, { key1: 15 }];
            const k = 9;
            let valueSet = new Set(arr.flatMap((x) => Object.values(x)));
            let valueArray = [...valueSet];

            let indices;
            let isFound = false;
            // valueArray.forEach((v1, i1) => {
            for (let i1 = 0; i1 < valueArray.length && !isFound; i1++) {
              for (let i2 = i1 + 1; i2 < valueArray.length && !isFound; i2++) {
                if ((valueArray[i1] + valueArray[i2]) === k) {
                  //Return the Indices
                  indices = [i1, i2];
                  isFound = true;;
                }
              }
            }
            console.log(indices);

此致，

卡罗琳

Answer 1

是的，你是对的。通常，代码的双 for 循环结构会产生 O(n^2) 时间复杂度，前提是您只在内部 for 循环的主体内进行持续工作，在这种情况下，您只执行一张支票，可能还有一些作业。

O(n^2) 的复杂性来自这样一个事实，即您在第一个内部 for 循环中有效地执行了 n-1 个检查，在第二个内部循环中有效地执行了 n-2 个...在最后一个中执行了 1 个，而从 1 到 n-1 的总和是 O(n^2):

这当然是最坏情况的复杂性，你查看每一对值，没有找到任何对和为 k，但通常这是你在做大 O 时要分析的最坏情况。

从另一个角度来看复杂性，您正在生成所有可能的索引对，其中第二个索引大于第一个索引，并为每一对做持续的工作。有 n(n-1)/2 个这样的可能对，因为您对第一个索引有 n 个选择，对第二个索引有 n-1 个选择，但只有一半生成的对的第一个索引小于第二个索引，因此您需要除以二，产生与总和完全相同的 n(n-1)/2 值。

至于你最初用“乘运行次”来表达整体复杂性的方式，这也是正确的，但你必须要小心一点，因为内循环运行-时间根据您所在的外循环的迭代而变化。但是，您可以说您将外循环的运行-时间 n 乘以 内循环的平均运行-时间。内部循环运行-time 的范围统一从 1 到 n-1，所以这意味着运行-time 是 1/2(n-1)，给我们相同的 n(n-1)/ 2 = O(n^2) 整体运行时间。

假设 Below Node JS 具有 O(n*n) 的复杂度是否正确，即 O(N) Square for 2 For loops

Is it correct to assume Below Node JS has the Complexity O(n*n) i.e. O(N) Square for 2 For loops

time-complexity

node.js

data-structures

npm

ecmascript-6