算法相关

[goldEli]

计算机程序通常是由数据结构+算法组成的。

知识点总览：

• 常见数据结构
  • 栈、队列、链表
  • 集合、字典、散列集
• 常见算法
  • 递归
  • 排序
  • 枚举
• 算法复杂度分析
• 算法思维
  • 分治
  • 贪心
  • 动态规划
• 高级算法结构
  • 树、图
  • 深度优先、广度优先

数据结构

数据结构决定了空间和时间的处理效率，根据不同的场景确定不同的数据结构。

读的多的数据，要想竟可能想办法提高读取效率，比如IP 的数据储存，他可能只会写一次，而读取很多次。

常见的数据结构

• 简单数据结构
  • 有序数据结构：栈、队列、链表 （占用空间小）
  • 无序数据结构：集合、字典、散列集 （查询熟读快）
• 复杂数据结构
  • 树、堆
  • 图

有序数据结构比如数组存储，节省空间，但查找慢。用无序数据结构比如对象存储，用 key 就可以快速查找到。

对于简单的数据结构，在 ES 中对应的是 Array 和 Object。可以想象下数组是有序的而对象是无序的，对象可以通过 key快速获取值，而数组则有个查找过程。

算法

算法分为时间复杂度和空间复杂度。

时间复杂度指的是算法运行的时间，空间复杂度指的是算法运行所需的储存空间。

算法的复杂度

一般遵循这几个原则：

1. 一重循环 O(n)，两重循环 O(n^2)，一次类推。
2. 如果是二分法，复杂度为 O(log(n))。
3. 去除常数，保留最大值。

举个例子：

var i = 0;                   // 这条语句执行1次
while(i < n) {             // 这条语句执行n次
    console.log(i);      // 这条语句执行n次
    ++i;                      // 这条语句执行n次
}

算法复杂度计算：1 + n + n + n = 1 + 3n，去除常数项，复杂度为 O(n)