数据结构

本章主要学习基础算法,数据结构和复杂度.
参考至web全栈体系

复杂度

衡量算法的优劣，一般通过耗费的时间资源和空间(内存)资源.
复杂度分为时间复杂度和空间复杂度。
复杂度一般由O()表示，内部的值越大，表示复杂度越高。

时间复杂度

表示运行算法所花费的时间，因变量的变化而增加的复杂度规律(数量级)。

O(1)

常数级别的时间复杂度

const a = 1;
console.log(a);
// 表示当变量没有变化

O(n)

自然数级别的时间复杂度

const n = 20;
for(let i=0; i<n; i++){
	// ...
}
// n的变化，会导致程序执行时间一起变化，呈自然数变化的规律。

O(n^2)

指数级别的时间复杂度

const n = 20;
for(let i=0; i<n; i++){
	for(let j=0; j<n; j++){
		// ...
	}
}

// 嵌套了2层循环，
// n的变化，会导致执行时间呈指数级别递增，
// 呈现指数级变化的规律。

O(log2n)

对数级别的时间复杂度
在O(n)和O(n2)案例上，都是变量i++执行循环。
当基本变化规律不是增减, 而是乘数变化时, 就是对数级别数量级

for(let i=0; i<n; i *= 2){
	// ...
}
// 由于i++ 变为了 i*=2
// 其总的时间复杂度由 O(n) 缩减为了 O(log2n)

计算步骤

计算时间复杂度的步骤：

找到执行次数最多的语句
计算语句执行次数的数量级
用大O来表示结果

let num = 0, num2 = 0;
for(let i=0; i<n; i *= 2){
	num +=1;
	for(let j=0; j<n; j++){
		// ...
		num2 +=1
	}
}

// 执行最多的是内部的num2 +=1
// 执行的数量级为 nlog2n
// 时间复杂度为 O(nlog2n)

计算规则

当n无限趋近于无穷时，1/n趋向于0.
加法规则: 当两个时间复杂度处于同级，相加时取较大值
乘法规则: 当两个时间复杂度处于嵌套级，量级相乘
只有可运行的语句，才会增加时间复杂度。

for (let i=1; i<=n; i++){
	for (let j=1; j<=n; j++){
		console.log(1);
	}
}
// 以上的时间复杂度为  O(n2)

for(let x=1; x<n; x++){
	console.log(1);
}
// 以上的时间复杂度为O(n)

// 因此，总的时间复杂度为 O(n+n2) =>O(max(n,n2)) => O(n2)

空间复杂度

表示运行算法所占用的空间，因变量的变化而增加的复杂度规律(数量级)。

O(1)

常数级别，即变量变化并没有导致程序占用的空间发生变化。

const a =10;
for(let i=0; i<n; i++){
	console.log(n)
}
for(let i=0; i<n; i++){
	for(let j=0; j<n; j++){
		console.log(n)
	}
}
// 以上3个, 空间复杂度均未为O(1)

O(n)

自然数级别，即变量变化会导致程序占用的空间递增。
内存占用变化的规则呈自然数级现象。

const arr = []
for(let i=0; i<n; i++){
	arr.push(i);
}
// 当i发生变化时，arr占用不断增大，并且与i的自然递增，有强相关。

O(n^2)

指数级别, 内存占用变化的规则呈指数级现象。

const arr = []
for(let i=0; i<n; i++){
	arr[i] = i;
	for(let j=0; j<n; j++){
		arr[i][j] = i + j;
	}
}

// 当嵌套到j层时，外部的arr[i] = i; 呈n级别递增，
// 内部的arr[i][j] = i + j; 也呈n级别递增
// 因此一共是 n * n, 也就是O(n2)

O(log2n)

对数级别, 与时间复杂度的O(log2n)一样
当基本变化规律不是增减, 而是乘数变化时,

const arr = []
for(let i=0; i<n;i*=2){
	arr[i] = i
}

额外补充

时间和空间复杂度往往是相互影响的, 当一味的追究时间复杂度
可能消耗更多的内存.

数据结构

栈

