# Frontend algorithm

**Repository Path**: DZHgino/frontend-algorithm

## Basic Information

- **Project Name**: Frontend algorithm
- **Description**: 前端常遇到的算法题、面试题
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2025-01-23
- **Last Updated**: 2025-12-12

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 算法复杂度
![](./img/complexity.png)
## 什么是复杂度
  - 程序执行时需要的计算量和内存空间（和代码是否简洁无关）
  - 复杂度是数量级（方便记忆、推广），不是具体的数字
  - 一般针对一个具体的算法，而非一个完整的系统

## 时间复杂度

### 程序执行时需要的计算量（cpu）
  - O(1) 一次就够（数量级）
  - O(n) 和传输的数量一样（数量级）
  - O(n^2) 数据量的平方（数量级）
  - O(logn) 数据量的对数（数量级）
  - O(n*logn) 数据量*数据量的对数（数量级） 

## 空间复杂度

### 程序执行时需要的内存空间
 - O(1) 有限的、可数的空间（数量级）
 - O(n) 和输入的数据量相同的空间（数据级）

### 前端开发：重时间，轻空间

## 栈
  - 先进后出
  - API: push pop length
  ![](./img/stack.png)
  
### 逻辑结构 vs 物理结构
  - 栈，逻辑结构。理论模型，不管如何实现，不受任何语言的限制
  - 数组，物理结构。真实的功能实现，受限于编程语言

## 队列
  - 先进先出
  - API: add delete length

### 逻辑结构 vs 物理结构
  - 队列是逻辑结构，抽象模型
  - 简单的可以用数组、链表实现
  - 复杂的队列服务，需要单独设计

## 链表
  - 链表是一种物理结构（非逻辑结构），类似于数组
  - 数组需要一段连续的内存区间，而链表是零散的
  - 链表节点的数据结构 { value, next?, prev? }

### 链表 vs 数组
 - 都是有序结构
 - 链表：查询慢O(n)，新增和删除快O(1)
 - 数组：查询快O(1)，新增和删除慢O(n)

  连环问：链表和数组哪个实现队列更快？
    性能分析：
        - 空间复杂度都是O(n)
        - add 时间复杂度：链表O(1)；数组O(1)
        - delete时间复杂度：链表O(1)；数组O(n)
    分析：
        - 数组是连续存储，push很快，shift很慢
        - 链表是非连续存储，add和delete都很快（但查找很慢）
        - 结论：链表实现队列更快！

# 二叉树（Binary Tree）
  - 是一棵树
  - 每个节点最多只能有2个子节点
  - 树节点的数据结构 { value, left?, right? }

## 二叉树的遍历
  - 前序遍历：root -> left -> right
  - 中序遍历：left -> root -> right
  - 后序遍历：left -> right -> root

# 二叉搜索树（Binary Search Tree）
 - left（包括其后代）value <= root value
 - right（包括其后代）value >= root value
 - 可使用二分法进行快速查找

注：二叉搜索树BST：查找快，增删快-“木桶效应”

提问：为何二叉树如此重要，而不是三叉树、四叉树？

# 堆栈模型
  - JS代码执行时
  - 值类型变量，存储在栈
  - 引用类型变量，存储在堆

## 堆
  - 完全二叉树
  - 最大堆：父节点 >= 子节点
  - 最小堆：父节点 <= 子节点

![](./img/CBT.png)

### 逻辑结构 vs 物理结构
  - 堆，逻辑结构是一颗二叉树
  - 但它物理结构是一个数组
  - 数组：适合连续存储 + 节省空间（回顾堆栈模型）

# 斐波那契数列
  - f(0) = 0
  - f(1) = 1
  - f(n) = f(n -1) + f(n -2)

为何 0.1 + 0.2 !== 0.3？

# 如何实现高效的英文单词前缀匹配
  - 第一，遍历单词库数组
  - 第二，indexOf判断前缀
  - 实际时间复杂度超过了O(n)，因为要考虑indexOf的计算量
  性能分析：
  - 如遍历数组，时间复杂度至少O(n)起步（n是数组长度）
  - 而改为树，时间复杂度降低到O(m)，（m是单词的长度）
  - PS：哈希表（对象）通过key查询，时间复杂度是O(1)