文章信息

标题: JavaScript 3. 数据结构与算法基础
发布时间: 2026 年 7 月 19 日
来源: https://physchen.com/zh-Hans/programming/notes/javascript-data-structures-and-algorithms/
摘要: 从计算机科学视角介绍 JavaScript 中常用的数据结构、渐进复杂度、排序与查找算法、树与图的遍历，以及递归、记忆化和动态规划等基本方法。

JavaScript 3. 数据结构与算法基础

发布于 2026 年 7 月 19 日

数据结构描述数据之间的组织关系⁠，算法描述处理这些数据的步骤⁠。程序设计中的许多性能问题⁠，本质上都来自两个选择⁠：

数据以什么结构保存⁠；
操作这些数据时采用什么算法⁠。

在 JavaScript 中⁠，数组⁠、普通对象⁠、Map 和 Set 已经能够满足大量实际需求⁠。学习链表⁠、栈⁠、队列⁠、树⁠、图和哈希表⁠，并不是要求所有程序都自行实现这些结构⁠，而是为了理解不同操作的成本⁠、适用条件和工程权衡⁠。

本章主要讨论⁠：

抽象数据类型与具体实现的区别⁠；
时间复杂度和辅助空间复杂度⁠；
JavaScript 内置集合在算法中的作用⁠；
栈⁠、队列⁠、链表和哈希表⁠；
树⁠、图⁠、广度优先搜索和深度优先搜索⁠；
常见排序与查找算法⁠；
递归⁠、记忆化和动态规划⁠；
0-1 背包问题与最长递增子序列⁠。

对象属性模型⁠、数组方法⁠、复制和集合 API 已在第五章系统讨论⁠。本章只保留分析算法时需要的接口和性能认识⁠。

3.1 数据结构与抽象数据类型

3.1.1 数据结构

数据结构是数据及其关系的组织方式⁠。

例如⁠：

数组使用整数索引表示顺序⁠；
链表通过节点之间的引用表示顺序⁠；
树表示父子层级⁠；
图表示一般的多对多关系⁠；
哈希表通过键映射到存储位置⁠。

同一逻辑关系可以有不同实现⁠。例如⁠，队列既可以由数组实现⁠，也可以由链表或环形缓冲区实现⁠。

3.1.2 抽象数据类型

抽象数据类型（⁠Abstract Data Type⁠，ADT⁠）规定一组值和允许执行的操作⁠，而不规定具体存储方法⁠。

栈通常提供⁠：

push(value)⁠；
pop()⁠；
peek()⁠；
isEmpty()⁠；
size()⁠。

队列通常提供⁠：

enqueue(value)⁠；
dequeue()⁠；
peek()⁠；
isEmpty()⁠；
size()⁠。

调用者依赖这些操作的语义⁠，不需要知道底层使用数组还是链表⁠。

3.1.3 线性与非线性结构

线性数据结构中的元素形成单一顺序⁠，例如⁠：

数组⁠；
链表⁠；
栈⁠；
队列⁠；
双端队列⁠。

非线性数据结构允许一个元素与多个元素关联⁠，例如⁠：

树⁠；
堆⁠；
图⁠；
Trie⁠。

“⁠线性⁠”描述逻辑关系⁠，不等同于物理内存一定连续⁠。链表在逻辑上是线性结构⁠，但节点不需要连续存储⁠。

3.2 渐进复杂度

算法复杂度描述输入规模增长时⁠，时间或空间消耗的增长趋势⁠。

通常使用 $n$ 表示输入规模⁠。

3.2.1 Big O⁠、Big Ω 与 Big Θ

严格地说⁠：

$O(f(n))$ 表示渐进上界⁠；
$\Omega(f(n))$ 表示渐进下界⁠；
$\Theta(f(n))$ 表示同阶的渐进紧确界⁠。

工程讨论中⁠，人们经常较宽松地使用 Big O 表示算法的主要增长量级⁠。例如⁠，线性遍历通常称为 $O(n)$ ⁠，虽然在给定模型下更严格地说可能是 $\Theta(n)$ ⁠。

本章沿用常见工程表达⁠，但应知道 Big O 并不是精确运行时间⁠。

3.2.2 常见增长量级

O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)

复杂度	典型含义	常见示例
$O(1)$	成本不随输入规模按比例增长	根据数组索引读取元素
$O(\log n)$	每一步显著缩小问题规模	二分查找
$O(n)$	遍历全部输入	线性查找
$O(n\log n)$	对数层级中处理线性数据	归并排序
$O(n^2)$	常见于双层相关遍历	选择排序
$O(2^n)$	枚举大量子集或重复分支	朴素递归斐波那契
$O(n!)$	枚举排列	暴力排列搜索

复杂度较低并不意味着在所有实际规模下都更快⁠。常数开销⁠、内存局部性⁠、实现方式和数据分布都可能影响实际性能⁠。

3.2.3 时间复杂度

时间复杂度关注基本操作次数如何随输入规模增长⁠。

function sum(values) {
  let total = 0;

  for (const value of values) {
    total += value;
  }

  return total;
}

每个元素访问一次⁠，因此时间复杂度为 $O(n)$ ⁠。

3.2.4 辅助空间复杂度

辅助空间复杂度只计算算法为了完成工作额外使用的空间⁠，不把输入本身重复计入⁠。

function sum(values) {
  let total = 0;

  for (const value of values) {
    total += value;
  }

  return total;
}

只使用少量变量⁠，辅助空间复杂度为 $O(1)$ ⁠。

归并排序需要与输入规模同阶的辅助数组⁠，因此通常为 $O(n)$ ⁠。

3.2.5 最好⁠、平均与最坏情况

线性查找目标位于第一个位置时⁠，最好情况为 $O(1)$ ⁠；目标不存在或位于最后时⁠，最坏情况为 $O(n)$ ⁠。

快速排序的平均时间复杂度通常为 $O(n\log n)$ ⁠，但高度不平衡的连续划分会使最坏情况退化为 $O(n^2)$ ⁠。

分析复杂度时必须说明讨论的是哪种情况⁠。

3.2.6 均摊复杂度

某些操作偶尔成本较高⁠，但在一系列操作中平均成本较低⁠。

动态数组容量不足时⁠，可能需要申请更大的存储并复制已有元素⁠。单次扩容可能需要 $O(n)$ ⁠，但连续尾部追加的平均成本通常视为均摊 $O(1)$ ⁠。

均摊分析不是对单次最坏成本的否认⁠，而是分析一系列操作的总成本⁠。

3.2.7 化简规则

忽略常数因子⁠：

5n=O(n)

保留最高阶项⁠：

5n^2+100n+20=O(n^2)

顺序执行⁠：

O(n)+O(n)=O(n)

嵌套执行⁠：

O(n)\times O(n)=O(n^2)

这些只是基本规则⁠。真实代码还需要分析循环边界是否相关⁠、内部操作是否为常数成本⁠，以及算法是否提前终止⁠。

3.2.8 JavaScript 内置方法的复杂度

ECMAScript 通常规定内置方法的可观察行为⁠，而不统一规定引擎必须采用哪种具体算法⁠。

例如⁠：

规范不要求数组必须使用连续内存⁠；
规范不规定 Array.prototype.sort() 必须使用快速排序或归并排序⁠；
规范不要求 Map 必须由哈希表实现⁠；
规范只对 Map 的平均访问性能提出次线性要求⁠。

因此⁠，内置方法的复杂度通常来自现代引擎的常见实现和算法模型⁠，而不是所有环境中的绝对语言保证⁠。

