1.遞回二分查找（回傳目標位置）
function recursiveBinarySearch(list, target) {
const binarySearchHelper = (list, target, left, right) => {
let mid = Math.floor((left right) / 2);
//not found
if (left > right) {
return -1;
}
if (list[mid] === target) {
return mid;
} else if (list[mid] > target) {
return binarySearchHelper(list, target, left, mid - 1);
} else if (list[mid] < target) {
return binarySearchHelper(list, target, mid 1, right);
}
};
return binarySearchHelper(list, target, 0, list.length - 1);
}
2.遞回二分查找（不回傳目標位置，只有布林值）
function recursiveBinarySearch(list, target) {
const binarySearchHelper = (list, target) => {
let mid = Math.floor((list.length - 1) / 2);
//not found
if (list.length <= 0) {
return false;
}
//found or recursive
if (list[mid] === target) {
return true;
} else if (list[mid] < target) {
return binarySearchHelper(list.slice(mid 1), target);
} else if (list[mid] > target) {
return binarySearchHelper(list.slice(0, mid), target);
}
};
return binarySearchHelper(list, target);
}
我很難理解空間復雜性。
這兩種演算法的空間復雜度是多少？
我認為 2具有O(log n)的空間復雜度，因為在遞回二進制搜索的每個函式呼叫中，它都會創建一個新的 size 串列，......等等（如果我錯了，請糾正我）。1.recursive binary search（回傳目標位置）怎么樣？n/2n/4
uj5u.com熱心網友回復：
不，空間復雜度不同（忽略初始陣列的 O(n) 記憶體）
第一個演算法的空間復雜度為 O(log n)。您有 log n 個步驟，并且在每個步驟中您需要恒定數量的變數
第二種演算法的空間復雜度為 O(n)。創建大小為 n/2 的第一個副本已經具有 O(n) 的空間復雜度。您有記錄 n 步。步驟 1 需要 n/2 記憶體，步驟 2 需要 n/4，步驟 3 需要 n/8，... n/2 n/4 n/8 ... <= n 仍然是 O(n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/425422.html
標籤：javascript 算法 递归 二分搜索 空间复杂性
上一篇：從陣列中獲取5個最舊的物件
下一篇：用鍵和另一個值陣列按陣列分組