关于数据结构和算法:记一次看到的小心得数据结构和算法

学习数据结构和算法，肯定会在你的工作中派上用场

常常会感觉学习数据结构和算法没有什么大的用途，因为工作根本用不上。写完代码就丢了不去优化所以感觉算法没意义，又难又容易遗记。

例如下边代码：

data.filter(({id}) => {return selectedIds.includes(id);
})

逻辑就是筛选出 data 外面曾经被勾选的数据。当 200 条数据，齐全没压力，性能没影响。但当数据调到了 2 万条再去测试，代码弊病就裸露进去了，界面进入卡顿，从新抉择的时候也会卡顿。而后就开始了优化，思路如下：

依照代码来看，这是一个两层循环的暴力搜寻工夫复杂度为 O(n^2)。从 selectedIds.includes(id) 这句动手优化

扭转暴力搜寻的办法根本都是：

1. 上指针
2. 数组升维
3. 利用 hash 表

利用 hash 表思维解决这个问题，因为 js 外面有一个人造的 hash 表构造就是对象。咱们晓得 hash 表的查问是 O(1) 的，所以将代码改写如下：

const ids = {};
selectedIds.forEach(id => ids[id] = 1);

data.filter(({id}) => {return !!ids[id];
})

将从 selectedIds 查问变成从 ids 查问，这样工夫复杂度就从 O(n^2) 变成了 O(n) 了，这段代码减少了

const ids = {};
selectedIds.forEach(id => ids[id] = 1);

其实减少了一个 selectedIds 遍历也是一个 O(n) 的复杂度，总来说复杂度是 O(2n)，然而从工夫复杂度长期冀望来看还是一个 O(n) 的工夫复杂度，只不过额定减少了一个对象，所以这也是一个典型的空间换工夫的例子，然而也不要放心，ids 用完之后垃圾回收机制会把它回收的。