性能敏感代码应结合⁠：

数据规模⁠；
目标运行环境⁠；
基准测试⁠；
性能分析器⁠；
内存分析⁠。

进行验证⁠。

3.3 JavaScript 内置集合与算法

3.3.1 Array

数组适合⁠：

按顺序保存元素⁠；
根据整数索引访问⁠；
顺序遍历⁠；
在尾部追加和移除⁠；
使用 map()⁠、filter()⁠、reduce() 等管线处理数据⁠。

典型近似成本⁠：

操作	常见复杂度
根据索引读取	$O(1)$
尾部 `push()` / `pop()`	均摊 $O(1)$
头部 `shift()` / `unshift()`	$O(n)$
`includes()` / `indexOf()`	$O(n)$
`slice()`	与复制元素数成正比
中间位置 `splice()`	通常为 $O(n)$

这些复杂度是常见实现下的算法模型⁠，不是 ECMAScript 对所有引擎作出的严格性能承诺⁠。

3.3.2 Map

Map 适合动态键值映射⁠：

const scores = new Map();

scores.set(
  "Alice",
  95,
);

scores.set(
  "Bob",
  88,
);

console.log(
  scores.get("Alice"),
);

键可以是任意 JavaScript 值⁠，包括对象⁠。

ECMAScript 不要求 Map 采用哈希表⁠，但要求实现提供相对于元素数量平均次线性的访问性能⁠。现代引擎通常使用哈希或具有类似性能特征的结构⁠。

3.3.3 Set

Set 适合成员判断和去重⁠：

const visited = new Set();

visited.add("A");

console.log(
  visited.has("A"),
); // true

图搜索中⁠，Set 常用于记录已经访问的顶点⁠，避免重复处理或陷入环⁠。

3.3.4 选择内置结构

需求	常见选择
有序元素序列	`Array`
动态键值映射	`Map`
唯一值集合	`Set`
固定字段记录	普通对象
固定数值类型的二进制序列	TypedArray

除非需要特殊操作语义⁠，不应因为“⁠手写结构更底层⁠”而替代已经成熟的内置集合⁠。

3.4 栈

栈遵循后进先出（⁠Last In, First Out⁠，LIFO⁠）原则⁠。

最后压入的元素最先弹出⁠。

3.4.1 数组实现

class Stack {
  #items = [];

  push(value) {
    this.#items.push(value);
  }

  pop() {
    return this.#items.pop();
  }

  peek() {
    return this.#items.at(-1);
  }

  get size() {
    return this.#items.length;
  }

  isEmpty() {
    return (
      this.#items.length === 0
    );
  }

  clear() {
    this.#items.length = 0;
  }
}

使用⁠：

const stack = new Stack();

stack.push(10);
stack.push(20);

console.log(stack.peek()); // 20
console.log(stack.pop());  // 20
console.log(stack.size);   // 1

数组尾部操作通常具有均摊常数成本⁠，因此非常适合实现栈⁠。

3.4.2 括号匹配

function hasBalancedBrackets(
  source,
) {
  const stack = [];

  const openingByClosing
    = new Map([
      [")", "("],
      ["]", "["],
      ["}", "{"],
    ]);

  const opening = new Set([
    "(",
    "[",
    "{",
  ]);

  for (const character of source) {
    if (opening.has(character)) {
      stack.push(character);
      continue;
    }

    if (
      openingByClosing.has(
        character,
      )
    ) {
      const expectedOpening
        = openingByClosing.get(
          character,
        );

      if (
        stack.pop()
        !== expectedOpening
      ) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

时间复杂度为 $O(n)$ ⁠，辅助空间最坏为 $O(n)$ ⁠。

3.4.3 典型应用

函数调用关系⁠；
括号匹配⁠；
撤销和重做⁠；
深度优先搜索⁠；
表达式求值⁠；
解析器⁠；
路径回溯⁠。

3.5 队列

队列遵循先进先出（⁠First In, First Out⁠，FIFO⁠）原则⁠。

最早进入的元素最先离开⁠。

3.5.1 不宜频繁使用 shift()

const queue = [];

queue.push("A");
queue.push("B");

console.log(
  queue.shift(),
); // A

这段代码适合小规模或非性能敏感场景⁠，但 shift() 通常需要重新处理后续索引⁠，因此队列较长⁠、出队频繁时成本会增大⁠。

3.5.2 头尾索引实现

class Queue {
  #items = Object.create(null);
  #head = 0;
  #tail = 0;

  enqueue(value) {
    this.#items[this.#tail]
      = value;

    this.#tail += 1;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }

    const value
      = this.#items[this.#head];

    delete this.#items[
      this.#head
    ];

    this.#head += 1;

    if (
      this.#head === this.#tail
    ) {
      this.#head = 0;
      this.#tail = 0;
    }

    return value;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }

    return this.#items[
      this.#head
    ];
  }

  get size() {
    return (
      this.#tail
      - this.#head
    );
  }

  isEmpty() {
    return (
      this.#head === this.#tail
    );
  }

  clear() {
    this.#items
      = Object.create(null);

    this.#head = 0;
    this.#tail = 0;
  }
}

在现代引擎的常见实现中⁠，这些基本操作可以视为平均或均摊 $O(1)$ ⁠。ECMAScript 不对普通对象属性操作提供逐次严格常数时间保证⁠，因此不应称为语言层面“⁠严格 $O(1)$ ⁠”⁠。

3.5.3 使用示例

const queue = new Queue();

queue.enqueue("Task A");
queue.enqueue("Task B");

console.log(queue.peek());
// Task A

console.log(queue.dequeue());
// Task A

console.log(queue.size);
// 1

3.5.4 典型应用

广度优先搜索⁠；
任务调度⁠；
消息缓冲⁠；
请求排队⁠；
生产者—消费者模型⁠；
流量控制⁠。

浏览器事件循环包含任务和微任务调度⁠，但不应简单等同于一个由 JavaScript 数组实现的统一队列⁠。相关宿主机制已在第四章讨论⁠。

3.6 单向链表

链表由节点组成⁠，每个节点保存值和后继节点引用⁠。

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

3.6.1 基本实现

class LinkedList {
  #head = null;
  #tail = null;
  #length = 0;

  get length() {
    return this.#length;
  }

  prepend(value) {
    const node
      = new ListNode(value);

    node.next = this.#head;
    this.#head = node;

    if (
      this.#tail === null
    ) {
      this.#tail = node;
    }

    this.#length += 1;
  }

  append(value) {
    const node
      = new ListNode(value);

    if (
      this.#tail === null
    ) {
      this.#head = node;
      this.#tail = node;
    } else {
      this.#tail.next = node;
      this.#tail = node;
    }

    this.#length += 1;
  }

  at(index) {
    if (
      !Number.isInteger(index)
      || index < 0
      || index >= this.#length
    ) {
      return undefined;
    }

    let current = this.#head;

    for (
      let currentIndex = 0;
      currentIndex < index;
      currentIndex += 1
    ) {
      current = current.next;
    }

    return current.value;
  }

  deleteAt(index) {
    if (
      !Number.isInteger(index)
      || index < 0
      || index >= this.#length
    ) {
      return undefined;
    }

    if (index === 0) {
      const removed
        = this.#head;

      this.#head
        = removed.next;

      this.#length -= 1;

      if (
        this.#length === 0
      ) {
        this.#tail = null;
      }

      return removed.value;
    }

    let previous = this.#head;

    for (
      let currentIndex = 1;
      currentIndex < index;
      currentIndex += 1
    ) {
      previous = previous.next;
    }

    const removed
      = previous.next;

    previous.next
      = removed.next;

    if (
      removed === this.#tail
    ) {
      this.#tail = previous;
    }

    this.#length -= 1;

    return removed.value;
  }

