算法

复杂度

• 数组，单循环遍历：O(n)时间复杂度
  • 如果只用到i，是常数级空间复杂度O(1)
  • 如果用到额外空间，比如一个对象当做字典保存数据，空间复杂度就是O(n)
• 数组，双循环遍历：O(n^2)时间复杂度，用到i、j，是常数级空间复杂度O(1)
• 从数组里，找到第1000个元素，时间复杂度是O(1)，相当于字典直接查
• 从数组里，找到值为1000的索引，时间复杂度是O(n)，需要遍历
• 从对象中，找到key为a的值，时间复杂度是O(1)，相当于字典直接查
• 数组，新增和删除数据的时间复杂度是多少？O(n)
  • 先要位移，再增删：[1,2,3,4] => [1,2,,3,4] => [1,2,3,4,5]
• 链表，新增和删除数据的时间复杂度是多少？O(1)
  • 只需要先断链，直接增加：1-2-3-4 => 1-2 3-4 => 1-2-5-3-4
• 链表，查找元素，复杂度是O(n)
  • 需要遍历

react的fiber架构，就是存储的虚拟dom，从树变成了链表 vue内部的keep-alive，缓存算法LRU，也是用的链表 链表+数组，组成了其他所有的数据结构

回溯：不停地试探。放一下，尝试一个结果，再撤销，走下一步。