概述
查找
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。
顺序查找
将每一个数据结构中的元素和要查找的元素做比较，类似于JavaScript中indexOf
时间复杂度：O(n)
function sequenceSearch(arr, item) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === item) {
return i
}
}
return -1
}
二分查找
首先这个数组是排好序的，然后将数组一直二分缩小范围，直到找到为止。
时间复杂度：O(logN)
function binarySearch(arr, item, start, end) {
if (start > end) {
return -1
}
let mid = Math.floor((start + end) / 2)
if (item < arr[mid]) {
return binarySearch(arr, item, start, mid - 1)
} else if (item > arr[mid]) {
return binarySearch(arr, item, mid + 1, end)
} else {
return mid
}
}
非递归写法：
function binarySearch(arr, item) {
let start = 0
let end = arr.length - 1
let mid
while (start < end) {
mid = Math.floor((start + end) / 2)
if (arr[mid] === item) {
return mid
} else if (arr[mid] < item) {
start = mid + 1
} else {
end = mid - 1
}
}
return -1
}
递归
递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用。
递归算法解决问题的特点：
- 递归就是方法里调用自身。
- 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
- 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
递归函数与循环有很多类似之处，比如为了获得结果，反复执行同一代码块，且都有结束反复执行代码的终止条件。可以认为循环和递归函数是能够相互转换的。
区别在于，使用递归函数极少被迫修改任何一个变量（只需要将新值作为参数传递给下一次函数调用）。
斐波拉契数列
f(n) = f(n-1) + f(n-2)
递归的本质是把一个问题分解成两个或者多个小问题，如果多个小问题存在互相重叠的情况，那么就存在重复计算。
f(n) = f(n-1) + f(n-2)这种拆分使用递归是典型的存在重叠的情况，所以会造成非常多的重复计算。
另外，每一次函数调用，内存中都需要分配空间，每个进程的栈的容量是有限的，递归层次过多，就会造成栈溢出。
function Fibonacci(n) {
if (n < 2) {
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
增加缓存以避免重复计算：
function Fibonacci(n, cache = new Map()) {
if (n < 2) {
return n;
}
if(!cache.get(n)){
cache.set(n,Fibonacci(n - 1,cache) + Fibonacci(n - 2,cache))
}
return cache.get(n);
}
跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
假设 f(n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法。
每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。
- 第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。
- 第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。
所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。这里代码就省略了。
汉诺塔
现有三根柱子a、b、c，a 柱上套有若干个圆盘，这些圆盘大小各异，按从大到小的顺序自下而上摆放，如下图所示。
现在要把套在 a 柱子上的圆盘全部转移到 c 柱上，并且在移动圆盘时必须遵守以下规则：
- 一次只能移动柱子最上端的一个圆盘
- 小圆盘上不能放大圆盘
将一个圆盘从一根柱子移到另一根柱子，算移动“1次”，那么，将若干个圆盘全部从 a 移到 c 最少需要移动几次呢?
function hanoi(n, a, b, c, arr = []) {
if (n === 1) {
const step = a + '->' + c
arr.push(step)
} else {
hanoi(n - 1, a, c, b, arr) //将n-1个元素从a借助c, 移动到b
const step = a + '->' + c //再将剩下的一个盘移动到c
arr.push(step)
hanoi(n - 1, b, a, c, arr) //将n-1个元素从b借助a, 移动到c
}
return arr
}
console.log(hanoi(2, 'a', 'b', 'c'))
//[ 'a->b', 'a->c', 'b->c' ]
尾递归
尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步（不一定出现在函数尾部）是调用另一个函数。
函数调用自身，称为递归。如果尾调用自身，就称为尾递归。
//尾调用
function f(x){
return g(x);
}
// m和n都是尾调用
function f(x) {
if (x > 0) {
return m(x)
}
return n(x);
}
//不是尾调用
function f(x){
let y = g(x);
return y;
}
//不是尾调用
function f(x){
return g(x) + 1;
}
对于递归函数的使用，人们所关心的一个问题是栈空间的增长。确实，随着被调用次数的增加，某些种类的递归函数会线性地增加栈空间的使用。
不过，有一类函数，即尾部递归函数，不管递归有多深，栈的大小都保持不变。尾递归属于线性递归，更准确的说是线性递归的子集。
当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。
- 递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误（stack overflow）。
- 但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。
尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。
以阶乘为例，说明：
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5) // 120
改写为尾递归后：
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
空间复杂度从最多需要保存n个调用记录O(n)，直接变为只保留一个调用记录 O(1) 。
最后
以上就是标致小蚂蚁为你收集整理的js 解构递归数据_JS数据结构与算法之《查找与递归》的全部内容，希望文章能够帮你解决js 解构递归数据_JS数据结构与算法之《查找与递归》所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复