为什么要学习算法？

学算法并非为了工作中实现它，而是面对实际问题善于找到最优解。

人的知识越完备，经验越多，分析问题就越深入。

参考书目：《Hello algo》

基本概念

算法的定义

算法（algorithm）是一组指令或操作步骤，其特性包括：

  • 明晰的输入和输出
  • 可行性：有限步骤、有限时间和内存空间。
  • 幂等性：同样的输入始终相同的输出。

数据结构定义

数据结构（data structure）是组织和存储数据的方式，包括内容、关系、操作，其设计目标为：

  • 更小的空间
  • 更快的操作
  • 简洁的信息表示。

[!NOTE]

数据结构设计是一个权衡的过程，想要某方面提升，往往需要另一方面的损失。

数据结构的分类

按照逻辑结构划分，可分为“线性”和“非线性两大类”，非线性结构又可分为树形结构和网状结构。

树、堆、哈希表等元素之间一对多关系的结构，称为树形结构，而在图中，元素之间是多对多关系。

image-20260527143450292

按照物理结构划分，可分为连续空间（数组）存储结构和分散空间（链表）存储结构。物理结构反映了数据在计算机内存中的存储方式。所有的数据结构都是基于链表和数组或者两者的组合实现的。

image-20260527143908081

数据结构与算法的联系

image-20260509111458021

算法与数据结构结合才能高效解决实际问题，常说的算法实际上也包括了数据结构。

复杂度分析

算法的设计，分为两个步骤：

  1. 找到问题的解
  2. 寻找最优解

对于步骤一，毋庸置疑，算法需要正确的将满足条件的全部输入都能在规定时间内映射到输出空间。

对于步骤二，所谓最优，即空间效率和时间效率都处于较高水准，并且综合两个指标来看属于最优水平。

而有效评估算法效率，则需要复杂度分析。

复杂度分析的方法

复杂度分析主要有两种方法。

  • 实际测试：直接用测试用例运行两个方法，监控记录运行时间和内存占比。
    • 缺点：难以排除测试环境diff带来的干扰；完整测试依赖较多资源和时间。
  • 理论估算：通过计算来估算算法效率，也称为渐进复杂度分析（asymptotic complexity analysis）。

对于渐进复杂度分析，它描述了随着输入数据规模增加，算法时间和空间的增长趋势，而非具体值。

时间复杂度

时间复杂度不是算法运行时间，而是算法运行随数据量变大时的增长趋势。、

对于以下三个算法

void algorithm_A(int n) {
	cout << 0 << endl;
}

void algorithm_B(int n) {
  for (int i = 0; i < n; ++i) cout << 0 << endl;
}

void algorithm_C(int n) {
  for (int i = 0; i < 1000000; ++i) { cout << 0 << endl;}
}

A和C的复杂度都是常数阶，B与n成线性关系，被称为线性阶。

image-20260513114004712

时间复杂度的特点

  • 时间复杂度是有效的。随着数据的增大，复杂度高的算法执行时间一定会超过复杂度低的算法。
  • 时间复杂度便于统计。在分析时间复杂度的时候，可以将运行时间统一简化为操作数量统计，这样就避免了运行平台和运算类型带来的干扰。
  • 时间复杂度具有局限性。不能仅凭时间复杂度判断算法效率，因为实际生产环境中，数据的输入分布是受限的，就比如上图中的C算法，在输入数据量不超过100的情况下，是不如B算法的。

时间复杂度的表示

我们把算法的操作数量关于输入数据大小 $n$ 的函数，记为 $T(n)$，我们将时间复杂度记为 $O(n)$，后者是前者的渐进上界，即两者处于相同的增长级别，并且有以下关系：

image-20260513141542589

时间复杂度的推算步骤

  1. step 1:统计操作数量。要想求得 $O(n)$，我们必须先得到 $T(n)$，这需要我们逐行统计操作数量。在统计过程中，我们可以利用以下技巧简化计算：
    • 忽略常数。
    • 省略系数。
    • 循环且套时使用乘法。
  2. step 2:判断渐进上界。时间复杂度由 $T(n)$中最高阶的项来决定。当 $n$ 趋于无穷大时，最高项发挥主导作用。

常见类型的时间复杂度

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

image-20260513145437600

常数阶 $O(1)$

常数阶的操作数量与输入数据大小 $n$ 无关，不随着 $n$变化。

int constant(int n) {
	int count = 0;
	int size = 100000;
	for (int i = 0; i < size; ++i) ++count;
	return count;
}

线性阶 $O(n)$

线性阶的操作数量相对于输入数据大小以线性级别增长。

int linear(int n) {
	int count = 0;
	for (int i = 0; i < n; ++i) ++count;
	return count;
}

遍历数组和遍历链表等操作的时间复杂度均为 $O(n)$。

平方阶 $O(n^2)$

平方阶的操作数量相对于输入数据大小 $n$以平方级别增长。平方阶通常出现在循环嵌套中，比如下面的冒泡排序的例子。

int bubbleSort(vector<int>& nums) {
  int count = 0;
  for (int i = nums.size() - 1; i > 0; --i) {
    for (int j = 0; j < i; ++j) {
      if (nums[j] > nums[j + 1]) {
        int tmp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
        count += 3;
      }
    }
  }
  return count;
}

image-20260513150403211

指数阶 $O(2^n)$

指数主要出现在递归函数中，数据规模每增加1，操作数增加一倍。

