数据结构与算法-1复杂度分析与数据信息

参考资料

• Hello 算法：https://www.hello-algo.com/

• 帅地：https://www.iamshuaidi.com/540.html

• https://dunwu.github.io/pages/133326

• 可视化：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

• 经典算法：https://github.com/nonstriater/Learn-Algorithms

• https://github.com/ls1248659692/leetcode

• 编码格式: https://blog.csdn.net/zhanghuaichao/article/details/77862037

写在前面

数据结构是存储数据的方式, 算法是处理数据的方法
两者密不可分, 正如著名的公式：

程序 = 数据结构 + 算法

我们可以把它们的关系类比为：

• 数据结构是 食材和厨具

  它决定了你“有什么可用”以及“操作的基本环境”

• 算法是 菜谱

  它描述的是“如何一步步做出成品”

• 程序则是最终做出来的 菜

学习数据结构与算法是为了解决实际问题，并且能够对 程序运行的效率和开销 进行优化

（一）数据结构是算法的基础

算法不能凭空操作数据, 它必须依赖于某种结构来组织和访问数据
数据结构直接决定了算法的 可行性 和 效率

• 【例子】查找一个元素

  如果数据存储在 数组 中（连续内存）, 可以使用 二分查找 算法（时间复杂度 O(log n)）, 效率很高
  如果数据存储在 链表 中（非连续内存, 只能顺序访问）, 只能使用 顺序查找 算法（时间复杂度 O(n)）

  所以如果选错了数据结构, 即使算法思想再精妙, 也无法高效运行

（二）算法是数据结构的灵魂

在已知能做什么的前提下, 怎么做最快、最省空间, 这就是算法要解决的问题

盲目自己刷题可能效果不显著，推荐先在开源社区查找一下有没有大神的刷题笔记
跟着他们的题单练习，一方面能看思路和解析，另一方面也比较有方向

复杂度分析

在算法设计中, 我们需要在给定的输入范围内求得问题的正确解
另一方面也追求 “既快又省”, 即算法运行时间短, 占用内存空间小

算法的特性

• 输入：算法具有 0 个或多个输入
• 输出：算法至少有 1 个或多个输出
• 有穷性：算法在有限的步骤之后会自动结束而 不会无限循环, 并且每一个步骤可以在 可接受的时间 内完成
• 确定性：算法中的每一步都有 确定的含义, 不会出现二义性
• 可行性：算法的 每一步都是可行的, 也就是说每一步都能够通过执行有限的次数来完成

时间复杂度

单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的
对于算法的时间性质和空间性质, 最重要的是其 数量级和趋势

时间复杂度使用 “Big O 记法”：$f(n) = O(g(n))$
在趋向无穷的极限意义下, 函数 f 的增长速度受到函数 g 的约束, 亦即函数 f 与函数 g 的特征相似

1

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

常量因子可以忽略不计, 故可以认为 $3n^{2}$ 和 $100n^{2}$ 属于同一个量级

• 最优 时间复杂度

  算法完成工作 最少 需要多少基本操作

• 最坏 时间复杂度

  算法完成工作 最多 需要多少基本操作

• 平均 时间复杂度

  算法完成工作 平均 需要多少基本操作

在没有特殊说明时, 我们所分析的算法的时间复杂度都是指 最坏时间复杂度

数组：随机访问 O(1), 插入删除 O(n)
链表：顺序访问 O(n), 插入删除 O(1)
（链表实际插入操作需要先找到位置, 整体时间复杂度可能仍是 O(n)）

时间复杂度不能只看循环层数, 要考虑每层操作次数

1
2
3
4
5

for i in range(n):    # O(n)
    for j in range(i, n):    # O(n/2)平均
        print(i, j)    # O(1)

# 时间复杂度为 O(n²)

1、基本操作, 即只有常数项, 认为其时间复杂度为 O(1)
2、顺序 结构, 时间复杂度按 加法 进行计算
3、循环 结构, 时间复杂度按 乘法 进行计算
4、分支 结构, 时间复杂度 取最大值
5、判断一个算法的效率时, 往往只需要 关注操作数量的最高次项, 其它次要项和常数项可以忽略

