這個問題在這里已經有了答案： 2 求和演算法解釋？ (2 個回答) 1 小時前關閉。
我想優化這段代碼的時間復雜度。現在，代碼具有 O(n^2) 復雜度。如何降低復雜性？輸入是未排序的陣列和目標，輸出是真或假。
這是我的代碼。
// pseudo code in js
function find(arr, target) {
for(let i = 0; i < arr.length; i ){
for(let j = i 1; j < arr.length; j ){
if(target === (arr[i] arr[j])){
return true;
}
}
}
return false;
}
我認為提示是unsorted陣列。而且我完全不知道..
uj5u.com熱心網友回復：
我不認為您的特定實作可以簡化，但是如果您首先對陣列進行排序，您可以采用雙指標方法來確定是否可以找到目標，從而導致O(n log n)復雜性。
function find(arr, target) {
arr.sort();
let start = 0;
let end = arr.length - 1;
while(start < end) {
if(arr[start] arr[end] > target) {
end--;
} else if(arr[start] arr[end] < target) {
start ;
} else {
return true;
}
}
return false;
}
uj5u.com熱心網友回復：
實際上你不需要對需要的陣列進行排序，O(nlogn)但你可以在linear runtime O(n n).
主意：
- 首先從陣列構建一個字典，以便稍后您可以及時搜索一個鍵
O(1)。 - 然后遍歷您的陣列并找出提醒是否在字典中，如果找到提醒就是答案。
例如：arr = [1, 5, 6]和target = 6；
所以當你0th就位時
let reminder = target - arr[0];
let reminder = 6 - 1 = 5
所以你只需要看看你的陣列有5沒有，這就是為什么你需要建立一個字典來查找O(1).
const find = (arr, dict, target) => { // then iterating through array which takes O(n)
let found = false;
arr.forEach((val) => {
const reminder = target - val; //just need to find out reminder is already in array or not
if (reminder in dict) {
found = true;
return;
}
});
return found;
}
const arr = [7, 3, 6, 2, 1];
const refDict = arr.reduce((currDict, val) => { //first create a dictionary which takes O(n)
return {
...currDict,
[val]: true
};
}, {});
const isFound = find(arr, refDict, 8);
console.log(isFound);希望能幫助到你！
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/526593.html
標籤：javascript算法
上一篇：回圈遍歷作業表并過濾VBA