  toArray() {
    const result = [];
    let current = this.#head;

    while (
      current !== null
    ) {
      result.push(
        current.value,
      );

      current = current.next;
    }

    return result;
  }

  *[Symbol.iterator]() {
    let current = this.#head;

    while (
      current !== null
    ) {
      yield current.value;
      current = current.next;
    }
  }
}

3.6.2 复杂度

操作	复杂度
头部插入	$O(1)$
保存尾指针后的尾部插入	$O(1)$
按索引访问	$O(n)$
按索引删除	$O(n)$
已知前驱节点时修改连接	$O(1)$
遍历	$O(n)$

“⁠链表删除为 $O(1)$ ⁠”必须说明前提⁠。只有在已经获得需要修改连接所需的节点引用时⁠，连接变更本身才是常数成本⁠；按索引或值寻找节点仍然通常需要 $O(n)$ ⁠。

3.6.3 与数组的权衡

链表优势⁠：

头部增删成本低⁠；
已知节点位置时连接修改简单⁠；
不需要移动后续元素⁠；
适合实现某些队列⁠、缓存和邻接结构⁠。

数组优势⁠：

随机访问⁠；
内存局部性通常更好⁠；
引擎高度优化⁠；
内置方法丰富⁠；
实际代码更简单⁠。

在 JavaScript 中⁠，自定义链表节点是独立对象⁠，会产生对象分配和垃圾回收成本⁠。大多数普通业务数据仍应优先使用数组⁠。

3.7 双向链表

双向链表节点同时保存前驱和后继引用⁠：

class DoublyLinkedNode {
  constructor(value) {
    this.value = value;
    this.previous = null;
    this.next = null;
  }
}

优势⁠：

可以双向遍历⁠；
已知节点时可直接连接前后节点⁠；
删除已知节点通常为 $O(1)$ ⁠；
适合双端队列和 LRU 缓存⁠。

代价⁠：

每个节点多保存一个引用⁠；
插入和删除需要维护更多关系⁠；
更容易产生断链或错误连接⁠；
JavaScript 对象分配成本较高⁠。

双向链表最常见的工程用途之一是与 Map 结合实现 LRU 缓存⁠：

Map 提供按键快速定位节点⁠；
双向链表维护最近使用顺序⁠；
链表头尾支持快速移动和淘汰⁠。

3.8 哈希表

哈希表使用哈希函数把键映射到桶或槽位⁠。

理想目标是让⁠：

插入⁠；
查找⁠；
删除⁠。

在平均情况下具有接近常数的成本⁠。

3.8.1 哈希函数

哈希函数需要⁠：

对相同键稳定产生相同结果⁠；
尽量把键均匀分布到桶中⁠；
计算成本可接受⁠；
适合所处理的键空间⁠。

教学用字符串哈希⁠：

function hashString(
  key,
  bucketCount,
) {
  let hashValue = 0;

  for (
    let index = 0;
    index < key.length;
    index += 1
  ) {
    hashValue = (
      hashValue * 31
      + key.charCodeAt(index)
    ) % bucketCount;
  }

  return hashValue;
}

这不是密码学哈希⁠，也不适合安全用途⁠。

3.8.2 哈希冲突

不同键可能映射到同一桶⁠：

"ab" → bucket 3
"ba" → bucket 3

这称为哈希冲突⁠。

常见处理方式⁠：

链地址法⁠；
开放寻址⁠；
再哈希⁠；
双重哈希⁠。

3.8.3 链地址法

每个桶保存多个键值对⁠：

class HashTable {
  #buckets;
  #count = 0;

  constructor(
    bucketCount = 16,
  ) {
    if (
      !Number.isInteger(
        bucketCount,
      )
      || bucketCount <= 0
    ) {
      throw new RangeError(
        "bucketCount 必须是正整数",
      );
    }

    this.#buckets
      = Array.from(
        {
          length: bucketCount,
        },
        () => [],
      );
  }

  get size() {
    return this.#count;
  }

  #hash(key) {
    if (
      typeof key !== "string"
    ) {
      throw new TypeError(
        "该教学实现只支持字符串键",
      );
    }

    return hashString(
      key,
      this.#buckets.length,
    );
  }

  set(key, value) {
    const bucket
      = this.#buckets[
        this.#hash(key)
      ];

    for (const entry of bucket) {
      if (entry.key === key) {
        entry.value = value;
        return this;
      }
    }

    bucket.push({
      key,
      value,
    });

    this.#count += 1;

    if (
      this.#count
      / this.#buckets.length
      > 0.75
    ) {
      this.#resize(
        this.#buckets.length * 2,
      );
    }

    return this;
  }

  get(key) {
    const bucket
      = this.#buckets[
        this.#hash(key)
      ];

    const entry = bucket.find(
      item => item.key === key,
    );

    return entry?.value;
  }

  has(key) {
    const bucket
      = this.#buckets[
        this.#hash(key)
      ];

    return bucket.some(
      item => item.key === key,
    );
  }

  delete(key) {
    const bucket
      = this.#buckets[
        this.#hash(key)
      ];

    const index
      = bucket.findIndex(
        item => item.key === key,
      );

    if (index === -1) {
      return false;
    }

    bucket.splice(index, 1);
    this.#count -= 1;

    return true;
  }

  #resize(nextBucketCount) {
    const entries = [];

    for (
      const bucket
      of this.#buckets
    ) {
      for (const entry of bucket) {
        entries.push(entry);
      }
    }

    this.#buckets
      = Array.from(
        {
          length: nextBucketCount,
        },
        () => [],
      );

    this.#count = 0;

    for (const entry of entries) {
      this.set(
        entry.key,
        entry.value,
      );
    }
  }
}

3.8.4 负载因子与扩容

负载因子常定义为⁠：

\alpha=\frac{\text{元素数量}}{\text{桶数量}}

负载过高时⁠，冲突增多⁠，桶内扫描成本上升⁠。扩容会⁠：

创建更多桶⁠；
重新计算所有键的位置⁠；
把元素放入新桶⁠。

单次扩容需要 $O(n)$ ⁠，但分散在连续插入中⁠，插入仍可获得均摊较低成本⁠。

3.8.5 最坏情况

如果所有键进入同一桶⁠，查找退化为线性扫描⁠：

O(n)

实际哈希表还需要考虑⁠：

恶意冲突⁠；
随机化⁠；
键相等语义⁠；
删除后的空间⁠；
内存占用⁠；
缩容⁠；
迭代顺序⁠；
并发安全⁠。

生产代码通常应使用 Map⁠，而不是自行实现通用哈希表⁠。

3.9 树

树表示层级结构⁠。

3.9.1 基本术语

根节点⁠：没有父节点⁠；
父节点⁠：直接连接到下层节点⁠；
子节点⁠：直接连接到上层节点⁠；
兄弟节点⁠：具有同一父节点⁠；
叶节点⁠：没有子节点⁠；
深度⁠：根到当前节点的边数⁠；
高度⁠：当前节点到最深叶节点的最大边数⁠；
子树⁠：某节点及其全部后代⁠。

3.9.2 二叉树

二叉树中每个节点最多具有两个子节点⁠：

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new TreeNode(10);

root.left = new TreeNode(5);
root.right = new TreeNode(20);

root.left.left
  = new TreeNode(3);

