hello 算法笔记

最近开始看朋友推荐的hello算法，平时对算法都不太懂，看了这本书的其中一点，有一些还是写的很好的，起码对于算法小白的我，很多比方都比喻的特别好。这里记录下看整本书的笔记。

1. 前言

本书主要内容：

复杂度分析：数据结构和算法的评价维度与方法。时间复杂度、空间复杂度的推算方法、常见类型、示例等。
数据结构：基本数据类型，数据结构的分类方法。数组、链表、栈、队列、散列表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。
算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤、示例题目等

2. 初识

算法无处不在

查阅字典实际就是著名的『二分查找』。数据结构角度：字典为已排序的数组，算法角度：查字典过程即为二分查找

查阅字典。字典是按照拼音顺序排列的，假如需要查找首字母为r的字，通常是以下操作
1. 翻开字典大概一半的页数，查看首字母是什么，假设为m（l、m、n、o、p、q、r、s、t）
2. 因为r是在m之后，所以可以排除前半部分，查找范围缩小为了后半部分
3. 重复 1.和 2.，直到找到首字母为r的页码

整理扑克本质上就是『插入排序』算法，在处理小型数据集是很高效

整理扑克。在打扑克时，每一局都需要整理扑克牌，使其小到大排列，实现流程：
1. 将扑克牌划分为有序和无序两部分，并假设初始时，最左边的 1 张扑克已经有序
2. 在无序区间里取出一张插入至有序区间中的位置；完成后最左边 2 张扑克已经有序
3. 再从无序区间里取出一张插入至有序区间中的位置；完成后最左边 3 张扑克已经有序
4. 循环以上操作，至所有有序

下面的货币找零方案，从数据结构和算法角度看就是「贪心算法」。（每一步都采取当前看起来最好的选择）

货币找零：假设我们在超市购买了 69 元的商品，付给了收银员 100 元，收银员需要找回，他会很自然的油以下思考
1. 能找到的可选零钱包括 1 元、5 元、10 元、20 元
2. 从可选项中拿出最大的 20 元。剩余 31-20=11 元
3. 从剩余可选项中拿出 10 元。剩余 11-10=1 元
4. 从剩余可选项中拿出 1 元，剩余 1-1=0 元
5. 完成找零，方案为 20+10+1=31 元

算法是什么

算法定义

算法 Algorithm 是在有限时间内解决特定问题的一组指令或操作步骤。算法具有以下特性：

问题是明确的，包含清晰的输入和输出定义。
具有可行性，能够在有限步骤、时间和内存空间下完成。
各步骤都有确定的含义，相同的输入和运行条件下，输出始终相同。

数据结构定义

「数据结构 Data Structure」是计算机中组织和存储数据的方式。为了提高数据存储和操作性能，数据结构的设计目标包括：

空间占用尽量减少，节省计算机内存。
数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。
提供简洁的数据表示和逻辑信息，以便使得算法高效运行

数据结构和算法的关系

「数据结构」与「算法」高度相关且紧密结合，具体表现在：

数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及用于操作数据的方法。
算法是数据结构发挥的舞台。数据结构本身仅存储数据信息，通过结合算法才能解决特定问题。
特定算法通常有对应最优的数据结构。算法通常可以基于不同的数据结构进行实现，但最终执行效率可能相差很大。

如下：

数据结构与算法	LEGO 乐高
输入数据	未拼装的积木
数据结构	积木组织形式，包括形状、大小、连接方式等
算法	把积木拼成目标形态的一系列操作步骤
输出数据	积木模型

3. 复杂度

时间复杂度

运行时间可以直观且准确的反映算法的效率。怎样才算准确？1 确定运行平台、2 评论各个计算操作的时间、3 统计所有的计算操作时间，事实上，运行时间不能和运行平台绑定，其次每个操作的时间很难获取到。

所以「时间复杂度的分析」采取的统计是，算法运行时间随着数据量变大时的增长趋势

