嘉兴服饰网站建设,wordpress后台编辑慢,设计师去哪个网站找工作,南京 网站建设参考引用 Hello 算法 Github 仓库#xff1a;hello-algo 1. 初识算法
1.1 算法无处不在
1.1.1 二分查找#xff1a;查阅字典
在字典里#xff0c;每个汉字都对应一个拼音#xff0c;而字典是按照拼音字母顺序排列的。假设我们需要查找一个拼音首字母为 r 的字#xff0… 参考引用 Hello 算法 Github 仓库hello-algo 1. 初识算法
1.1 算法无处不在
1.1.1 二分查找查阅字典
在字典里每个汉字都对应一个拼音而字典是按照拼音字母顺序排列的。假设我们需要查找一个拼音首字母为 r 的字通常会按下述步骤实现 翻开字典约一半的页数查看该页的首字母是什么假设首字母为 m由于在拼音字母表中 r 位于 m 之后所以排除字典前半部分查找范围缩小到后半部分不断重复上两步直至找到拼音首字母为 r 的页码为止
1.1.2 插入排序整理扑克
在打牌时每局都需要整理扑克牌使其从小到大排列实现流程如下 将扑克牌划分为 “有序” 和 “无序” 两部分并假设初始状态下最左 1 张扑克牌已经有序在无序部分抽出一张扑克牌插入至有序部分的正确位置完成后最左 2 张扑克已经有序不断循环步骤 2每一轮将一张扑克牌从无序部分插入至有序部分直至所有扑克牌都有序 1.1.3 贪心算法货币找零
假设在超市购买了 69 元的商品给了收银员 100 元则收银员需要找 31 元他会很自然地完成下面的思考 可选项是比 (31) 元面值更小的货币包括 (1) 元、(5) 元、(10) 元、(20) 元。从可选项中拿出最大的 20 元剩余 31 - 20 11 元从剩余可选项中拿出最大的 10 元剩余 11 - 10 1 元从剩余可选项中拿出最大的 1 元剩余 1 - 1 0 元完成找零方案为 20 10 1 31 元 以上每一步都采取当前看来最好的选择尽可能用大面额的货币最终得到了可行的找零方案这种方法本质上是 “贪心” 算法 1.2 算法是什么
1.2.1 算法定义
算法algorithm是在有限时间内解决特定问题的一组指令或操作步骤它具有以下特性 问题是明确的包含清晰的输入和输出定义具有可行性能够在有限步骤、时间和内存空间下完成各步骤都有确定的含义相同的输入和运行条件下输出始终相同
1.2.2 数据结构定义 数据结构data structure是计算机中组织和存储数据的方式具有以下设计目标 空间占用尽量减少节省计算机内存数据操作尽可能快速涵盖数据访问、添加、删除、更新等提供简洁的数据表示和逻辑信息以便使得算法高效运行 数据结构设计是一个充满权衡的过程。如果想要在某方面取得提升往往需要在另一方面作出妥协如 链表相较于数组在数据添加和删除操作上更加便捷但牺牲了数据访问速度图相较于链表提供了更丰富的逻辑信息但需要占用更大的内存空间
1.2.3 数据结构与算法的关系
数据结构与算法高度相关、紧密结合具体表现以下三个方面 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据以及用于操作数据的方法算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息结合算法才能解决特定问题算法通常可以基于不同的数据结构进行实现但执行效率可能相差很大选择合适的数据结构是关键 数据结构与算法是独立于编程语言的 将数据结构与算法类比为积木
2. 数据结构
2.1 数据结构分类
常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图它们可以从 “逻辑结构” 和 “物理结构” 两个维度进行分类
2.1.1 逻辑结构线性与非线性 逻辑结构揭示了数据元素之间的逻辑关系 在数组和链表中数据按照顺序依次排列体现了数据之间的线性关系在树中数据从顶部向下按层次排列表现出祖先与后代之间的派生关系图则由节点和边构成反映了复杂的网络关系 如下图所示逻辑结构可被分为 “线性” 和 “非线性” 两大类。线性结构比较直观指数据在逻辑关系上呈线性排列非线性结构则相反呈非线性排列 线性数据结构数组、链表、栈、队列、哈希表非线性数据结构树、堆、图、哈希表 非线性数据结构可以进一步被划分为树形结构和网状结构 线性结构数组、链表、队列、栈、哈希表元素之间是一对一的顺序关系树形结构树、堆、哈希表元素之间是一对多的关系网状结构图元素之间是多对多的关系 2.1.2 物理结构连续与分散 在计算机中内存和硬盘是两种主要的存储硬件设备 内存用于运行程序时暂存数据速度较快但容量较小通常为 GB 级别硬盘主要用于长期存储数据容量较大但速度较慢通常可达到 TB 级别 在算法运行过程中相关数据都存储在内存中 下图展示了一个计算机内存条其中每个黑色方块都包含一块内存空间。可以将内存想象成一个巨大的 Excel 表格其中每个单元格都可以存储一定大小的数据在算法运行时所有数据都被存储在这些单元格中 系统通过内存地址来访问目标位置的数据 如下图所示计算机根据特定规则为表格中的每个单元格分配编号确保每个内存空间都有唯一的内存地址。有了这些地址程序便可以访问内存中的数据 内存是所有程序的共享资源当某块内存被某个程序占用时则无法被其他程序同时使用了。因此在数据结构与算法的设计中内存资源是一个重要的考虑因素 算法所占用的内存峰值不应超过系统剩余空闲内存如果缺少连续大块的内存空间那么所选用的数据结构必须能够存储在分散的内存空间内 如下图物理结构反映了数据在计算机内存中的存储方式可分为连续空间存储数组和分散空间存储链表。物理结构从底层决定了数据的访问、更新、增删等操作方法同时在时间效率和空间效率方面呈现出互补的特点 所有数据结构都是基于数组、链表或二者的组合实现的。例如栈和队列既可以使用数组实现也可以使用链表实现而哈希表的实现可能同时包含数组和链表 基于数组可实现栈、队列、哈希表、树、堆、图、矩阵、张量等 基于数组实现的数据结构也被称为 “静态数据结构”这意味着此类数据结构在初始化后长度不可变 基于链表可实现栈、队列、哈希表、树、堆、图等 基于链表实现的数据结构被称为 “动态数据结构”这类数据结构在初始化后仍可以在程序运行过程中对其长度进行调整
2.2 基本数据结构 基本数据类型是 CPU 可以直接进行运算的类型在算法中直接被使用主要包括以下几种类型 整数类型 byte、short、int、long浮点数类型 float、double用于表示小数字符类型 char用于表示各种语言的字母、标点符号、甚至表情符号等布尔类型 bool用于表示 “是” 与 “否” 判断 基本数据类型以二进制的形式存储在计算机中 一个二进制位即为 1 比特。在绝大多数现代系统中1 字节byte由 8 比特bits组成
3. 复杂度分析
3.1 算法效率评估 在能够解决问题的前提下算法效率是衡量算法优劣的主要评价指标它包括以下两个维度 时间效率算法运行速度的快慢空间效率算法占用内存空间的大小 效率评估方法主要分为两种实际测试、理论估算
3.1.1 实际测试
假设有算法 A 和算法 B它们都能解决同一问题现在对比这两个算法的效率最直接的方法是找一台计算机运行这两个算法并监控记录它们的运行时间和内存占用情况。这种评估方式能够反映真实情况但也存在较大局限性 一方面难以排除测试环境的干扰因素。硬件配置会影响算法的性能表现。比如在某台计算机中算法 A 的运行时间比算法 B 短但在另一台配置不同的计算机中可能得到相反的测试结果另一方面展开完整测试非常耗费资源。随着输入数据量的变化算法会表现出不同的效率。例如在输入数据量较小时算法 A 的运行时间比算法 B 更少而输入数据量较大时测试结果可能恰恰相反
3.1.2 理论估算 可以考虑仅通过一些计算来评估算法的效率。这种估算方法被称为渐近复杂度分析 asymptotic complexity analysis简称复杂度分析 复杂度分析体现算法运行所需的时间空间资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加算法执行所需时间和空间的增长趋势 “时间和空间资源” 分别对应时间复杂度和空间复杂度“随着输入数据大小的增加” 意味着复杂度反映了算法运行效率与输入数据体量之间的关系“时间和空间的增长趋势” 表示复杂度分析关注的不是运行时间或占用空间的值而是时间或空间增长的 “快慢”
3.2 迭代与递归
3.2.1 迭代
迭代iteration是一种重复执行某个任务的控制结构 在迭代中程序会在满足一定的条件下重复执行某段代码直到这个条件不再满足
for 循环
for 循环是最常见的迭代形式之一适合预先知道迭代次数时使用 以下函数基于 for 循环实现了求和 1 2 … n求和结果使用变量 res 记录 int forLoop(int n) {int res 0;for (int i 1; i n; i) {res i;}return res;
}while 循环
与 for 循环类似while 循环也是一种实现迭代的方法。在 while 循环中程序每轮都会先检查条件如果条件为真则继续执行否则就结束循环 while 循环中初始化和更新条件变量的步骤独立在循环结构之外因此比 for 循环的自由度更高下面的条件变量 i 每轮进行了两次更新这种情况就不太方便用 for 循环实现 /* while 循环两次更新 */
int whileLoopII(int n) {int res 0;int i 1; // 初始化条件变量// 循环求和 1, 4, ...while (i n) {res i;// 更新条件变量i;i * 2;}return res;
}嵌套循环
可以在一个循环结构内嵌套另一个循环结构以 for 循环为例/* 双层 for 循环 */
string nestedForLoop(int n) {ostringstream res;// 循环 i 1, 2, ..., n-1, nfor (int i 1; i n; i) {// 循环 j 1, 2, ..., n-1, nfor (int j 1; j n; j) {res ( i , j ), ;}}return res.str();
}3.2.2 递归 递归recursion是一种算法策略通过函数调用自身来解决问题它主要包含两个阶段 递程序不断深入地调用自身通常传入更小或更简化的参数直到达到 “终止条件”归触发 “终止条件” 后程序从最深层的递归函数开始逐层返回汇聚每一层的结果 从实现的角度看递归代码主要包含三个要素 终止条件用于决定什么时候由 “递” 转 “归”递归调用对应 “递”函数调用自身通常输入更小或更简化的参数返回结果对应 “归”将当前递归层级的结果返回至上一层 只需调用函数 recur(n) 就可以完成 1 2 … n 的计算 int recur(int n) {// 终止条件if (n 1)return 1;// 递递归调用int res recur(n - 1);// 归返回结果return n res;
}调用栈
递归函数每次调用自身时系统都会为新开启的函数分配内存以存储局部变量、调用地址和其他信息等这将导致两方面的结果 函数的上下文数据都存储在称为 “栈帧空间” 的内存区域中直至函数返回后才会被释放。因此递归通常比迭代更加耗费内存空间递归调用函数会产生额外的开销因此递归通常比循环的时间效率更低 上述代码的递归深度为 n实际的递归深度通常是有限的过深的递归可能导致栈溢出报错事实上“调用栈” 和 “栈帧空间” 这类递归术语已经暗示了递归与栈之间的密切关系 递当函数被调用时系统会在 “调用栈” 上为该函数分配新的栈帧用于存储函数的局部变量、参数、返回地址等数据归当函数完成执行并返回时对应的栈帧会从 “调用栈” 上被移除恢复之前函数的执行环境
尾递归
如果函数在返回前的最后一步才进行递归调用则该函数可以被编译器或解释器优化使其在空间效率上与迭代相当。这种情况被称为尾递归tail recursion普通递归 当函数返回到上一层级的函数后需要继续执行代码因此系统需要保存上一层调用的上下文求和操作是在 “归” 的过程中执行的每层返回后都要再执行一次求和操作 尾递归 递归调用是函数返回前的最后一个操作这意味着函数返回到上一层级后无需继续执行其他操作因此系统无需保存上一层函数的上下文求和操作是在 “递” 的过程中执行的“归” 的过程只需层层返回 int tailRecur(int n, int res) {// 终止条件if (n 0)return res;// 尾递归调用return tailRecur(n - 1, res n);
}递归树
当处理与 “分治” 相关的算法问题时递归往往比迭代的思路更加直观、代码更加易读以 “斐波那契数列” 为例给定一个斐波那契数列 0, 1, 1, 2, 3, 5, 8, 13, … 求该数列的第 n 个数字 设斐波那契数列的第 n 个数字为 f(n)易得两个结论 数列的前两个数字为 f(1) 0 和 f(2) 1数列中的每个数字是前两个数字的和即 f(n) f(n - 1) f(n - 2) 按照递推关系进行递归调用将前两个数字作为终止条件便可写出递归代码。调用 fib(n) 即可得到斐波那契数列的第 n 个数字 int fib(int n) {// 终止条件 f(1) 0, f(2) 1if (n 1 || n 2)return n - 1;// 递归调用 f(n) f(n-1) f(n-2)int res fib(n - 1) fib(n - 2);// 返回结果 f(n)return res;
}上述代码在函数内递归调用了两个函数这意味着从一个调用产生了两个调用分支。如下图所示这样不断递归调用下去最终将产生一个层数为 n 的递归树recursion tree
3.2.3 两者对比
迭代“自下而上” 地解决问题 从最基础的步骤开始然后不断重复或累加这些步骤直到任务完成从 1 遍历到 n每轮执行求和操作即可求得 f(n) 递归“自上而下” 地解决问题 将原问题分解为更小的子问题这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题直到基本情况时停止基本情况的解是已知的将问题分解为子问题 f(n) n f(n-1) 不断递归地分解下去直至基本情况 f(1) 1 时终止 3.3 时间复杂度
3.3.1 统计时间增长趋势
时间复杂度分析统计的不是算法运行时间而是算法运行时间随着数据量变大时的增长趋势假设输入数据大小为 n 给定三个算法函数 A、B 和 C// 算法 A 的时间复杂度常数阶
void algorithm_A(int n) {cout 0 endl;
}
// 算法 B 的时间复杂度线性阶
void algorithm_B(int n) {for (int i 0; i n; i) {cout 0 endl;}
}
// 算法 C 的时间复杂度常数阶
void algorithm_C(int n) {for (int i 0; i 1000000; i) {cout 0 endl;}
}下图展示了以上三个算法函数的时间复杂度 算法 A 只有 1 个打印操作算法运行时间不随着 n 增大而增长。称此算法的时间复杂度为 “常数阶”算法 B 中的打印操作需要循环 n 次算法运行时间随着 n 增大呈线性增长。此算法的时间复杂度被称为 “线性阶”算法 C 中的打印操作需要循环 1000000 次虽然运行时间很长但它与输入数据大小 n 无关。因此 C 的时间复杂度和 A 相同仍为 “常数阶” 相较于直接统计算法运行时间时间复杂度分析有哪些特点 时间复杂度能够有效评估算法效率 算法 B 的运行时间呈线性增长在 n 1 时比算法 A 更慢在 n 1000000 时比算法 C 更慢 时间复杂度的推算方法更简便 运行平台和计算操作类型都与算法运行时间的增长趋势无关 时间复杂度也存在一定的局限性 尽管算法 B 的时间复杂度比 C 高但在输入数据大小 n 较小时算法 B 明显优于算法 C
3.3.2 函数渐近上界 给定一个输入大小为 n 的函数 void algorithm(int n) {int a 1; // 1a a 1; // 1a a * 2; // 1// 循环 n 次for (int i 0; i n; i) { // 1每轮都执行 icout 0 endl; // 1}
}设算法的操作数量是一个关于输入数据大小 n 的函数记为 T(n)则以上函数的的操作数量为T(n) 3 2n T(n) 是一次函数说明其运行时间的增长趋势是线性的因此它的时间复杂度是线性阶将线性阶的时间复杂度记为 O(n)这个数学符号称为大 O 记号表示函数 T(n) 的渐近上界 计算渐近上界就是寻找一个函数 f(n)使得当 n 趋向于无穷大时T(n) 和 f(n) 处于相同的增长级别仅相差一个常数项 c 的倍数
3.3.3 推算方法
确定 f(n) 之后我们便可得到时间复杂度 O(f(n))。那么如何确定渐近上界 f(n) 呢总体分为两步
第一步统计操作数量
针对代码逐行从上到下计算即可。然而由于上述 c·f(n) 中的常数项 c 可以取任意大小因此操作数量 T(n) 中的各种系数、常数项都可以被忽略。根据此原则可以总结出以下计数简化技巧 1. 忽略 T(n) 中的常数项 因为它们都与 n 无关所以对时间复杂度不产生影响 2. 省略所有系数 例如循环 2n 次、5n 1 次等都可简记为 n 次因为 n 前面的系数对时间复杂度没有影响 3. 循环嵌套时使用乘法 总操作数量等于外层循环和内层循环操作数量之积每一层循环依然可以分别套用第 1 点和第 2 点的技巧 // 时间复杂度O(n^2)
void algorithm(int n) {int a 1; // 0技巧 1a a n; // 0技巧 1// n技巧 2for (int i 0; i 5 * n 1; i) {cout 0 endl;}// n*n技巧 3for (int i 0; i 2 * n; i) {for (int j 0; j n 1; j) {cout 0 endl;}}
}第二步判断渐近上界
时间复杂度由多项式 T(n) 中最高阶的项来决定。这是因为在 n 趋于无穷大时最高阶的项将发挥主导作用其他项的影响都可以被忽略 下表展示了一些例子其中一些夸张的值是为了强调 “系数无法撼动阶数” 这一结论。当 n 趋于无穷大时这些常数变得无足轻重
3.3.4 常见类型 常数阶 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) 线性阶的操作数量相对于输入数据大小 n 以线性级别增长通常出现在单层循环中 int linear(int n) {int count 0;for (int i 0; i n; i) {count;}return count;
}遍历数组和遍历链表等操作的时间复杂度均为 O(n) 其中 n 为数组或链表的长度 int arrayTraversal(vectorint nums) {int count 0;// 循环次数与数组长度成正比for (int num : nums) {count;}return count;
}平方阶 O(n^2)
平方阶的操作数量相对于输入数据大小 n 以平方级别增长。平方阶通常出现在嵌套循环中外层循环和内层循环都为 O(n)因此总体为 O(n^2)int quadratic(int n) {int count 0;// 循环次数与数组长度成平方关系for (int i 0; i n; i) {for (int j 0; j n; j) {count;}}return count;
}指数阶 O(2^n)
生物学的 “细胞分裂” 是指数阶增长的典型例子初始状态为 1 个细胞分裂一轮后变为 2 个分裂两轮后变为 4 个以此类推分裂 n 轮后有 2^n 个细胞。下图和代码模拟了细胞分裂的过程时间复杂度为 O(2^n)/* 指数阶循环实现 */
int exponential(int n) {int count 0, base 1;// 细胞每轮一分为二形成数列 1, 2, 4, 8, ..., 2^(n-1)for (int i 0; i n; i) {for (int j 0; j base; j) {count;}base * 2;}// count 1 2 4 8 .. 2^(n-1) 2^n - 1return count;
}在实际算法中指数阶常出现于递归函数中。例如在以下代码中其递归地一分为二经过 n 次分裂后停止/* 指数阶递归实现 */
int expRecur(int n) {if (n 1)return 1;return expRecur(n - 1) expRecur(n - 1) 1;
}指数阶增长非常迅速在穷举法暴力搜索、回溯等中比较常见。对于数据规模较大的问题指数阶是不可接受的通常需要使用动态规划或贪心等算法来解决 对数阶 O(log n)
与指数阶相反对数阶反映了 “每轮缩减到一半” 的情况。设输入数据大小为 n由于每轮缩减到一半因此循环次数是 log_2 n 即 2^n 的反函数。下图和代码模拟了 “每轮缩减到一半” 的过程时间复杂度为 O(\log_2 n) 简记为 O(\log n)/* 对数阶循环实现 */
int logarithmic(float n) {int count 0;while (n 1) {n n / 2;count;}return count;
}与指数阶类似对数阶也常出现于递归函数中。以下代码形成了一个高度为 log_2 n 的递归树/* 对数阶递归实现 */
int logRecur(float n) {if (n 1)return 0;return logRecur(n / 2) 1;
}对数阶常出现于基于分治策略的算法中体现了 “一分为多” 和 “化繁为简” 的算法思想。它增长缓慢是仅次于常数阶的理想的时间复杂度 线性对数阶 O(n log n) 线性对数阶常出现于嵌套循环中两层循环的时间复杂度分别为 O(log n) 和 O(n) int linearLogRecur(float n) {if (n 1)return 1;int count linearLogRecur(n / 2) linearLogRecur(n / 2);for (int i 0; i n; i) {count;}return count;
}二叉树的每一层操作总数都为 n 树共有 log_2 n 1 层因此时间复杂度为 O(n log n) 主流排序算法的时间复杂度通常为 O(n log n)例如快速排序、归并排序、堆排序等 阶乘阶 O(n!)
阶乘阶对应数学上的 “全排列” 问题阶乘通常使用递归实现。如下图和代码所示第一层分裂出 n 个第二层分裂出 n - 1 个以此类推直至第 n 层时停止分裂/* 阶乘阶递归实现 */
int factorialRecur(int n) {if (n 0)return 1;int count 0;// 从 1 个分裂出 n 个for (int i 0; i n; i) {count factorialRecur(n - 1);}return count;
}阶乘阶比指数阶增长得更快在 n 较大时也是不可接受的 3.3.5 最差、最佳和平均时间复杂度
算法的时间效率往往不是固定的而是与输入数据的分布有关。假设输入一个长度为 n 的数组 nums其中 nums 由从 1 至 n 的数字组成每个数字只出现一次但元素顺序是随机打乱的任务目标是返回元素 1 的索引可以得出 当 nums [?, ?, …, 1] 即当末尾元素是 1 时需要完整遍历数组达到最差时间复杂度 O(n) “最差时间复杂度” 对应函数渐近上界使用大 O 记号表示 当 nums [1, ?, ?, …] 即当首个元素为 1 时无论数组多长都不需要继续遍历达到最佳时间复杂度 Omega(1) “最佳时间复杂度” 对应函数渐近下界用 Omega 记号表示 在实际中很少使用最佳时间复杂度因为通常只有在很小概率下才能达到可能会带来一定的误导性。而最差时间复杂度更为实用因为它给出了一个效率安全值
3.4 空间复杂度
空间复杂度用于衡量算法占用内存空间随着数据量变大时的增长趋势
3.4.1 算法相关空间 算法在运行过程中使用的内存空间主要包括以下几种 输入空间用于存储算法的输入数据暂存空间用于存储算法在运行过程中的变量、对象、函数上下文等数据输出空间用于存储算法的输出数据 一般情况下空间复杂度的统计范围是 “暂存空间” 加上 “输出空间” 暂存空间可以进一步划分为三个部分 暂存数据用于保存算法运行过程中的各种常量、变量、对象等栈帧空间用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧函数返回后栈帧空间会被释放指令空间用于保存编译后的程序指令在实际统计中通常忽略不计 在分析一段程序的空间复杂度时通常统计暂存数据、栈帧空间和输出数据三部分 struct Node {int val;Node *next;Node(int x) : val(x), next(nullptr) {}
};int func() {// 执行某些操作...return 0;
}int algorithm(int n) { // 输入数据const int a 0; // 暂存数据常量int b 0; // 暂存数据变量Node* node new Node(0); // 暂存数据对象int c func(); // 栈帧空间调用函数return a b c; // 输出数据
}3.4.2 推算方法 通常只关注最差空间复杂度因为内存空间是一项硬性要求必须确保在所有输入数据下都有足够的内存空间预留 在递归函数中需要注意统计栈帧空间 函数 loop() 在循环中调用了 n 次 func() 每轮中的 func() 都返回并释放了栈帧空间因此空间复杂度仍为 O(1)递归函数 recur() 在运行过程中会同时存在 n 个未返回的 recur()从而占用 O(n) 的栈帧空间 int func() {// 执行某些操作return 0;
}
/* 循环 O(1) */
void loop(int n) {for (int i 0; i n; i) {func();}
}
/* 递归 O(n) */
void recur(int n) {if (n 1) return;return recur(n - 1);
}3.4.3 常见类型 常数阶 O(1)
常数阶常见于数量与输入数据大小 n 无关的常量、变量、对象。在循环中初始化变量或调用函数而占用的内存在进入下一循环后就会被释放因此不会累积占用空间空间复杂度仍为 O(1)int func() {// 执行某些操作return 0;
}void constant(int n) {// 常量、变量、对象占用 O(1) 空间const int a 0;int b 0;vectorint nums(10000);ListNode node(0);// 循环中的变量占用 O(1) 空间for (int i 0; i n; i) {int c 0;}// 循环中的函数占用 O(1) 空间for (int i 0; i n; i) {func();}
}线性阶 O(n)
线性阶常见于元素数量与 n 成正比的数组、链表、栈、队列等void linear(int n) {// 长度为 n 的数组占用 O(n) 空间vectorint nums(n);// 长度为 n 的列表占用 O(n) 空间vectorListNode nodes;for (int i 0; i n; i) {nodes.push_back(ListNode(i));}// 长度为 n 的哈希表占用 O(n) 空间unordered_mapint, string map;for (int i 0; i n; i) {map[i] to_string(i);}
}如下图所示此函数的递归深度为 n即同时存在 n 个未返回的 linear_recur() 函数使用 O(n) 大小的栈帧空间/* 线性阶递归实现 */
void linearRecur(int n) {cout 递归 n n endl;if (n 1)return;linearRecur(n - 1);
}平方阶 O(n^2)
平方阶常见于矩阵和图元素数量与 n 成平方关系void quadratic(int n) {// 二维列表占用 O(n^2) 空间vectorvectorint numMatrix;for (int i 0; i n; i) {vectorint tmp;for (int j 0; j n; j) {tmp.push_back(0);}numMatrix.push_back(tmp);}
}如下图所示该函数的递归深度为 n在每个递归函数中都初始化了一个数组长度分别为 n、n-1、…、2、1平均长度为 n / 2 因此总体占用 O(n^2) 空间/* 平方阶递归实现 */
int quadraticRecur(int n) {if (n 0)return 0;vectorint nums(n);cout 递归 n n 中的 nums 长度 nums.size() endl;return quadraticRecur(n - 1);
}指数阶 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;
}对数阶 O(log n)
对数阶常见于分治算法 例如归并排序输入长度为 n 的数组每轮递归将数组从中点划分为两半形成高度为 log n 的递归树使用 O(log n) 栈帧空间再例如将数字转化为字符串输入一个正整数 n 它的位数为 log_{10} n 1 即对应字符串长度为 log_{10} n 1因此空间复杂度为 O(log_{10} n 1) O(log n)
3.4.4 权衡时间与空间
理想情况下希望算法的时间复杂度和空间复杂度都能达到最优但实际非常困难降低时间复杂度通常需要以提升空间复杂度为代价反之亦然 将牺牲内存空间来提升算法运行速度的思路称为 “以空间换时间”反之则称为 “以时间换空间”在大多数情况下时间比空间更宝贵因此 “以空间换时间” 通常是更常用的策略