root.left.right
  = new TreeNode(8);

3.10 二叉树遍历

3.10.1 前序遍历

顺序⁠：

根 → 左子树 → 右子树

function preorder(
  node,
  result = [],
) {
  if (node === null) {
    return result;
  }

  result.push(node.value);

  preorder(
    node.left,
    result,
  );

  preorder(
    node.right,
    result,
  );

  return result;
}

3.10.2 中序遍历

顺序⁠：

左子树 → 根 → 右子树

function inorder(
  node,
  result = [],
) {
  if (node === null) {
    return result;
  }

  inorder(
    node.left,
    result,
  );

  result.push(node.value);

  inorder(
    node.right,
    result,
  );

  return result;
}

二叉搜索树的中序遍历可以得到有序序列⁠。

3.10.3 后序遍历

顺序⁠：

左子树 → 右子树 → 根

function postorder(
  node,
  result = [],
) {
  if (node === null) {
    return result;
  }

  postorder(
    node.left,
    result,
  );

  postorder(
    node.right,
    result,
  );

  result.push(node.value);

  return result;
}

后序遍历适合需要先处理子节点⁠，再处理父节点的任务⁠。

3.10.4 层序遍历

按照树的层级从上到下访问⁠，使用队列⁠：

function levelOrder(root) {
  if (root === null) {
    return [];
  }

  const result = [];
  const queue = new Queue();

  queue.enqueue(root);

  while (!queue.isEmpty()) {
    const node
      = queue.dequeue();

    result.push(node.value);

    if (
      node.left !== null
    ) {
      queue.enqueue(node.left);
    }

    if (
      node.right !== null
    ) {
      queue.enqueue(node.right);
    }
  }

  return result;
}

每个节点访问一次⁠，时间复杂度为 $O(n)$ ⁠，辅助空间最坏为 $O(n)$ ⁠。

3.11 二叉搜索树

二叉搜索树通常满足⁠：

左子树中的键小于当前节点键⁠；
右子树中的键大于当前节点键⁠；
左右子树也分别满足相同规则⁠。

重复键如何处理需要由具体实现定义⁠。

3.11.1 查找

function searchBinaryTree(
  root,
  target,
) {
  let current = root;

  while (
    current !== null
  ) {
    if (
      target === current.value
    ) {
      return current;
    }

    current = (
      target < current.value
        ? current.left
        : current.right
    );
  }

  return null;
}

复杂度取决于树高 $h$ ⁠：

O(h)

平衡树⁠：

h=O(\log n)

退化链状树⁠：

h=O(n)

因此⁠，普通二叉搜索树并不自动保证 $O(\log n)$ 查找⁠。

3.11.2 平衡搜索树

AVL 树⁠、红黑树等结构通过额外规则控制树高⁠，使主要操作保持对数级复杂度⁠。

JavaScript 标准库没有直接提供有序平衡树⁠。需要⁠：

有序映射⁠；
范围查询⁠；
顺序统计⁠；
按序快速插入删除⁠。

时⁠，可以使用专用库或根据需求实现⁠。

3.12 图

图由顶点和边组成⁠。

3.12.1 分类

有向图与无向图⁠；
加权图与无权图⁠；
连通图与非连通图⁠；
有环图与无环图⁠；
稀疏图与稠密图⁠。

典型应用⁠：

道路网络⁠；
社交关系⁠；
网页链接⁠；
软件依赖⁠；
状态转换⁠；
任务调度⁠；
知识图谱⁠。

3.12.2 邻接表

class Graph {
  #adjacency = new Map();

  addVertex(vertex) {
    if (
      !this.#adjacency.has(
        vertex,
      )
    ) {
      this.#adjacency.set(
        vertex,
        new Set(),
      );
    }
  }

  addUndirectedEdge(
    first,
    second,
  ) {
    this.addVertex(first);
    this.addVertex(second);

    this.#adjacency
      .get(first)
      .add(second);

    this.#adjacency
      .get(second)
      .add(first);
  }

  neighbors(vertex) {
    return (
      this.#adjacency.get(
        vertex,
      )
      ?? new Set()
    );
  }

  hasVertex(vertex) {
    return this.#adjacency.has(
      vertex,
    );
  }
}

对于 $V$ 个顶点和 $E$ 条边⁠，邻接表空间复杂度通常为⁠：

O(V+E)

无向图中每条边通常在两个顶点的邻接集合中各记录一次⁠，但渐进量级仍为 $O(V+E)$ ⁠。

3.12.3 邻接矩阵

使用二维矩阵⁠：

const matrix = [
  [0, 1, 1],
  [1, 0, 0],
  [1, 0, 0],
];

空间复杂度⁠：

O(V^2)

优点⁠：

判断两个给定顶点是否直接相连通常为 $O(1)$ ⁠；
适合稠密图⁠；
矩阵算法表达自然⁠。

缺点⁠：

稀疏图浪费空间⁠；
遍历某顶点邻居需要扫描整行⁠。

3.13 广度优先搜索

广度优先搜索（⁠Breadth-First Search⁠，BFS⁠）按距离起点由近到远访问顶点⁠，使用队列⁠。

function breadthFirstSearch(
  graph,
  start,
) {
  if (
    !graph.hasVertex(start)
  ) {
    return [];
  }

  const visited = new Set([
    start,
  ]);

  const queue = new Queue();
  const order = [];

  queue.enqueue(start);

  while (!queue.isEmpty()) {
    const vertex
      = queue.dequeue();

    order.push(vertex);

    for (
      const neighbor
      of graph.neighbors(vertex)
    ) {
      if (
        visited.has(neighbor)
      ) {
        continue;
      }

      visited.add(neighbor);
      queue.enqueue(neighbor);
    }
  }

  return order;
}

邻接表下⁠，每个顶点和每条边只被处理有限次⁠：

O(V+E)

辅助空间⁠：

O(V)

对于无权图⁠，BFS 可以求起点到其他顶点的最少边数⁠。

3.14 深度优先搜索

深度优先搜索（⁠Depth-First Search⁠，DFS⁠）沿一条路径尽可能深入⁠，再回溯⁠。

3.14.1 递归实现

function depthFirstSearch(
  graph,
  start,
) {
  if (
    !graph.hasVertex(start)
  ) {
    return [];
  }

  const visited = new Set();
  const order = [];

  function visit(vertex) {
    visited.add(vertex);
    order.push(vertex);

    for (
      const neighbor
      of graph.neighbors(vertex)
    ) {
      if (
        !visited.has(neighbor)
      ) {
        visit(neighbor);
      }
    }
  }

  visit(start);

  return order;
}

3.14.2 显式栈实现

function depthFirstSearchIterative(
  graph,
  start,
) {
  if (
    !graph.hasVertex(start)
  ) {
    return [];
  }

  const visited = new Set();
  const stack = [start];
  const order = [];

  while (
    stack.length > 0
  ) {
    const vertex
      = stack.pop();

    if (
      visited.has(vertex)
    ) {
      continue;
    }

    visited.add(vertex);
    order.push(vertex);

    const neighbors = [
      ...graph.neighbors(vertex),
    ];

    for (
      let index
        = neighbors.length - 1;
      index >= 0;
      index -= 1
    ) {
      const neighbor
        = neighbors[index];

      if (
        !visited.has(neighbor)
      ) {
        stack.push(neighbor);
      }
    }
  }

  return order;
}

邻接表下时间复杂度同样为⁠：

O(V+E)

递归实现受 JavaScript 调用栈深度限制⁠。图很深时⁠，显式栈通常更加稳妥⁠。