// 在某运行平台下的各个时间
// 1 + 1 + 10 + 1 + 5 ns
function algorithm(n) {
  var a = 2 // 1ns
  a = a + 1 // 1ns
  a = a * 2 // 10ns
  for (let i = 0; i < n; i++) {
    // 1ns
    console.log(0) // 5 ns
  }
}

:::

推算方法：统计操作数量、判断渐近上界

见 hello 算法

:::

时间复杂度常见类型

常见的时间复杂度类型（低到高）

常数阶 O(1)
对数阶 O(log n)
线性阶 O(n)
线性对数阶 O(n log n)
平方阶 O(n²)
指数阶 O(2 的 n 次方)
阶乘阶 O(n!)

常数介阶

常数阶的操作数量与输入数据大小 n 无关，即不会随便 n 的变化而变化

/* 常数阶 */
function constant(n) {
  let count = 0
  const size = 100000
  for (let i = 0; i < size; i++) count++
  return count
}

线性阶

线性阶的操作数量相对于输入数据大小以线性级别增长。线性阶通常出现在单层循环中。

/* 线性阶 */
// 操作数组或链表时，n为数组或链表的长度
function linear(n) {
  let count = 0
  for (let i = 0; i < n; i++) count++
  return count
}

平方阶

平方阶的操作数量相对于输入数据大小以平方级别增长。平方阶通常出现在嵌套循环中，外层循环和内层循环都为 O(n) ，因此总体为 O(n^2) 。

/* 平方阶 */
function quadratic(n) {
  let count = 0
  // 循环次数与数组长度成平方关系
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      count++
    }
  }
  return count
}

// 下面是常见的冒泡排序(平方阶)
function bubbleSort(nums) {
  let count = 0 // 计数器
  // 外循环：未排序区间为 [0, i]
  for (let i = nums.length - 1; i > 0; i--) {
    // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
    for (let j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        // 交换 nums[j] 与 nums[j + 1]
        let tmp = nums[j]
        nums[j] = nums[j + 1]
        nums[j + 1] = tmp
        count += 3 // 元素交换包含 3 个单元操作
      }
    }
  }
  return count
}

指数阶

生物学的“细胞分裂”是指数阶增长的典型例子：初始状态为 1 个细胞，分裂一轮后变为 2 个，分裂两轮后变为 4 个，以此类推，分裂 n 轮后有 2^n 个细胞。

指数阶增长非常迅速，在实际应用中通常是不可接受的。若一个问题使用「暴力枚举」求解的时间复杂度为 O(2^n) ，那么通常需要使用「动态规划」或「贪心算法」等方法来解决

/* 指数阶（循环实现） */
function exponential(n) {
  let count = 0,
    base = 1
  // cell 每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < base; j++) {
      count++
    }
    base *= 2
  }
  // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
  return count
}

// 实际算法中，指数阶常出现于递归函数
/* 指数阶（递归实现） */
function expRecur(n) {
  if (n === 1) return 1
  return expRecur(n - 1) + expRecur(n - 1) + 1
}

对数阶

与指数阶相反，对数阶反映了“每轮缩减到一半的情况”。对数阶仅次于常数阶，时间增长缓慢，是理想的时间复杂度。

对数阶常出现于「二分查找」和「分治算法」中，体现了一分为多和化繁为简的算法思想。

设输入数据大小为 n ，由于每轮缩减到一半，因此循环次数是 log_2 n ，即 2^n 的反函数。

/* 对数阶（循环实现） */
function logarithmic(n) {
  let count = 0
  while (n > 1) {
    n = n / 2
    count++
  }
  return count
}

// 与指数阶类似，对数阶也常出现于递归函数。以下代码形成了一个高度为 \(\log_2 n\) 的递归树
/* 对数阶（递归实现） */
function logRecur(n) {
  if (n <= 1) return 0
  return logRecur(n / 2) + 1
}

线性对数阶

线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 O(log n)和 O(n)