栈是指: 按一种先进后出的原则存储数据.
想象一个瓶子装石头,往往先装入的,只有最后才能取出.
栈和队列在js中,经常用数组模拟

// 用数组模拟栈
class Stack{
	constructor(){
		this.arr = []
	}
	addData(...data){
		this.arr.push(...data)
	}
	delData(){
		this.arr.pop()
	}
}

const stack = new Stack()
stack.addData(1,2,3,4,5)  //按 顺序挤入, 5最后挤入
stack.delData() //5被删除
console.log(stack.arr); //1,2,3,4

队列

队列是指: 按一种先进先出的原则存储数据.
想象一个漏斗, 往里面倒入石头, 先倒入的先流出.

// 用数组模拟队列
class Queue{
	constructor(){
		this.arr = []
	}
	addData(...data){
		this.arr.push(...data)
	}
	delData(){
		this.arr.shift()
	}
}
const queue = new Queue()
queue.addData(1,2,3,4,5);  //1最先挤入
queue.delData(); //1被删除了
console.log(queue.arr);  //2,3,4,5

链表

链表由一系列节点和指向下一个节点的指针组成。
优点：可以动态且快速的增加和删除节点。
缺点：由于链表的顺序由指针决定，是非连续的。
因此访问第i个元素需要遍历整个链表，效率较低。

// 用原生js实现链表
// 定义链表的节点类
class Node {
  constructor(value) {
    this.value = value;  //值
    this.next = null;  //指向下一个节点的指针(引用)
  }
}

// 定义链表类
class LinkedList {
  constructor() {
    this.head = null; //头部指针
    this.tail = null;  //尾部指针
    this.length = 0;  //链表长度
  }

  // 在链表尾部添加节点 就是更改指针/引用即可。
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // 在链表指定位置插入节点, 时间复杂度为O(1)
  insert(position, value) {
    if (position < 0 || position > this.length) {
      return false;
    }
    const newNode = new Node(value);
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
      if (!this.tail) {
        this.tail = newNode;
      }
    } else if (position === this.length) {
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      let current = this.head;
      let previous = null;
      let index = 0;
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = newNode;
      newNode.next = current;
    }
    this.length++;
    return true;
  }

  // 根据值查找节点位置, 时间复杂度为O(n)
  indexOf(value) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

  // 根据位置删除节点, 时间复杂度为O(1)
  removeAt(position) {
    if (position < 0 || position >= this.length) {
      return null;
    }
    let current = this.head;
    if (position === 0) {
      this.head = current.next;
      if (this.length === 1) {
        this.tail = null;
      }
    } else {
      let previous = null;
      let index = 0;
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = current.next;
      if (position === this.length - 1) {
        this.tail = previous;
      }
    }
    this.length--;
    return current.value;
  }

  // 根据值删除节点
  remove(value) {
    const position = this.indexOf(value);
    return this.removeAt(position);
  }

  // 判断链表是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 返回链表长度
  size() {
    return this.length;
  }

  // 返回链表头部节点的值
  getHead() {
    return this.head ? this.head.value : null;
  }

  // 返回链表尾部节点的值
  getTail() {
    return this.tail ? this.tail.value : null;
  }

  // 将链表转换为数组
  toArray() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }

  // 将链表转换为字符串
  toString() {
    return this.toArray().toString();
  }
}

// 测试代码
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.insert(1, 4);
console.log(list.toArray()); // [1, 4, 2, 3]
console.log(list.indexOf(2)); // 2
console.log(list.remove(4)); // 4
console.log(list.toArray()); // [1, 2, 3]
console.log(list.size()); // 3
console.log(list.getHead()); // 1
console.log(list.getTail()); // 3
console.log(list.toString()); // 1,2,3

链表 VS 数组

链表中数据指定位置的添加和删除, 只需要更改指针引用即可。
因此这两种操作的时间复杂度为O(1).
但是链表的查询需要遍历找指针，因此时间复杂时间复杂度为O(n).

// 以添加为例：
append(value) {
	const newNode = new Node(value);
	if (!this.head) {
	  this.head = newNode;
	  this.tail = newNode;
	} else {
	  this.tail.next = newNode;
	  this.tail = newNode;
	}
	this.length++;
}