3.14.3 BFS 与 DFS

对比	BFS	DFS
核心结构	队列	栈或递归
访问方式	分层扩展	沿路径深入
无权最短路	适合	不保证
路径探索	逐层	先深入
调用栈风险	无递归时较低	递归实现可能溢出
典型应用	最少边数⁠、层序	拓扑⁠、连通性⁠、回溯

3.15 排序算法

排序算法根据比较规则重新排列元素⁠。

需要关注⁠：

时间复杂度⁠；
辅助空间⁠；
稳定性⁠；
是否修改原数组⁠；
对输入分布是否敏感⁠；
递归深度⁠；
实际数据规模⁠。

实际项目通常优先使用 sort() 或 toSorted()⁠。手写排序主要用于理解算法和满足特殊约束⁠。

3.16 稳定排序

如果两个元素在比较意义上相等⁠，排序后仍保持原相对顺序⁠，则算法稳定⁠。

const students = [
  {
    name: "Alice",
    score: 90,
  },
  {
    name: "Bob",
    score: 80,
  },
  {
    name: "Carol",
    score: 90,
  },
];

按 score 排序后⁠，如果 Alice 仍位于 Carol 前面⁠，则保持稳定性⁠。

现代 ECMAScript 要求 Array.prototype.sort() 和 toSorted() 稳定⁠，但不规定引擎必须使用哪种排序算法⁠。

3.17 冒泡排序

冒泡排序重复比较相邻元素⁠，把较大元素逐步移动到未排序区域末尾⁠。

