算法图解-note
Opened this issue · 0 comments
ronghaoZHI commented
1 简介：
一般谈到复杂度较优的查找算法 都会想到介 -- 二分查找（tips: 所有的算法都用它的适用场景，遇到问题要先分析问题具体场景，否则方法再牛只是画蛇添足！ ）。
what is ‘二分查找’？
👇👇
/* 二分查找 */
function binarySearch(arr = [], item) {
let low = 0,
high = arr.length - 1;
while (low <= high) {
const mid = parseInt((low + high) / 2);
const guess = arr[mid];
if (guess === item) {
return mid;
}
if (guess > item) {
high = mid - 1;
}
if (guess < item) {
low = mid + 1;
}
}
return null;
}
const myList = [1, 3, 5, 7, 9];
console.log(binarySearch(myList, 3));
下面介绍1下，what is ‘大O’ ？
对，大O 一般用来表示算法复杂度（时间复杂度，空间复杂度）
下面列出常见的5种大O运行时间
👇👇
O(log n):也叫对数时间，这样的算法包括二分查找；
O(n):也叫线性时间，这样的算法包括简单查找；
O(n * log n): 这种算法包括快速排序 —— 一种速度较快的排序算法；
O(n²):这样的算法包括选择排序 —— 一种速度较慢的排序算法；
O(n!): 这样的算法包括难以解决的旅行商问题 —— 一种非常慢的算法。（旅行商问题 感兴趣的可以研究一下狄克斯拉特算法 Dijstra's algorithm）
2 数组&&链表
数组-- 在内存空间中地址始终是连续的（索引值与内存地址都是连续的），并且数组长度扩大时 会开辟一块新长度的内存空间，因此访问操作时效率较高，插入删除操作时效性能较差。
链表-- 在内存空间中地址可以间断，因此插入，删除操作时效率较高，访问操作时效率较低（因为需要从头进行遍历查找）。
链表和数组各种操作的时间复杂度对比
3 递归
递归由两部分组成：
- 基线条件（base case）：函数不再调用自己的条件
- 递归条件（recursive case）: 函数调用自己的条件
举个🌰，常见的递归算法
/*斐波纳契数列*/
function fib(n){
if(n<1) return
if (n <=2) {
return 1
} else {
return fib(n-1)*fib(n-2)
}
}
很明显此递归方法中-- 1. 结束条件 2. 调用自身
but...使用递归很方便，但是要付出代价：存储详尽的信息需要占用大量的内存。递归中函数会嵌套执行多层函数，每个函数调用都要占用一定的内存，如果栈很高，计算机就需要存储大量函数调用的信息，这就是为什么有的语言会限制递归最多的层数.
顺便开个小灶 —— 介绍下
尾调用优化
如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，
这将大大节省内存。这就是"尾调用优化"的意义。
通过变量保存函数运算结果，然后通过参数传递给下层递归函数，如果可以确切的知道下层函数需要从上层函数得到什么信息，则可把所有用到的内部变量改写成函数的参数，构成尾递归
4 快速排序
- 选择基准值
- 将数组分为两个子数组，小于基准值的元素和大于基准值的元素
- 对两个子数组再次运用快速排序
function quickSort(arr){
if(arr.length<=1) {
return arr;
}
let q = arr[0];
let left = [];
let right = [];
for(let i=1,len=arr.length;i<len;i++){
if(arr[i]<q){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return [].concat(quickSort(left), [q], quickSort(right));
}
var result = quickSort([1,5,7,90,55,4,2]);