主流排序算法的时间复杂度通常为 O(n log n) 。例如：快速排序、归并排序、堆排序等。

/* 线性对数阶 */
function linearLogRecur(n) {
  if (n <= 1) return 1
  let count = linearLogRecur(n / 2) + linearLogRecur(n / 2)
  for (let i = 0; i < n; i++) {
    count++
  }
  return count
}

阶乘阶

对应数学上的「全排列问题」。见 hello 算法

阶乘通常使用递归实现。例如以下代码，第一层分裂出 n 个，第二层分裂出 n - 1 个，以此类推，直至第 n 层时终止分裂。

空间复杂度

空间复杂度用户衡量算法使用的内存空间随着数据量变大时的增长趋势。

通常情况下，空间复杂度统计范围是「暂存空间」+ 「输出空间」。

暂存空间进一步划分为：

「暂存数据」保存算法运行过程中的各种常量、变量、对象
「栈帧空间」用于保存调用函数的上下文数据。
「指令空间」用于保存编译后的程序指令，在实际统计中通常忽略不计。

因此，在分析一段程序的空间复杂度时，一般统计：暂存数据、输出数据、栈帧空间三部分。

推算方法

与时间复杂度大致相同。只是将统计对象从计算操作数量转为使用空间大小。不同的是，通常只关注「最差空间复杂度」（因为内存空间是一项硬性要求，我们必须确保在所有输入数据下都有足够的内存空间预留）

空间复杂度常见类型

常数阶
对数阶
线性阶
平方阶
指数阶

常数阶

常见于数量与输入数据大小无关的常量、变量、对象。（在循环中初始化变量或调用函数而占用的内存，在进入下一一循环后就会释放，不会累积占用空间，空间复杂度仍为 O(1)）

/* 常数阶 */
function constant(n) {
  // 常量、变量、对象占用 O(1) 空间
  const a = 0
  const b = 0
  const nums = new Array(10000)
  const node = new ListNode(0)
  // 循环中的变量占用 O(1) 空间
  for (let i = 0; i < n; i++) {
    const c = 0
  }
  // 循环中的函数占用 O(1) 空间
  for (let i = 0; i < n; i++) {
    constFunc()
  }
}

线性阶

常见于元素数量与 n 成正比的数组、链表、栈、队列等。 ???

/* 线性阶 */
function linear(n) {
  // 长度为 n 的数组占用 O(n) 空间
  const nums = new Array(n)
  // 长度为 n 的列表占用 O(n) 空间
  const nodes = []
  for (let i = 0; i < n; i++) {
    nodes.push(new ListNode(i))
  }
  // 长度为 n 的哈希表占用 O(n) 空间
  const map = new Map()
  for (let i = 0; i < n; i++) {
    map.set(i, i.toString())
  }
}
// 以下递归函数会同时存在 n 个未返回的 algorithm() 函数，使用 O(n) 大小的栈帧空间。
/* 线性阶（递归实现） */
function linearRecur(n) {
  console.log(`递归 n = ${n}`)
  if (n === 1) return
  linearRecur(n - 1)
}

平方阶

常见于矩阵和图，元素数量与 n 成平方关系。

指数阶

指数阶常见于二叉树。高度为 n 的「满二叉树」的节点数量为 2^n - 1，占用 O(2^n)空间。

/* 指数阶（建立满二叉树） */
function buildTree(n) {
  if (n === 0) return null
  const root = new TreeNode(0)
  root.left = buildTree(n - 1)
  root.right = buildTree(n - 1)
  return root
}

对数阶

常见于分治算法和数据类型转换

4. 数据结构

数据结构分类

逻辑结构：线性与非线性

非线性数据结构进一步划分：树形结构和网状结构。即：

线性结构：数组、链表、队列、栈、哈希表，元素存在一对一的顺序关系。
非线性结构：
- 树形结构：树、堆、哈希表，元素存在一对多的关系。
- 网状结构：图，元素存在多对多的关系

物理结构：连续与离散

见 hello 算法