function bubbleSortInPlace(
  array,
  compare = (
    first,
    second,
  ) => first - second,
) {
  for (
    let end
      = array.length - 1;
    end > 0;
    end -= 1
  ) {
    let swapped = false;

    for (
      let index = 0;
      index < end;
      index += 1
    ) {
      if (
        compare(
          array[index],
          array[index + 1],
        ) > 0
      ) {
        [
          array[index],
          array[index + 1],
        ] = [
          array[index + 1],
          array[index],
        ];

        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }
  }

  return array;
}

复杂度⁠：

最好⁠： $O(n)$ ⁠；
平均⁠： $O(n^2)$ ⁠；
最坏⁠： $O(n^2)$ ⁠；
辅助空间⁠： $O(1)$ ⁠；
稳定⁠。

它实现简单⁠，但比较和交换次数较多⁠，不适合大规模数据⁠。

3.18 选择排序

每轮从未排序区域找出最小元素⁠，与当前起始位置交换⁠。

function selectionSortInPlace(
  array,
  compare = (
    first,
    second,
  ) => first - second,
) {
  for (
    let start = 0;
    start < array.length - 1;
    start += 1
  ) {
    let minimumIndex = start;

    for (
      let index = start + 1;
      index < array.length;
      index += 1
    ) {
      if (
        compare(
          array[index],
          array[minimumIndex],
        ) < 0
      ) {
        minimumIndex = index;
      }
    }

    if (
      minimumIndex !== start
    ) {
      [
        array[start],
        array[minimumIndex],
      ] = [
        array[minimumIndex],
        array[start],
      ];
    }
  }

  return array;
}

复杂度⁠：

最好⁠、平均⁠、最坏⁠： $O(n^2)$ ⁠；
辅助空间⁠： $O(1)$ ⁠；
通常不稳定⁠。

选择排序比较次数基本不受输入有序程度影响⁠，但交换次数较少⁠。

3.19 插入排序

插入排序维护一个已排序前缀⁠，把下一元素插入合适位置⁠。

function insertionSortInPlace(
  array,
  compare = (
    first,
    second,
  ) => first - second,
) {
  for (
    let index = 1;
    index < array.length;
    index += 1
  ) {
    const current
      = array[index];

    let position
      = index - 1;

    while (
      position >= 0
      && compare(
        array[position],
        current,
      ) > 0
    ) {
      array[position + 1]
        = array[position];

      position -= 1;
    }

    array[position + 1]
      = current;
  }

  return array;
}

复杂度⁠：

已有序最好情况⁠： $O(n)$ ⁠；
平均⁠： $O(n^2)$ ⁠；
逆序最坏⁠： $O(n^2)$ ⁠；
辅助空间⁠： $O(1)$ ⁠；
稳定⁠。

插入排序适合⁠：

小规模数组⁠；
基本有序的数据⁠；
作为复杂排序算法处理小子数组的辅助方法⁠。

3.20 快速排序

快速排序采用分治⁠：

选择基准值⁠；
把较小值与较大值分到基准两侧⁠；
递归处理左右子区间⁠。

3.20.1 原地划分

function partition(
  array,
  left,
  right,
  compare,
) {
  const randomIndex
    = left + Math.floor(
      Math.random()
      * (right - left + 1),
    );

  [
    array[randomIndex],
    array[right],
  ] = [
    array[right],
    array[randomIndex],
  ];

  const pivot = array[right];
  let boundary = left;

  for (
    let index = left;
    index < right;
    index += 1
  ) {
    if (
      compare(
        array[index],
        pivot,
      ) < 0
    ) {
      [
        array[boundary],
        array[index],
      ] = [
        array[index],
        array[boundary],
      ];

      boundary += 1;
    }
  }

  [
    array[boundary],
    array[right],
  ] = [
    array[right],
    array[boundary],
  ];

  return boundary;
}

function quickSortInPlace(
  array,
  compare = (
    first,
    second,
  ) => first - second,
  left = 0,
  right = array.length - 1,
) {
  if (left >= right) {
    return array;
  }

  const pivotIndex = partition(
    array,
    left,
    right,
    compare,
  );

  quickSortInPlace(
    array,
    compare,
    left,
    pivotIndex - 1,
  );

  quickSortInPlace(
    array,
    compare,
    pivotIndex + 1,
    right,
  );

  return array;
}

3.20.2 复杂度

平均时间⁠： $O(n\log n)$ ⁠；
最坏时间⁠： $O(n^2)$ ⁠；
平均调用栈⁠： $O(\log n)$ ⁠；
最坏调用栈⁠： $O(n)$ ⁠；
通常不稳定⁠。

随机基准降低特定有序输入持续产生极端划分的概率⁠，但不能消除理论最坏情况⁠。

JavaScript 调用栈深度有限⁠，超大数组的递归实现可能抛出 RangeError⁠。高可靠实现可以⁠：

使用显式栈⁠；
优先递归较小分区⁠；
对小分区切换插入排序⁠；
使用三路划分处理大量重复值⁠；
使用内置排序⁠。

3.21 归并排序

归并排序将数组不断分成两半⁠，分别排序后合并⁠。

3.21.1 合并两个有序区间

function merge(
  left,
  right,
  compare,
) {
  const result = [];

  let leftIndex = 0;
  let rightIndex = 0;

  while (
    leftIndex < left.length
    && rightIndex < right.length
  ) {
    if (
      compare(
        left[leftIndex],
        right[rightIndex],
      ) <= 0
    ) {
      result.push(
        left[leftIndex],
      );

      leftIndex += 1;
    } else {
      result.push(
        right[rightIndex],
      );

      rightIndex += 1;
    }
  }

  while (
    leftIndex < left.length
  ) {
    result.push(
      left[leftIndex],
    );

    leftIndex += 1;
  }

  while (
    rightIndex < right.length
  ) {
    result.push(
      right[rightIndex],
    );

    rightIndex += 1;
  }

  return result;
}

3.21.2 递归排序

function mergeSort(
  array,
  compare = (
    first,
    second,
  ) => first - second,
) {
  if (
    array.length <= 1
  ) {
    return array.slice();
  }

  const middle
    = Math.floor(
      array.length / 2,
    );

  const left = mergeSort(
    array.slice(
      0,
      middle,
    ),
    compare,
  );

  const right = mergeSort(
    array.slice(middle),
    compare,
  );

  return merge(
    left,
    right,
    compare,
  );
}

复杂度⁠：

最好⁠、平均⁠、最坏⁠： $O(n\log n)$ ⁠；
辅助空间⁠： $O(n)$ ⁠；
稳定⁠；
返回新数组⁠。

教学实现使用 slice() 创建多个中间数组⁠，常数成本和内存分配较高⁠。高性能实现通常复用一个辅助缓冲区⁠。

3.22 排序算法对照

算法	最好时间	平均时间	最坏时间	辅助空间	稳定性
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	通常不稳定
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	平均 $O(\log n)$	通常不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定

表格对应本章给出的典型实现⁠。不同变体可能具有不同稳定性或空间特征⁠。

3.23 比较函数

通用排序函数应接受比较器⁠：

function compareNumbers(
  first,
  second,
) {
  return first - second;
}

对象排序⁠：

const students = [
  {
    name: "Alice",
    score: 90,
  },
  {
    name: "Bob",
    score: 80,
  },
];

students.toSorted(
  (
    first,
    second,
  ) => {
    return (
      first.score
      - second.score
    );
  },
);

比较器应满足一致的排序关系⁠。依赖随机数⁠、当前时间或不断变化的外部状态会使排序结果不可预测⁠。

3.24 线性查找

线性查找逐个检查元素⁠：

function linearSearch(
  array,
  target,
) {
  for (
    let index = 0;
    index < array.length;
    index += 1
  ) {
    if (
      Object.is(
        array[index],
        target,
      )
    ) {
      return index;
    }
  }

  return -1;
}

复杂度⁠：

最好⁠： $O(1)$ ⁠；
平均⁠： $O(n)$ ⁠；
最坏⁠： $O(n)$ ⁠；
辅助空间⁠： $O(1)$ ⁠。

它不要求数组有序⁠，适合⁠：

数据规模较小⁠；
只查找一次⁠；
数据无法预先排序⁠；
比较规则复杂⁠。

3.25 二分查找

二分查找要求序列已经按照同一比较规则排序⁠。

数组可以包含重复值⁠，不要求严格递增⁠。

function binarySearch(
  array,
  target,
  compare = (
    first,
    second,
  ) => first - second,
) {
  let low = 0;
  let high
    = array.length - 1;

  while (low <= high) {
    const middle = (
      low
      + Math.floor(
        (high - low) / 2,
      )
    );

    const comparison
      = compare(
        array[middle],
        target,
      );

    if (comparison === 0) {
      return middle;
    }

    if (comparison < 0) {
      low = middle + 1;
    } else {
      high = middle - 1;
    }
  }

  return -1;
}

复杂度⁠：

时间⁠： $O(\log n)$ ⁠；
辅助空间⁠： $O(1)$ ⁠。

3.25.1 不使用 >>> 计算中点

const middle
  = (low + high) >>> 1;

JavaScript 位运算会把操作数转换为 32 位整数⁠，超出范围时可能截断高位⁠。

3.25.2 重复元素

基本二分查找只保证返回某个匹配位置⁠。

查找第一个匹配⁠：

function findFirst(
  array,
  target,
) {
  let low = 0;
  let high
    = array.length - 1;

  let result = -1;

  while (low <= high) {
    const middle = (
      low
      + Math.floor(
        (high - low) / 2,
      )
    );

    if (
      array[middle] >= target
    ) {
      if (
        array[middle]
        === target
      ) {
        result = middle;
      }

      high = middle - 1;
    } else {
      low = middle + 1;
    }
  }

  return result;
}

同理可以查找最后一个匹配位置或插入边界⁠。

3.25.3 排序成本

如果数据无序⁠，只为一次查找先排序⁠：

O(n\log n)+O(\log n)=O(n\log n)

这通常不如直接线性查找的 $O(n)$ ⁠。

二分查找适合⁠：

数据本来就有序⁠；
排序一次后重复查询⁠；
数据更新频率较低⁠；
需要查找范围边界⁠。

3.26 递归

递归函数直接或间接调用自身⁠。

function factorial(n) {
  if (
    !Number.isInteger(n)
    || n < 0
  ) {
    throw new TypeError(
      "n 必须是非负整数",
    );
  }

  if (n <= 1) {
    return 1;
  }

  return (
    n * factorial(n - 1)
  );
}

3.26.1 两个必要部分

终止条件⁠；
把问题缩小的递归关系⁠。

缺少终止条件⁠：

function invalid() {
  return invalid();
}

最终通常导致调用栈溢出⁠。

3.26.2 递归复杂度

递归不必然是指数复杂度⁠。

阶乘⁠：

T(n)=T(n-1)+O(1)=O(n)

归并排序⁠：

T(n)=2T(n/2)+O(n)=O(n\log n)

朴素斐波那契⁠：

T(n)=T(n-1)+T(n-2)+O(1)

产生大量重复子问题⁠，时间呈指数增长⁠。

3.26.3 调用栈空间

线性深度递归通常需要 $O(n)$ 调用栈空间⁠。

JavaScript 引擎调用栈大小有限⁠，规范不保证所有实现都优化尾调用⁠。因此⁠，大规模线性问题通常应改为循环或显式栈⁠。

3.27 朴素递归斐波那契

function fibonacciRecursive(n) {
  if (
    n <= 1
  ) {
    return n;
  }

  return (
    fibonacciRecursive(
      n - 1,
    )
    + fibonacciRecursive(
      n - 2,
    )
  );
}

它重复计算相同状态⁠。

例如⁠，计算 $F_5$ 时⁠， $F_3$ ⁠、 $F_2$ 等会被多次调用⁠。

常用简单上界为⁠：

O(2^n)

更精确的增长与黄金比例相关⁠，但工程结论相同⁠：随着 $n$ 增大⁠，执行成本快速增长⁠。

3.28 记忆化

记忆化保存已经计算的状态⁠：

function fibonacciMemoized(n) {
  if (
    !Number.isInteger(n)
    || n < 0
  ) {
    throw new TypeError(
      "n 必须是非负整数",
    );
  }

  const memo = new Map([
    [0, 0],
    [1, 1],
  ]);

  function calculate(value) {
    if (memo.has(value)) {
      return memo.get(value);
    }

    const result = (
      calculate(value - 1)
      + calculate(value - 2)
    );

    memo.set(value, result);

    return result;
  }

  return calculate(n);
}

复杂度⁠：

时间⁠： $O(n)$ ⁠；
缓存⁠： $O(n)$ ⁠；
调用栈⁠： $O(n)$ ⁠。

记忆化是自顶向下动态规划的常见形式⁠。

3.29 自底向上递推

function fibonacciIterative(n) {
  if (
    !Number.isInteger(n)
    || n < 0
  ) {
    throw new TypeError(
      "n 必须是非负整数",
    );
  }

  if (n <= 1) {
    return n;
  }

  let previousTwo = 0;
  let previousOne = 1;

  for (
    let index = 2;
    index <= n;
    index += 1
  ) {
    const current = (
      previousTwo
      + previousOne
    );

    previousTwo
      = previousOne;

    previousOne
      = current;
  }

  return previousOne;
}

复杂度⁠：

时间⁠： $O(n)$ ⁠；
辅助空间⁠： $O(1)$ ⁠。

普通 Number 无法精确表示任意大的整数⁠。需要更大精确整数时可以使用 BigInt⁠：

function fibonacciBigInt(n) {
  let previousTwo = 0n;
  let previousOne = 1n;

  for (
    let index = 0;
    index < n;
    index += 1
  ) {
    [
      previousTwo,
      previousOne,
    ] = [
      previousOne,
      previousTwo
        + previousOne,
    ];
  }

  return previousTwo;
}

3.30 动态规划

动态规划常用于具有以下性质的问题⁠：

重叠子问题⁠；
最优子结构⁠；
可以定义有限状态并建立状态转移⁠。

一般步骤⁠：

定义状态⁠；
明确状态含义⁠；
推导转移关系⁠；
设置初始状态⁠；
确定计算顺序⁠；
输出目标状态⁠；
根据依赖范围优化空间⁠。

动态规划不等于“⁠使用二维数组⁠”⁠，也不等于“⁠所有递归都可以优化⁠”⁠。关键是问题能否通过复用有限子问题状态得到解⁠。

3.31 0-1 背包问题

有 $n$ 件物品⁠，第 $i$ 件物品重量为 $w_i$ ⁠，价值为 $v_i$ ⁠，背包容量为 $W$ ⁠。每件物品最多选择一次⁠。

3.31.1 二维状态

定义⁠：

dp[i][w]

表示只考虑前 $i$ 件物品⁠、容量为 $w$ 时的最大价值⁠。

初始状态⁠：

dp[0][w]=0

dp[i][0]=0

如果当前物品放不下⁠：

dp[i][w]=dp[i-1][w]

如果可以放入⁠：

dp[i][w]=\max\left(dp[i-1][w],dp[i-1][w-w_i]+v_i\right)

3.31.2 一维空间优化

function knapsack01(
  weights,
  values,
  capacity,
) {
  if (
    weights.length
    !== values.length
  ) {
    throw new RangeError(
      "weights 与 values 长度必须相同",
    );
  }

  if (
    !Number.isInteger(capacity)
    || capacity < 0
  ) {
    throw new TypeError(
      "capacity 必须是非负整数",
    );
  }

  const dp = new Array(
    capacity + 1,
  ).fill(0);

  for (
    let itemIndex = 0;
    itemIndex < weights.length;
    itemIndex += 1
  ) {
    const weight
      = weights[itemIndex];

    const value
      = values[itemIndex];

    if (
      !Number.isInteger(weight)
      || weight <= 0
    ) {
      throw new TypeError(
        "物品重量必须是正整数",
      );
    }

    for (
      let currentCapacity
        = capacity;
      currentCapacity >= weight;
      currentCapacity -= 1
    ) {
      dp[currentCapacity]
        = Math.max(
          dp[currentCapacity],
          dp[
            currentCapacity
            - weight
          ] + value,
        );
    }
  }

  return dp[capacity];
}

必须从大容量向小容量更新⁠，确保当前物品在本轮最多使用一次⁠。

如果从小到大更新⁠，本轮刚写入的状态可以再次被使用⁠，问题会变为完全背包模型⁠。

复杂度⁠：

时间⁠： $O(nW)$ ⁠；
辅助空间⁠： $O(W)$ ⁠。

该复杂度与容量数值 $W$ 成正比⁠，而不是与表示 $W$ 所需的位数成多项式关系⁠，因此通常称为伪多项式时间⁠。

3.32 最长递增子序列

给定序列⁠，寻找一个保持原相对顺序且严格递增的最长子序列⁠。

例如⁠：

[10, 9, 2, 5, 3, 7, 101, 18]

最长递增子序列长度为 4⁠，例如⁠：

[2, 3, 7, 18]

子序列不要求元素在原数组中连续⁠。

3.32.1 动态规划定义

令⁠：

dp[i]

表示以索引 $i$ 元素结尾的最长递增子序列长度⁠。

初始⁠：

dp[i]=1

转移⁠：

dp[i]=\max(dp[i],dp[j]+1),\qquad j<i,\ a_j<a_i

3.32.2 实现

function longestIncreasingSubsequenceLength(
  values,
) {
  if (
    values.length === 0
  ) {
    return 0;
  }

  const dp = new Array(
    values.length,
  ).fill(1);

  let best = 1;

  for (
    let right = 0;
    right < values.length;
    right += 1
  ) {
    for (
      let left = 0;
      left < right;
      left += 1
    ) {
      if (
        values[left]
        < values[right]
      ) {
        dp[right]
          = Math.max(
            dp[right],
            dp[left] + 1,
          );
      }
    }

    best = Math.max(
      best,
      dp[right],
    );
  }

  return best;
}

复杂度⁠：

时间⁠： $O(n^2)$ ⁠；
辅助空间⁠： $O(n)$ ⁠。

还存在基于二分查找的 $O(n\log n)$ 算法⁠。该方法维护不同长度递增子序列的最小可能尾值⁠，但中间数组本身通常不是最终的实际子序列⁠；如果需要恢复具体序列⁠，还要记录前驱信息⁠。

3.33 贪心⁠、分治与动态规划

3.33.1 分治

分治把问题拆为相对独立的子问题⁠，分别求解后合并⁠。

典型⁠：

归并排序⁠；
快速排序⁠；
二分查找⁠；
大整数乘法⁠；
最近点对⁠。

3.33.2 动态规划

动态规划处理具有重叠状态的子问题⁠，并保存结果避免重复计算⁠。

典型⁠：

0-1 背包⁠；
最长递增子序列⁠；
编辑距离⁠；
最短路径的某些算法⁠；
区间优化⁠。

3.33.3 贪心

贪心算法在每一步选择当前看来最优的决策⁠，并希望形成全局最优解⁠。

典型⁠：

某些活动选择问题⁠；
Huffman 编码⁠；
最小生成树⁠；
Dijkstra 算法在非负权边条件下⁠。

贪心策略必须证明具有正确性⁠。不能因为局部选择看起来合理⁠，就假定一定得到全局最优结果⁠。

3.34 算法选择

3.34.1 根据操作频率选择结构

高频需求	常见选择
按索引读取	数组
尾部压入和弹出	栈或数组
先进先出	队列
按动态键查找	Map
唯一性判断	Set
已知节点频繁连接和删除	链表
层级关系	树
一般网络关系	图
有序数据重复查找	二分查找
无权图最少边数	BFS
路径探索和回溯	DFS

3.34.2 考虑完整工作流程

不要只比较局部函数的复杂度⁠。

例如⁠，二分查找为 $O(\log n)$ ⁠，但如果数据无序且只查询一次⁠，先排序的总成本为 $O(n\log n)$ ⁠，可能不如直接线性查找⁠。

3.34.3 考虑数据规模

当 $n$ 很小时⁠：

代码简单程度⁠；
函数调用⁠；
内存分配⁠；
引擎优化⁠；
缓存局部性⁠。

可能比渐进量级更加重要⁠。

插入排序在小型或基本有序数组上可以非常实用⁠，即使最坏为 $O(n^2)$ ⁠。

3.34.4 考虑空间

时间和空间经常需要权衡⁠：

归并排序使用额外空间换取稳定的 $O(n\log n)$ ⁠；
记忆化使用缓存换取避免重复计算⁠；
哈希表使用额外桶空间换取快速查找⁠；
邻接矩阵使用 $O(V^2)$ 空间换取直接边查询⁠。

3.34.5 考虑可维护性

生产代码应优先使用清晰⁠、经过验证的内置方法⁠：

const sorted = values.toSorted(
  compare,
);

而不是为了展示算法自行实现复杂排序⁠。

自定义实现适合⁠：

学习⁠；
内置 API 无法满足特殊语义⁠；
已通过性能分析确认瓶颈⁠；
需要特定稳定性或空间约束⁠；
处理流式或外部存储数据⁠；
实现底层库⁠。

3.35 基准测试与复杂度

3.35.1 Big O 不能代替测量

Big O 回答增长趋势⁠，不能直接给出毫秒数⁠。

两个 $O(n)$ 算法可能具有完全不同的常数成本⁠。

3.35.2 测量环境

浏览器中可以使用⁠：

const start
  = performance.now();

operation();

const elapsed
  = performance.now() - start;

console.log(elapsed);

但严谨基准还需要考虑⁠：

JIT 预热⁠；
垃圾回收⁠；
CPU 频率⁠；
后台任务⁠；
数据分布⁠；
多次重复⁠；
统计波动⁠；
代码是否被优化掉⁠。

3.35.3 不要只测单个示例

排序算法应测试⁠：

随机数组⁠；
已排序数组⁠；
逆序数组⁠；
大量重复值⁠；
小数组⁠；
大数组⁠；
不同比较器⁠。

哈希结构应测试⁠：

均匀键⁠；
相似键⁠；
冲突⁠；
扩容⁠；
删除⁠；
长期内存占用⁠。

3.36 本章小结

本章从计算机科学视角介绍了 JavaScript 数据结构与算法的基础⁠：

数据结构描述数据关系⁠，抽象数据类型规定操作语义⁠，具体实现决定存储和性能⁠；
线性结构描述单一逻辑顺序⁠，并不要求物理存储连续⁠；
Big O 表示渐进上界⁠，工程讨论中常被宽松地用来表示主要增长量级⁠；
时间复杂度⁠、辅助空间⁠、最好情况⁠、平均情况⁠、最坏情况和均摊复杂度需要区分⁠；
ECMAScript 通常不规定内置集合必须采用的具体算法和严格逐次复杂度⁠；
数组适合顺序与索引访问⁠，Map 适合动态键值⁠，Set 适合唯一值和成员判断⁠；
数组尾部适合实现栈⁠，频繁队首删除应使用专门队列⁠；
队列基本操作在常见实现中可以达到平均或均摊常数成本⁠，但不应宣称 ECMAScript 保证严格 $O(1)$ ⁠；
链表支持低成本连接修改⁠，但按索引访问需要线性遍历⁠；
“⁠链表删除为 $O(1)$ ⁠”只在已经获得相关节点引用时成立⁠；
哈希表通过哈希函数与冲突处理实现快速平均查找⁠，极端冲突下会退化⁠；
负载因子过高时需要扩容和重新散列⁠，单次扩容为 $O(n)$ ⁠；
生产 JavaScript 通常应使用 Map⁠，而不是自行实现通用哈希表⁠；
树表示层级⁠，二叉树遍历包括前序⁠、中序⁠、后序和层序⁠；
二叉搜索树操作复杂度取决于树高⁠，普通二叉搜索树可能退化为链表⁠；
图可以使用邻接表或邻接矩阵表示⁠，二者具有不同空间与查询权衡⁠；
邻接表下 BFS 和 DFS 的时间复杂度通常为 $O(V+E)$ ⁠；
BFS 使用队列⁠，适合无权图最少边数⁠；DFS 使用栈或递归⁠，适合路径探索和回溯⁠；
冒泡⁠、选择和插入排序均具有 $O(n^2)$ 最坏时间⁠，但稳定性和适用输入不同⁠；
快速排序平均为 $O(n\log n)$ ⁠，最坏为 $O(n^2)$ ⁠，递归栈最坏为 $O(n)$ ⁠；
归并排序在所有主要情况下为 $O(n\log n)$ ⁠，稳定但需要 $O(n)$ 辅助空间⁠；
ECMAScript 要求内置数组排序稳定⁠，但不规定引擎采用哪种具体排序算法⁠；
二分查找要求数据已经按同一比较规则排序⁠，时间复杂度为 $O(\log n)$ ⁠；
JavaScript 中不应使用 >>> 计算可能超出 32 位范围的中间索引⁠；
递归复杂度取决于子问题数量与规模⁠，不必然为指数时间⁠；
JavaScript 调用栈有限⁠，大规模深递归应考虑循环或显式栈⁠；
记忆化通过缓存实现自顶向下动态规划⁠；
自底向上动态规划可以避免递归栈⁠，并可能进一步压缩状态空间⁠；
0-1 背包的一维实现必须从大容量向小容量更新⁠；
0-1 背包的 $O(nW)$ 属于伪多项式时间⁠；
最长递增子序列的基本动态规划为 $O(n^2)$ ⁠，还存在 $O(n\log n)$ 方法⁠；
分治⁠、动态规划和贪心是不同算法设计方法⁠，贪心策略需要证明正确性⁠；
算法选择应考虑完整工作流程⁠、数据规模⁠、空间⁠、数据分布和维护成本⁠；
Big O 不能代替真实基准测试⁠，性能优化必须基于测量⁠。

文章信息

目录

JavaScript 3. 数据结构与算法基础

3.1 数据结构与抽象数据类型

3.1.1 数据结构

3.1.2 抽象数据类型

3.1.3 线性与非线性结构

3.2 渐进复杂度

3.2.1 Big O⁠、Big Ω 与 Big Θ

3.2.2 常见增长量级

3.2.3 时间复杂度

3.2.4 辅助空间复杂度

3.2.5 最好⁠、平均与最坏情况

3.2.6 均摊复杂度

3.2.7 化简规则

3.2.8 JavaScript 内置方法的复杂度

3.3 JavaScript 内置集合与算法

3.3.1 Array

3.3.2 Map

3.3.3 Set

3.3.4 选择内置结构

3.4 栈

3.4.1 数组实现

3.4.2 括号匹配

3.4.3 典型应用

3.5 队列

3.5.1 不宜频繁使用 shift()

3.5.2 头尾索引实现

3.5.3 使用示例

3.5.4 典型应用

3.6 单向链表

3.6.1 基本实现

3.6.2 复杂度

3.6.3 与数组的权衡

3.7 双向链表

3.8 哈希表

3.8.1 哈希函数

3.8.2 哈希冲突

3.8.3 链地址法

3.8.4 负载因子与扩容

3.8.5 最坏情况

3.9 树

3.9.1 基本术语

3.9.2 二叉树

3.10 二叉树遍历

3.10.1 前序遍历

3.10.2 中序遍历

3.10.3 后序遍历

3.10.4 层序遍历

3.11 二叉搜索树

3.11.1 查找

3.11.2 平衡搜索树

3.12 图

3.12.1 分类

3.12.2 邻接表

3.12.3 邻接矩阵

3.13 广度优先搜索

3.14 深度优先搜索

3.14.1 递归实现

3.14.2 显式栈实现

3.14.3 BFS 与 DFS

3.15 排序算法

3.16 稳定排序

3.17 冒泡排序

3.18 选择排序

3.19 插入排序

3.20 快速排序

3.20.1 原地划分

3.20.2 复杂度

3.21 归并排序

3.21.1 合并两个有序区间

3.21.2 递归排序

3.22 排序算法对照

3.23 比较函数

3.24 线性查找

3.25 二分查找

3.25.1 不使用 >>> 计算中点

3.25.2 重复元素

3.25.3 排序成本

3.26 递归