几种复杂度的函数形式

常数O(1)
线性O(N)
对数O(log(n))
指数O(n^2)
级数

问题分类

P问题
在确定计算机设备上，可在多项式时间内求解问题

NP问题
NP(Nondeterministic Polynomially，非确定性多项式)类问题是指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。

数学基础-分治

分而治之，是各类算法的基础思想 - 将问题不断划分为更小的单位。直到问题规模可被求解，然后再将问题的结果合并起来

递归

函数在没有执行完成之前，可以再次被调用
经典：斐波那契数列

  1. const arr = [];
  2. for(let i = 0; i < 10000; i ++){
  3.   arr.push(i);
  4. }
  6. // 二分法 一定是有序数组 递归调用
  7. function findIndex(arr, value, start, end) {
  8.   if (start > end) return -1;
  9.   let center = Math.floor((start+end) /2);
  10.   if(value === arr[center]) { 
  11.     return center;
  12.   } else if(value < arr[center]) {
  13.     return findIndex(arr, value, start, center -1);
  14.   } else {
  15.     return findIndex(arr, value,  center + 1, end);
  16.   }
  17. }
  19. console.log(findIndex(arr, 2838838, 0, arr.length -1));

语言基础

ADT
抽象数据类型，类似ts范型

指针
计算机中，数据类型分为2种
基本类型：变量直接存储数据本身，例如：数字 字符串
引用类型：变量直接不存储数据本身，而存储数据所在的内存地址，这种变量为 - 指针变量

ts/js中数据的结构与算法

高级语言中，大量的数据结构都是现成的：

  • Array 很好的实现了 sort、stack、queue操作
  • Object/Json很好的实现了map 操作
  • Set