前端算法

预计,这是一篇需要长期更新的文章。想到啥就来补充吧。

合理使用更适合的算法可以提升代码执行效率,比如二分查找的效率更高。

前端常见的数据结构

  • 简单。
    • 有序数据结构。栈,队列,链表,有序数据结构省空间。
    • 无需数据结构。集合,字典,散列表。无需数据结构省时间。
  • 复杂。
    • 数,堆

简单数据结构对应js里就是 Object 和 Array

时间复杂度

  • 常数 o(1)
  • 对数 o(logN)
  • 线性 o(n)
  • 线性对数 o(nlogN)
  • 平方 立方 o(n^2) o(n^3)
  • 指数 o(2^n)
    小技巧,二重循环,就是 n^2。 有二分 logN 。 保留最高项。

举例分析算法复杂度

1
2
let i =0 //1
while(i<n){} //n

代码 1+n ,最终 O(n)

1
2
3
4
5
let num =1
while(num < n){
num*=2 // 增长速度 2^n 代码 logN
}
// 1+2*logN = O(logN)
1
2
3
4
for(){
for(){}
}
// n^2

基础算法

枚举和递归。

递归经典案例,js对象深拷贝。
递归容易造成爆栈,尾部调用可以解决递归问题。递归的爆栈问题可以通过把递归改成枚举,也就是 for while 代替递归

1
2
3
4
5
6
7
8
9
10
11
12
13
function deepClone(_empty, _target) {
for (let k in _target) {
if (typeof _target[k] === "object") {
_empty[k] = {};
deepClone(_empty[k], _target[k]);
} else {
_empty[k] = _target[k];
}
}
}

let tmp = Object.create(null)
deepClone(tmp,obj)

快排和二分查找

基于 分治思想。通过对数据分类处理,不断降低数量级,实现O(logN)

快速排序

随机选择数组a,以这个数为基准。
其他数组和这个数字比较,数字小的放左边,数字大的放右边
一次循环后,a左边是小于a的数,a右边是大于a的数
对左边和右边的数据再递归

二分查找

解决在一堆有序的数中找到指定的数。

  • 数组中排在中间的数字a,与要找的数字比大小
  • 因为数据是有序的,觉得从前后部分查找

二分查找logN

做题思路,找关键词: 有序的数列查找,要求算法复杂度 logN 一般就是二分思想

思路:

  1. 先降低数量级,拿可以计算出来的情况做解题步骤
  2. 有限把特殊情况处理
  3. 检验正确性
  4. 是否可以优化

    正则匹配

    比如一个字符出现的次数。可以for循环里使用 正则

1234567变成 1,234,567
算法可以,正则也可以。正则零宽断言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function exchange(num) {
num += ''; //转成字符串
if (num.length <= 3) {
return num;
}
num = num.replace(/\d{1,3}(?=(\d{3})+$)/g, (v) => {
console.log(v)
return v + ',';
});
return num;
}
console.log(exchange(1234567));


---

### 排序

https://segmentfault.com/a/1190000009426421

https://segmentfault.com/img/bVNIpc?w=554&h=337



数据结构与算法

https://juejin.im/entry/58759e79128fe1006b48cdfd

js递归

https://segmentfault.com/a/1190000009857470

波兰式,逆波兰式

请我喝杯咖啡吧~