内存工作原理

你请求计算机提供存储空间，计算机给你一个存储地址。计算机需要存储多项数据时，有两种基本方式——数组和链表。

链表

链表中的素材可存储在内存中的任何地方。
链表的每个元素都存储了在下一个元素的地址，从而使一系列随机内存地址串在一起。
链表的优势：插入、删除元素（可存储在内存中的任何地方）。
链表的劣势：读取元素，在需要同时读取所有元素时，链表效率很高，如果需要跳跃读取效率就很低。

数组

数组的优势：随机读取数据效率很高。

读取

读取最后一个元素
数组：O(1)
链表：O(n)

插入

在第一个元素前插入元素
数组：O(n)
链表：O(1)

删除

如果你要删除元素
链表：O(1)
数组：O(n)

选择排序 O(n2)

原理：每次遍历查找到最大数，直到最后一个。
O(n2) = O(n 1/2(n+1))
大O表示法可以省略常量，因为它表示的是算法运行时间的增速。

递归

基线条件

停止调用的条件

递归条件

继续调用的条件

栈

调用栈就像贴便条一样

  1. function printUserInfo(){
  2.    let name = 'lucky'
  3.    let age = '20'
  4.      printName(name)
  5.    printAge(age)
  6. }
  8. function printName(name){
  9.     console.log(name);
  10. }
  12. function printAge(age){
  13.     console.log(age);
  14. }

在调用printUserInfo时，计算机为该函数调用分配一块内存（一个栈表示一个内存块）。
调用printName时，计算机分配了一个栈，并将这个栈堆在printUserInfo对应栈上，直到printName执行完成之后，printName对应的栈会被弹出。
调用printAge时，同上。
直到执行完printUserInfo，这个栈就用于存储多个函数的变量。

如果使用递归时，没有触发基线条件，就会堆栈溢出。

快速排序

分而治之

分而治之（divide and conquer，D&C）——著名的递归时问题解决方法。
假设你是农场主，有一块小土地，你要将这块地均匀的分成方块，且分出的方块要尽可能的大。
这个问题就很适合D&C解决问题
1.找出基线条件，要尽可能简单。
2.不断将问题分解，直到符合基线条件。
一块1680640的地，可以分成 640 640 +640 640 +400640
余下一块非正方形，我们可以继续使用同样的方法分割，
直到余下的方块为正方形，这个正方形就最大的能均匀分割这块地的方块。（欧几里得算法）
结果为80*80。

快速排序

基本原理：
1.选取基准值
2.将数组分成两个子数组（小于基准值的元素的数组 和 大于基准值的元素的数组 ）
3.再这两个数组快速排序

  1. let quickSort = function(arr) {
  3.       //基线条件为数组长度小于等于1
  4. 　　if (arr.length <= 1) { return arr; }
  6. 　　let pivotIndex = Math.floor(arr.length / 2);
  8. 　　let pivot = arr.splice(pivotIndex, 1)[0];//选择基准值
  10. 　　let left = [];
  12. 　　let right = [];
  14. 　　for (let i = 0; i < arr.length; i++){
  15.          //与基准值比较，小则放入left数组，大则放入right数组
  17. 　　　　if (arr[i] < pivot) {
  19. 　　　　　　left.push(arr[i]);
  21. 　　　　} else {
  23. 　　　　　　right.push(arr[i]);
  25. 　　　　}
  27. 　　}
  29.       //concat quickSort所有返回的值
  30. 　　return quickSort(left).concat([pivot], quickSort(right));
  32. };

大O表达式：O(log)
扩展：快速排序和合并排序区别

散列表

js中对象/数组就是散列表

散列函数

定义：无论你给它什么数据，它都还你一个数字。

应用

1.模拟映射关系，用于查找
2.防止重复
3.缓存/记住数据，以免服务器在通过处理来声称它们（通过路由）

冲突

在js中我们很少遇到这种情况。
在其他语言中，数组长度是固定的情况下，数组长度为26位分别表示26个字母，要将两个首字母为a的元素存入第一个位置时，就会发生冲突。两个key值对应的是后存入的值。
这种情况下可以使用链表查询，第一个位置存储的是先存入的值，通过链表查询第二个值。
但是如果遇到只有首字母为a元素，那么这么存储并不能发挥散列表的优势。

性能

如何避免冲突
较低的填装因子
良好的散列函数

填装因子

定义：散列表中还有多少位置是空的。 （散列表包含的元素数/位置总数）

良好的散列表

呈均匀分布。