int expRecur(int n) {
	if (n == 1) return 1;
	return expRecur(n - 1) + exprecur(n - 1) + 1;
}

image-20260513151531768

对数阶 $O(\log{n})$

对数阶与指数相反，数据规模每增加一倍，操作数增加1。对数阶也经常出现在递归函数中。

int logRecur(int n) {
	if (n <= 1) return 0;
	return logRecur(n/2) + 1;
}

image-20260513151923070

线性对数阶 $O(n\log{n})$

线性对数阶常出现在嵌套循环中，外层或内层一层$n$，一层 $\log{n}$ 。

int linearLogrecur(int n) {
  if (n <= 1) return 1;
  int count = linearLogRecur(n/2) + linearLogRecur（n/2);
  for (int i = 0; i < n; ++i) count++;
  return count;
}

image-20260513152055015

阶乘阶 $O(n!)$

阶乘对应数学上的全排列问题，通常也是使用递归实现。

int factorialRecur(int n) {
	if (n == 0) return 1;
	int count = 0;
	for (int i = 0; i < n; ++i) {
		count += factorialRecur(n - 1);
	}
	
	return count;
}

image-20260513152554067

当(n \geq 4)时恒有(n! > 2^{n}) ，因此阶乘阶比指数阶增长的更快。

最差、最佳、平均时间复杂度

算法的时间效率不是固定的，而是与输入数据的分布有关。

  • 最差时间复杂度对应函数渐进上界，用 $O$表示。最差时间复杂度更为常用，给出了一个效率安全值。
  • 最佳时间复杂度对应函数渐进下界，用 $\Omega$ 表示。
  • 平均时间复杂度可以体现算法在随机输入数据下的运行效率，用 $\Theta$ 表示（为了省事，常用 $O$代替），平均时间复杂度等于于数据分布下的整体数学期望，存在一定的计算难度，因此不常见。

空间复杂度

空间复杂度（space complexity）用于衡量算法占用内存空间随着数据量变大时的增长趋势。

算法与内存空间

算法在运行过程中，使用的内存空间主要包括以下三种：

  • 输入空间。输入空间用于存储算法的输入数据。
  • 暂存空间。暂存空间用于存储算法在运行过程中的变量、对象、函数上下文的数据。暂存空间可以进一步划分为三部分：
    • 暂存数据：用于保存算法在运行过程中的各种常量、变量和对象。
    • 栈帧空间：主要包括函数的上下文。系统调用函数时会在栈顶创建一个栈帧，函数返回后空间释放。
    • 指令空间：用于保存编译后的程序指令，通常极小，忽略不计。
  • 输出空间。输出空间用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是“暂存空间” + “输出空间”。

image-20260513154254241

空间复杂度的推算步骤

对于空间复杂度，只关注最差空间复杂度。 最差代表算法运行的峰值内存，并且也是对内存空间的硬性要求。

常见类型的空间复杂度。

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

image-20260513154630831

常数阶 $O(1)$

常数阶常见于与输入数据大小无关的算法。

int func() {
	return 0;
}

void constant(int n) {
	const int a = 0;
	int b = 0;
	vector<int> nums(10000);
	ListNode node(0);
	
	for (int i = 0; i < n; ++i) int c = 0;
	for (int i = 0; i < n; ++i) func();
}

线性阶 $O(n)$

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

void linear(int n) {
	vector<int> nums(n);
	vector<ListNode> nodes;
	for (int i = 0; i < n; ++i) {
		nodes.push_back(ListNodes(i));
	}
	
	unordered_map<int, string> map;
	for (int i = 0; i < n; ++i) {
		map[i] = to_string(i);
	}
}

对于以下递归函数，它的空间复杂度也是n

void linearRecur(int n) {
	if (n == 1) return;
  linearRecur(n - 1);
}

image-20260513155702085

平方阶 $O(n^2)$

平方常见于矩阵和图。

void quadratic(int n) {
  vector<vector<int>> numMatrix;
  for (int i = 0; i < n; ++i) {
    vector<int> tmp;
    for (int j = 0; j < n; ++j) tmp.push_back(0);
  }
  
  numMatrix.push_back(tmp);
}

以下递归函数，递归深度为 $n$，每个递归函数中初始化数组，平均长度为 $\frac{n}{2}$，总体空间复杂度也是 $O(n_2)$。

int quadraticrecur(int n) {
  if (n <= 0) return 0;
  vector<int> nums(n);
	cout << n << endl;
  return quadraticRecur(n - 1);
}

image-20260513160520311

指数阶 $O(2^n)$

指数阶常见于二叉树，层数为 $n$ 的“满二叉树” 的节点数量为 $2^n - 1$，占用 $O(2^n)$ 空间。

TreeNode* buildTree(int n) {
	if (n == 0) return nullptr;
	TreeNode* root = new TreeNode(0);
	root->left = buildTree(n - 1);
	root->right = buildTree(n - 1);
	return root;
}

image-20260513161237185

线性对数阶 $O(n\log{n})$

对数阶常见于分治算法，例如归并排序，输入长度为 $n$ 的数组，每轮递归将数组从中点处划分为两半，形成高度为 $logn$的递归树。

权衡时间与空间

实际生产环境中，降低时间复杂度通常以牺牲空间复杂度为代价，反之亦然。通常时间比空间更宝贵，因此以空间换时间是很常用的策略。

##