空间复杂度

用于衡量算法 占用内存空间 随着数据量变大时的 增长趋势

我们通常只关注 最差空间复杂度
这是因为内存空间是一项硬性要求, 我们必须确保在所有输入数据下都有足够的内存空间预留

假设有两个函数, 一个进行 循环 调用 myfunc() n 次, 另一个进行 递归 调用 myfunc() n 次
它们的时间复杂度都是 O(n), 但是前者在每轮调用函数后都返回并释放了栈帧空间, 因此空间复杂度仍为 O(1)
而后者在每轮调用函数后没有直接返回, 栈帧空间未被释放, 因此空间复杂度为 O(n)

降低时间复杂度通常需要以提升空间复杂度为代价, 反之亦然
要根据实际情况选择不同的优化方向

数据信息

数据元素之间不是独立的，存在特定的关系，这些关系便是 结构

• 逻辑结构

  揭示了数据元素之间的逻辑关系

  • 一对一的 线性 关系

    例如数组、链表、栈等

  • 一对多、多对多的 非线性 关系

    树形结构，图结构

• 物理结构

  涉及数据在计算机内存上的存储方式

  • 内存空间上是连续

    顺序存储的数组

  • 内存空间是分散

    链式存储的链表

基本数据类型

计算机中的数据形式各异，有文本、图片、视频、语音、3D 模型等
但是它们都由基本数据类型构成，以二进制的形式存储

• 整数类型（int, long）
• 浮点类型（float, double）
• 字符类型（char）
• 布尔类型（bool）
• 指针类型（pointer）

数字编码

原码、反码、补码

https://zhuanlan.zhihu.com/p/118432554

下列内容涉及模运算（Modular Arithmetic）
在计算机中，数值的表示是有限位数的（如 8 位、16 位、32 位等）
下面假设计算机二进制数为 8 位

• 原码
  -5 的原码即 1000 0101，首位为符号位，其余位用于表示值
  $2^0 + 2^1 + … + 2^6 = 2^7-1 = 127$，故原码的数值范围：$[-127, 127]$
  1000 0000 表示 −0，0000 0000 表示 +0，实际数值范围不包括 −128

• 反码
  正数的反码即原码
  负数的反码在原码的基础上，首位符号位不变，其余取反

  但是零存在歧义，+0 的反码即 0000 0000，-0 的反码即 1111 1111
  反码的正数范围：$[0, 2^7 - 1]$（即 $[0, 127]$）；负数范围：$[-2^7 + 1, -1]$（即 $[-127, -1]$）

• 补码
  正数的补码还是原码
  负数的补码在反码的基础上 加一

  补码的正数范围：0000 0000(0) 到 0111 1111(127) 共 128 个数
  负数范围：1000 0000(分配给-128) 到 1111 1111(-1) 共 128 个数

  如果 1000 0000 不表示 -128，那么 -128 就无法表示，导致数值范围不对称
  可以使用 1000 0000(补码) 进行加减法去验证其确实可以表示为 -128

通常反码和补码无法直接算出对应的十进制数值，需要先转换成原码

为什么机器使用的是补码？？？
对于人来说，我们知道原码的首位是符号位，然后对后面的真值进行加减运算

1
2
3
4

    0000 1011
-   0000 1000
-------------
         0011 = 3

而对于计算机来说，去辨别符号位会让计算机的基础电路设计变得十分复杂
根据运算法则，减去一个正数等于加上一个负数，即：$11 - 8 = 11 + (-8) = 3$
于是人们想出了 将符号位也参与运算 的方法

• 补码的主要优势
  • 简化加减法运算：补码允许加法和减法使用相同的硬件电路，无需区分符号位
  • 消除零的歧义：原码和反码中有 +0 和 -0 两种表示，补码中只有一种零的表示 0000 0000，1000 0000 表示 -128（在 8 位补码中）
  • 模运算性质：补码的加法可以自然地处理溢出，溢出位可以丢弃而不影响结果的正确性

下面举一个例子，计算 $11-8 = 11+(-8)$
让 首位符号位也参与运算

