對于下面的代碼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);
問候，
卡羅琳
uj5u.com熱心網友回復：
你是對的。一般來說，代碼的雙 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 乘以內回圈的平均運行時間。內回圈運行時間統一從 1 到 n-1，所以它的平均運行時間是 1/2(n-1)，給我們相同的 n(n-1)/2 = O(n^2)整體運行時間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/378846.html
標籤：节点.js 新产品经理 数据结构 ecmascript-6 时间复杂度
下一篇：Npm和Json檔案的問題