数组的查询有时候非常简单，时间复杂度为O(1)
但是数组指定位置的添加和删除，需要遍历，时间复杂度为O(n)
并且需要重新为数组分配空间，空间复杂度增加.

总结:
链表适用于需要频繁动态的添加、删除的操作。
数组适用于需要频繁的查询操作。

链表应用场景

实现栈和队列：与数组一样，链表也是有顺序的数据结构
实现哈希表：可以用链表解决哈希冲突的问题。
实现图: 链表的指针特点，非常适合用于实现图。

/*
哈希冲突：两个或多个数据集之间有某种关联性，
不符合使用哈希实现均匀散布的目的。
*/

算法

常见算法思想

回溯算法

一种按优尝试性的算法思想。当问题解有多种可能, 优先按优尝试求解。
当某种可能求解失败，重头再来，替换第二个求解方式。

贪心算法

一种按当前最优求解的算法思想。
当问题解目前有一个最优选择, 就按目前的方式求解。
不从整体看考虑，考虑局部最优解。

分治法

一种规模分解求解的算法思想。
当一个规模为n的问题短期难以求解，则分解为多个子规模
必要时通过递归，组合等方式，合并问题的解得到最终解。

动态规划

一种规模分解的算法思想，和分治法很像。
其注意子问题解决的顺序，先求解易解决的子问题。
并且保存前面的解, 以便后续可以重复利用。后续阶段通过前面的解+决策得到问题最优解。

动态规划和分治法的区别
目标不同:
- 分治法: 为了问题能被解决，而分解为子问题，并一一求解。
- 动态规划: 为了求得问题的最优解, 而分解子问题，并以易求解优先。
子问题重复利用:
- 分治法: 不会保存子问题的解。
- 动态规划: 保存前面的解, 以便后续可以重复利用。
子问题规模:
- 分治法: 分解为多个一样的规模。
- 动态规划: 分解为较小的子问题。
时间复杂度和空间复杂度:
- 分支法: 不产生额外空间，但是时间复杂度较高。
- 动态规划: 需要额外空间保存子问题解，但是时间复杂度较低。

排序算法

冒泡排序

小气泡不断往上冒泡，直到变大。
两个元素不断比较，较小的排序在前，直到排序完成。

插入排序

和打扑克抓牌一样，根据抓到的牌，插入到手上。先把第2个元素额外存起来，
根据后续元素的大小，插入到额外数组里面。

选择排序

宏观的排序思想，每次把最小的选出来, 放置到最左边。
然后选除了该元素外，最小的选出来, 递归排序。

快速排序

采用分治法配合基准值的算法思想，将数组分为两个子数组。
基准值: 计算数组的平均值，作为基准值。分治规定: 左边数组的元素小于基准值，右边元素大于基准值。
然后根据与基准值比较, 继续划分，递归快排直到划分完整。
快速排序是数组sort排序方式的实现原理。

数据结构 ​

复杂度 ​

时间复杂度 ​

O(1) ​

O(n) ​

O(n^2) ​

O(log2n) ​

计算步骤 ​

计算规则 ​

空间复杂度 ​

O(1) ​

O(n) ​

O(n^2) ​

O(log2n) ​

额外补充 ​

数据结构 ​

栈 ​

队列 ​

链表 ​

链表 VS 数组 ​

链表应用场景 ​

算法 ​

常见算法思想 ​

回溯算法 ​

贪心算法 ​

分治法 ​

动态规划 ​

排序算法 ​

冒泡排序 ​

插入排序 ​

选择排序 ​

快速排序 ​

数据结构

复杂度

时间复杂度

O(1)

O(n)

O(n^2)

O(log2n)

计算步骤

计算规则

空间复杂度

O(1)

O(n)

O(n^2)

O(log2n)

额外补充

数据结构

栈

队列

链表

链表 VS 数组

链表应用场景

算法

常见算法思想

回溯算法

贪心算法

分治法

动态规划

排序算法

冒泡排序

插入排序

选择排序

快速排序