• 1、使用原码表示数

  1 2 3 4

  0000 1011(原码) + 1000 1000(原码) ------------------- 1001 0011(原码)

  该原码对应的十进制数即 -19。故原码进行减法运算会出现错误

• 2、使用反码表示数

  1 2 3 4

  0000 1011(反码) + 1111 0111(反码) ------------------- 1 0000 0010(反码) = 0000 0011(反码)

  这里涉及循环进位处理，最高位溢出时需要将进位加回最低位

  该反码首位符号位为 0，对应的原码与反码相同，得到十进制数即 +3，结果是正确的

• 3、使用补码表示数

  1 2 3 4

  0000 1011(补码) + 1111 1000(补码) ------------------- 1 0000 0011(补码) = 0000 0011(补码)

  因为补码的设计已经将符号位纳入数值的表示中，加法可以直接进行，溢出位可以丢弃
  得到 0000 0011，首位为 0, 正数的补码即原码，即 +3，正确

  补码的本质
  补码将负数表示为模减去其绝对值。对于 8 位二进制，模是 $2^8 = 256$，因此 $-x$ 的补码是 $256 - x$
  例如 $-8$ 的补码是 $256 - 8 = 248$，即 1111 1000
  当计算 $11-8$ 时，实际上是在计算 $11+248=259$，259 对 256 取模得到 3 即 0000 0011
  丢弃溢出位相当于自动进行取模运算

  也可以理解为补码的 符号位具有负权重（权重为 $-2^7$），因此可以直接计算真值：
  1111 1000 = $-2^7 + 2^6 + 2^5 + 2^4 + 2^3$ = $-128 + 64 + 32 + 16 + 8$ = $-8$

  而反码的模是 $2^8-1=255$（因为1111 1111被用于表示 -0），因此需要进行循环进位模拟对 255 取模的运算

字符编码

浮点数 IEEE 754 标准

IEEE 754 是 Institute of Electrical and Electronics Engineers（电气与电子工程师协会） 制定的二进制/十进制浮点数算术标准
是硬件、编程语言和数值库实现统一浮点运算的基石，包括以下内容：

1. 浮点数的表示形式（单精度、双精度、四倍精度等）
2. 算术运算的行为（加、减、乘、除、平方根）
3. 舍入模式、异常处理、特殊数值（NaN、∞）等细节

• 精度
  • 单精度（binary32）：1 位符号 + 8 位指数 + 23 位尾数
  • 双精度（binary64）：1 位符号 + 11 位指数 + 52 位尾数
  • 四倍精度（binary128）：1 位符号 + 15 位指数 + 112 位尾数

使用 bias（偏移）来表示正负指数
binary32 的 bias 为 127
binary64 的 bias 为 1023

特殊符号包括：±∞（正/负无穷）、NaN（Not‑a‑Number），分为 quiet NaN 与 signaling NaN、+0 / -0**（正负零）

• 舍入模式

  • 最近偶数（Round‑to‑nearest, ties‑to‑even）
  • 向零舍入（Round‑toward‑zero）
  • 向正无穷舍入（Round‑up）
  • 向负无穷舍入（Round‑down）

• 异常（Flags）

  • Invalid operation（无效操作）
  • Division by zero（除零）
  • Overflow（上溢）
  • Underflow（下溢）
  • Inexact（结果不精确）

• 编程语言注意点

  C/C++ 中的 float（binary32）和 double（binary64）遵循 IEEE 754
  Python 中的 float 实际上是 IEEE 754 双精度

  浮点数比较时不要直接使用 ==，应设定容差（epsilon）
  对于 累加、求和 等易产生误差的操作，可使用 Kahan 求和 或 高精度库
  使用标准库函数：isnan(x)、isinf(x)、signbit(x) 等，安全判断 NaN、∞、符号位

ASCII/Unicode/UTF-8 编码

base64 编码表

1
2
3
4

1234567890
abcdefghijklmnopqrstuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZ
+/

base58 编码表少了 6 个，分别是 0、大写 O、大写 I、小写 l、+、/