5. 数组与链表

数组

「数组 Array」是线性结构，其将相同类型元素存储在连续的内存空间中。我们将在数组中的位置成为「索引 Index」

数组优点

在数组中访问元素非常高效。由于数组元素被存储在连续的内存空间中，计算数组元素的内存地址很容易。给定首尾元素的索引，可以使用以下公式计算该元素的内存地址，从而直接访问此元素。

// 元素内存地址 = 数组内存地址 + 元素长度 * 元素索引
elementAddr = firtstElementAddr + elementLength * elementIndex

TIP

为什么数组元素的索引要从 0 开始编号？

观察上图，我们发现数组首个元素的索引为 0，这似乎有些反直觉，因为从 1 开始计数会更自然。然而，从地址计算公式的角度看，索引本质上表示的是内存地址的偏移量。首个元素的地址偏移量是 0 ，因此索引为 0 也是合理的。

因为访问元素非常高效，所以可以在 O(1)时间内获取数组的任一元素。 arr[index]

数组缺点

数组在初始化后长度不可变。系统无法保证数组之后的内存空间是否可用，因此数组长度无法扩展，如若希望扩容数组，需新建数组，然后一次拷贝过去，数组很大时则会很耗时。

::: 请注意，JavaScript 的 Array 是动态数组，可以直接扩展为了方便学习，将 Array 看作是长度不可变的数组 :::

总结, 数组的插入与删除操作有以下缺点：

时间复杂度高：数组的插入和删除的平均时间复杂度均为 O(n) ，其中 n 为数组长度。丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是我们不关心的，但这样做同时也会造成内存空间的浪费。

hello 算法笔记

1. 前言

本书主要内容：

2. 初识

算法无处不在

算法是什么

算法定义

数据结构定义

数据结构和算法的关系

3. 复杂度

时间复杂度

时间复杂度常见类型

常数介阶

线性阶

平方阶

指数阶

对数阶

线性对数阶

阶乘阶

空间复杂度

推算方法

空间复杂度常见类型

常数阶

线性阶

平方阶

指数阶

对数阶

4. 数据结构

数据结构分类

逻辑结构：线性与非线性

物理结构：连续与离散

5. 数组与链表

数组

数组优点

数组缺点

6. 栈与队列

7. 散列表

8. 树

9. 堆

hello 算法笔记 ​

1. 前言 ​

本书主要内容： ​

2. 初识 ​

算法无处不在 ​

算法是什么 ​

算法定义 ​

数据结构定义 ​

数据结构和算法的关系 ​

3. 复杂度 ​

时间复杂度 ​

时间复杂度常见类型 ​

常数介阶 ​

线性阶 ​

平方阶 ​

指数阶 ​

对数阶 ​

线性对数阶 ​

阶乘阶 ​

空间复杂度 ​

推算方法 ​

空间复杂度常见类型 ​

常数阶 ​

线性阶 ​

平方阶 ​

指数阶 ​

对数阶 ​

4. 数据结构 ​

数据结构分类 ​

逻辑结构：线性与非线性 ​

物理结构：连续与离散 ​

5. 数组与链表 ​

数组 ​

数组优点 ​

数组缺点 ​

6. 栈与队列 ​

7. 散列表 ​

8. 树 ​

9. 堆 ​

hello 算法笔记

1. 前言

本书主要内容：

2. 初识

算法无处不在

算法是什么

算法定义

数据结构定义

数据结构和算法的关系

3. 复杂度

时间复杂度

时间复杂度常见类型

常数介阶

线性阶

平方阶

指数阶

对数阶

线性对数阶

阶乘阶

空间复杂度

推算方法

空间复杂度常见类型

常数阶

线性阶

平方阶

指数阶

对数阶

4. 数据结构

数据结构分类

逻辑结构：线性与非线性

物理结构：连续与离散

5. 数组与链表

数组

数组优点

数组缺点

6. 栈与队列

7. 散列表

8. 树

9. 堆