查找
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。
顺序查找
将每一个数据结构中的元素和要查找的元素做比较，类似于JavaScript中indexOf
时间复杂度：O(n)
1
2
3
4
5
6
7
8
9function sequenceSearch(arr, item) { for (let i = 0; i < arr.length; i++) { if (arr[i] === item) { return i } } return -1 }
二分查找
首先这个数组是排好序的，然后将数组一直二分缩小范围，直到找到为止。
时间复杂度：O(logN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function 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 } }
非递归写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function 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)这种拆分使用递归是典型的存在重叠的情况，所以会造成非常多的重复计算。
另外，每一次函数调用，内存中都需要分配空间，每个进程的栈的容量是有限的，递归层次过多，就会造成栈溢出。
1
2
3
4
5
6
7function Fibonacci(n) { if (n < 2) { return n; } return Fibonacci(n - 1) + Fibonacci(n - 2); }
增加缓存以避免重复计算：
1
2
3
4
5
6
7
8
9
10function 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 最少需要移动几次呢?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function 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' ]
尾递归
尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步（不一定出现在函数尾部）是调用另一个函数。
函数调用自身，称为递归。如果尾调用自身，就称为尾递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//尾调用 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）。
- 但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。
尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。
以阶乘为例，说明：
1
2
3
4
5
6
7function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1); } factorial(5) // 120
改写为尾递归后：
1
2
3
4
5
6
7function 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内容请搜索靠谱客的其他文章。
发表评论 取消回复