AlgoNote 算法复杂度详解：从大 O 记号到时间与空间复杂度分析实战

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」AlgoNote系列的开篇基础课系统讲解算法复杂度的核心概念问题规模 $n$ 的定义、渐近符号$O$、$\Omega$、$\Theta$、时间复杂度的计算方法$O(1)$、$O(\log n)$、$O(n)$、$O(n \log n)$、$O(n^2)$、$O(2^n)$、$O(n!)$以及空间复杂度的评估要点。读完本文你将掌握一套不依赖具体语言与硬件、仅凭算法结构即可估算资源消耗的通用方法论并能用它去分析仓库中冒泡排序、归并排序、二分查找、计数排序等任意一个源码文件。1. 什么是算法复杂度衡量资源消耗的标尺算法复杂度Algorithm Complexity用于衡量算法在输入规模为 $n$ 时所需的时间和空间资源。其中问题规模 $n$指算法输入的数据量而 $n$ 的具体含义随算法类型不同而变化排序算法$n$ 表示待排序元素的数量查找算法$n$ 表示查找范围的大小如数组长度、字符串长度等图论算法$n$ 可以指节点数或边数具体视问题而定二进制相关算法$n$ 通常指二进制的位数。一般来说输入规模越大算法的计算成本也随之增加当输入规模相近时计算成本也会比较接近。「算法分析」的核心目标是优化算法使其运行时间更短、内存占用更小。分析算法时主要从运行时间和空间使用两个维度入手对应两种常见方法事后统计将不同算法分别实现并运行通过实际测量运行时间和内存占用来比较优劣预先估算在算法设计阶段根据算法的步骤理论上估算其运行时间和空间消耗并进行比较。实际应用中更倾向于预先估算事后统计不仅工作量大而且同一算法在不同编程语言和硬件环境下的表现差异较大。预先估算通常不考虑编程语言、计算机运行速度等外部因素只关注算法随问题规模增长时的资源消耗趋势——这正是复杂度分析的本质。从源码结构看本仓库的 codes/python 目录正是按「数据结构 算法」的章节组织存放 Python 实现例如01_array下的十余种排序、04_string下的 KMP 与 Sunday 等字符串匹配算法、06_graph下的 DFS/BFS 与最短路径等每个文件都可以用本文的方法独立做一次复杂度分析。2. 时间复杂度2.1 时间复杂度简介时间复杂度Time Complexity用于衡量算法在输入规模为 $n$ 时的运行时间通常记作 $T(n)$。其本质是统计算法中基本操作的执行次数——时间复杂度与基本操作的数量成正比。基本操作指在常数时间内可以完成的语句其执行时间与操作数的大小无关。例如两个小整数相加所需时间不会因为数字位数的不同而变化因此属于基本操作但如果操作数非常大运算时间会随位数增加而增长此时整体加法就不再是基本操作应将每一位的加法视为基本操作。通过一个具体例子演示计算方法。下面的find_max从数组中找出最大值def find_max(arr): max_val arr[0] # 1 次操作 for i in range(len(arr)): # n 次循环 if arr[i] max_val: # n 次比较 max_val arr[i] # 最多 n 次赋值 return max_val # 1 次操作基本操作总共执行 $1 n n n 1 3 \times n 2$ 次可用 $f(n) 3 \times n 2$ 表示其操作次数。时间复杂度分析如下当 $n$ 足够大时$3n$ 是主要影响项常数 $2$ 可以忽略不计由于关注的是随规模增长的趋势常数系数 $3$ 也可以省略因此该算法的时间复杂度为 $O(n)$。这里的 $O$ 表示渐近符号强调 $f(n)$ 与 $n$ 成正比。所谓「算法执行时间的增长趋势」就是用类似 $O$ 这样的渐近符号简洁地描述算法随输入规模变化时的资源消耗情况。2.2 渐近符号时间复杂度通常记作 $T(n) O(f(n))$称为渐近时间复杂度Asymptotic Time Complexity用于描述当问题规模 $n$ 趋近于无穷大时算法运行时间的增长趋势。常用渐近符号有 $O$、$\Omega$、$\Theta$ 三种渐近符号Asymptotic Symbol一类数学符号用于描述函数如算法运行时间或空间随输入规模增长时的变化速度。大 $O$ 描述上界、大 $\Omega$ 描述下界、大 $\Theta$ 描述紧确界它们帮助我们以统一的方式比较不同算法的效率。渐近时间复杂度只关注主导项忽略常数和低阶项从而简洁地反映算法的本质效率。2.2.1 渐近上界符号 $O$渐近上界符号 $O$用于描述算法运行时间的上限通常反映算法在最坏情况下的性能。数学定义设 $T(n)$ 和 $f(n)$ 为两个函数如果存在正常数 $c$ 和 $n_0$使得对所有 $n \geq n_0$都有 $T(n) \leq c \cdot f(n)$则称 $T(n) O(f(n))$。直观理解$T(n) O(f(n))$ 表示「算法的运行时间至多为 $f(n)$ 的某个常数倍」即不会比 $f(n)$ 增长得更快。示例如果 $T(n) 3 \times n^2 2 \times n 1$则 $T(n) O(n^2)$如果 $T(n) 2 \times n 5$则 $T(n) O(n)$如果 $T(n) 100$则 $T(n) O(1)$。2.2.2 渐近下界符号 $\Omega$渐近下界符号 $\Omega$用于描述算法运行时间的下界通常反映算法在最优情况下的性能。数学定义设 $T(n)$ 和 $f(n)$ 为两个函数如果存在正常数 $c 0$ 和 $n_0$使得对所有 $n \geq n_0$都有 $T(n) \geq c \cdot f(n)$则称 $T(n) \Omega(f(n))$。直观理解$T(n) \Omega(f(n))$ 表示「算法的运行时间至少不会低于 $f(n)$ 的某个常数倍」即增长速度不慢于 $f(n)$。示例如果 $T(n) 3 \times n^2 2 \times n 1$则 $T(n) \Omega(n^2)$如果 $T(n) 2 \times n 5$则 $T(n) \Omega(n)$如果 $T(n) n^3$则 $T(n) \Omega(n^2)$。2.2.3 渐近紧确界符号 $\Theta$渐近紧确界符号 $\Theta$用于描述算法运行时间的精确数量级即算法在最好和最坏情况下的增长速度都与 $f(n)$ 保持一致。数学定义设 $T(n)$ 和 $f(n)$ 为两个函数如果存在正常数 $c_1, c_2 0$ 及 $n_0$使得对所有 $n \geq n_0$都有 $c_1 \cdot f(n) \leq T(n) \leq c_2 \cdot f(n)$则称 $T(n) \Theta(f(n))$。直观理解$T(n) \Theta(f(n))$ 表示「算法运行时间与 $f(n)$ 同阶」即上下界都为 $f(n)$ 的常数倍。示例如果 $T(n) 3 \times n^2 2 \times n 1$则 $T(n) \Theta(n^2)$如果 $T(n) 2 \times n 5$则 $T(n) \Theta(n)$如果 $T(n) n \log n n$则 $T(n) \Theta(n \log n)$。三个符号之间的关系可以概括为$O$ 给出性能「不高于」某数量级的保证$\Omega$ 给出「不低于」某数量级的保证而 $\Theta$ 同时给出上下界是最精确的数量级描述。2.3 时间复杂度计算在分析时间复杂度时通常使用 $O$ 符号来表示算法的上界因为实际应用中更关注算法在最坏情况下的表现。计算步骤一般分为三步确定基本操作找出算法中执行次数最多的语句通常是最内层循环的核心操作估算执行次数只关注基本操作的最高阶项忽略常数系数和低阶项用大 O 符号表示将上一步得到的数量级用 $O$ 符号表示出来。计算时还需注意两条常用原则加法原则多个代码块顺序执行时总时间复杂度等于其中最大的那一个。即如果 $T_1(n) O(f_1(n))$$T_2(n) O(f_2(n))$$T(n) T_1(n) T_2(n)$则 $T(n) O(\max(f_1(n), f_2(n)))$。乘法原则循环嵌套时总时间复杂度等于各层复杂度的乘积。即如果 $T_1(n) O(f_1(n))$$T_2(n) O(f_2(n))$$T(n) T_1(n) \times T_2(n)$则 $T(n) O(f_1(n) \times f_2(n))$。下面通过具体实例说明各种常见时间复杂度的计算方法。2.3.1 常数时间 $O(1)$没有循环和递归的算法时间复杂度通常为 $O(1)$def get_first_element(arr): return arr[0] # 直接返回第一个元素 def add_two_numbers(a, b): return a b # 简单的加法运算每个函数都只执行常数次操作时间复杂度为 $O(1)$。在数据结构中数组按下标访问、哈希表查找等都属于常数时间操作这也是它们被广泛应用于「以空间换时间」优化中的根本原因。2.3.2 线性时间 $O(n)$单层循环遍历 $n$ 个元素的算法时间复杂度为 $O(n)$def find_max(arr): max_val arr[0] for num in arr: # 遍历数组中的每个元素 if num max_val: max_val num return max_val def sum_array(arr): total 0 for num in arr: # 遍历数组中的每个元素 total num return total每个函数都只遍历数组一次时间复杂度为 $O(n)$。线性扫描是最基础的遍历模式本仓库 codes/python/01_array 中的计数排序 array_sort_counting_sort.py 的主体统计阶段就是对数组的一次完整线性遍历。2.3.3 平方时间 $O(n^2)$两层嵌套循环、每层执行 $n$ 次操作的算法时间复杂度为 $O(n^2)$def bubble_sort(arr): n len(arr) for i in range(n): # 外层循环 for j in range(n - 1): # 内层循环 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] def find_all_pairs(arr): pairs [] for i in range(len(arr)): # 外层循环 for j in range(len(arr)): # 内层循环 pairs.append((arr[i], arr[j])) return pairs每个函数都包含两层嵌套循环总操作次数为 $n^2$时间复杂度为 $O(n^2)$。仓库中的 array_sort_bubble_sort.py 正是 $O(n^2)$ 的典型实现外层for i in range(len(nums) - 1)控制趟数内层for j in range(len(nums) - i - 1)在未排序区间 [0, n-i-1] 上做相邻元素比较与交换。值得注意的是该实现加入了flag标志位——若某趟未发生任何交换说明数组已有序直接跳出循环这使得最好情况下数组本身有序时间复杂度可以降到 $O(n)$这就是第 2.4 节「最佳时间复杂度」的现实意义。同理array_sort_selection_sort.py 中每次从[i1, len(nums))区间找最小值比较次数恒为 $\frac{n(n-1)}{2}$因此无论输入如何都稳定是 $O(n^2)$。2.3.4 对数时间 $O(\log n)$每次操作将问题规模缩小一半的算法如「二分查找」和「分治算法」时间复杂度为 $O(\log n)$def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1 def power_of_two(n): count 0 while n 1: n n // 2 # 每次除以2 count 1 return count每次将问题规模缩小一半循环次数为 $\log_2 n$时间复杂度为 $O(\log n)$。本仓库对二分查找有完整展开01_13_array_binary_search_01.md 以一个长度为 10 的有序数组查找目标值 6 为例三次比较即定位成功$mid$ 依次取 5、8、6而顺序遍历最坏需 10 次比较直观体现了 $O(\log n)$ 与 $O(n)$ 的差距。同样属于 $O(\log n)$ 量级的还有二叉堆的上浮/下沉调整在 queue_priority_queue.py 中heapAdjust每次沿父子链向下或向上移动一层树高为 $\log n$因此堆的插入与取最值都是 $O(\log n)$。2.3.5 线性对数时间 $O(n \log n)$线性对数一般出现在排序算法中例如「快速排序」「归并排序」「堆排序」时间复杂度为 $O(n \log n)$def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) # 递归处理左半部分 right merge_sort(arr[mid:]) # 递归处理右半部分 return merge(left, right) # 合并两个有序数组 def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return resultmerge_sort采用分治思想每次递归将数组一分为二递归深度为 $\log_2 n$ 层每层合并过程处理 $n$ 个元素整体时间复杂度为 $O(n \log n)$。仓库中的 array_sort_merge_sort.py 与上述实现完全同构mergeSort负责分解mid len(nums) // 2后递归左右两半merge负责合并两个有序子数组分解树的深度是 $\log_2 n$每一层的总合并代价是 $O(n)$由乘法原则得总复杂度 $O(n \log n)$。归并排序同时还会产生 $O(n)$ 的辅助数组空间这一点将在空间复杂度部分继续讨论。2.3.6 指数时间 $O(2^n)$指数时间复杂度 $O(2^n)$ 通常出现在每一步都存在两种选择、递归分支成倍增长的算法中如递归斐波那契、子集枚举等def fibonacci_recursive(n): if n 1: return n return fibonacci_recursive(n-1) fibonacci_recursive(n-2) def generate_subsets(arr): def backtrack(start, current): result.append(current[:]) for i in range(start, len(arr)): current.append(arr[i]) backtrack(i 1, current) current.pop() result [] backtrack(0, []) return resultfibonacci_recursive每次递归分裂成两个子问题递归树节点总数为 $2^n$时间复杂度为 $O(2^n)$generate_subsets通过回溯枚举所有子集每个元素有选或不选两种选择子集总数为 $2^n$整体也是 $O(2^n)$。这正是本仓库动态规划章节存在的意义例如 08_dynamic_programming 中的Pack-ZeroOnePack.py等背包问题如果暴力枚举每个物品选或不选复杂度就是 $O(2^n)$而通过 DP 可将其降为多项式级别。2.3.7 阶乘时间 $O(n!)$阶乘时间 $O(n!)$ 通常出现在需要枚举所有排列或组合的算法中如全排列、旅行商问题暴力解法等。随着输入规模 $n$ 增加算法执行次数以阶乘级别增长计算量极大几乎无法处理较大的输入规模def generate_permutations(arr): def backtrack(start): if start len(arr): result.append(arr[:]) return for i in range(start, len(arr)): arr[start], arr[i] arr[i], arr[start] # 交换 backtrack(start 1) # 递归 arr[start], arr[i] arr[i], arr[start] # 恢复 result [] backtrack(0) return resultgenerate_permutations通过回溯法枚举所有排列每一层递归将当前位置与后续每个元素交换递归深度为 $n$ 层。第 1 层有 $n$ 种选择第 2 层有 $n-1$ 种选择依此类推总共 $n!$ 种排列时间复杂度为 $O(n!)$。2.3.8 时间复杂度对比常见时间复杂度从小到大排序$$O(1) O(\log n) O(n) O(n \log n) O(n^2) O(n^3) O(2^n) O(n!) O(n^n)$$时间复杂度输入规模 $n10$$n100$$n1000$实际应用$O(1)$$1$$1$$1$数组访问、哈希表查找$O(\log n)$$3$$7$$10$二分查找、平衡树操作$O(n)$$10$$100$$1000$线性搜索、数组遍历$O(n \log n)$$33$$664$$9966$快速排序、归并排序$O(n^2)$$100$$10000$$1000000$冒泡排序、选择排序$O(2^n)$$1024$$1.3 \times 10^{30}$$1.1 \times 10^{301}$递归斐波那契$O(n!)$$3628800$$9.3 \times 10^{157}$$4.0 \times 10^{2567}$全排列这张表能直观说明为什么复杂度分析必须看「数量级」而不是「实际运行毫秒数」$n10$ 时 $O(n!)$ 的 362 万次操作尚可忍受但 $n1000$ 时 $O(n^2)$ 已到百万量级$O(2^n)$ 更是天文数字。结合 01_02_array_sort.md 中对排序算法的分类可以更好地理解这套体系简单排序冒泡、选择、插入是 $O(n^2)$高级排序快排、归并、堆排是 $O(n \log n)$而计数、桶、基数等线性排序是 $O(n)$——复杂度正是区分「简单 / 高级 / 线性」三类排序算法的第一标准。2.4 最佳、最坏、平均时间复杂度同一算法在不同输入下的表现可能差异很大因此通常从三个角度分析时间复杂度最佳时间复杂度最理想输入下的时间复杂度最坏时间复杂度最差输入下的时间复杂度平均时间复杂度随机输入下的期望时间复杂度。示例在数组中查找目标值def find(nums, val): for i in range(len(nums)): if nums[i] val: return i return -1最佳情况目标值在数组开头时间复杂度 $O(1)$最坏情况目标值不存在需要遍历整个数组时间复杂度 $O(n)$平均情况假设目标值等概率出现在任意位置平均时间复杂度 $O(n)$。实际应用通常使用最坏时间复杂度作为算法性能的衡量标准因为它能保证算法在任何输入下的性能上限。只有在不同情况下的时间复杂度存在量级差异时才需要区分三种情况。以本仓库源码为例array_sort_quick_sort.py 的快速排序平均与最佳情况是 $O(n \log n)$但若基准数pivot选取不当如始终取到最小/最大值递归会退化为单侧划分最坏时间复杂度为 $O(n^2)$。该实现特意引入random.randint随机挑选基准数见 randomPartition正是为了在概率上规避最坏情况——这从源码侧印证了「最坏情况分析 随机化防御」这一工程实践。3. 空间复杂度3.1 空间复杂度简介空间复杂度Space Complexity在问题的输入规模为 $n$ 的条件下算法所占用的空间大小可记作 $S(n)$。一般将算法的辅助空间作为衡量空间复杂度的标准。空间复杂度的渐近符号表示方法与时间复杂度相同可表示为 $S(n) O(f(n))$表示算法空间占用随问题规模 $n$ 的增长趋势。相对于时间复杂度空间复杂度更容易计算。其计算主要包括两个部分局部变量占用的存储空间函数内定义的变量、数组等递归栈空间递归调用时每一层调用帧在系统栈上占用的空间。值得强调的是「辅助空间」这一口径输入数据本身占用的空间通常不计入算法自身的空间复杂度只有算法额外申请的空间临时数组、递归栈、哈希表等才纳入统计。这也是 01_02_array_sort.md 中「原地排序」与「非原地排序」分类的理论依据原地排序的空间复杂度为 $O(1)$如冒泡、选择、插入、快排、堆排非原地排序空间复杂度为 $O(n)$ 或更高如归并、计数、桶、基数排序。3.2 空间复杂度计算空间复杂度的计算主要考虑算法运行过程中额外占用的空间包括局部变量和递归栈空间。3.2.1 常数空间 $O(1)$def algorithm(n): a 1 b 2 res a * b n return res只使用了固定数量的变量因此空间复杂度为 $O(1)$。冒泡排序、选择排序等原地排序都属于这一类——如 array_sort_bubble_sort.py 仅借助flag标志位与临时交换变量额外空间与 $n$ 无关。3.2.2 线性空间 $O(n)$def algorithm(n): if n 0: return 1 return n * algorithm(n - 1)递归深度为 $n$需要 $O(n)$ 的栈空间。与之类似的还有归并排序的辅助数组虽然递归深度只有 $\log n$但合并阶段每次需要临时结果数组array_sort_merge_sort.py 中merge函数在每一层都会构造nums []承接合并结果整体额外空间为 $O(n)$。这也是归并排序在「空间受限」场景下不如原地排序的原因。3.2.3 常见空间复杂度常见空间复杂度从小到大排序$$O(1) O(\log n) O(n) O(n^2) O(2^n)$$$O(1)$冒泡、选择、插入、快排原地版本、堆排等原地算法$O(\log n)$递归深度为 $\log n$ 的分治算法如平衡二叉树的递归遍历$O(n)$归并排序、计数排序、线性 DP 等需要线性辅助空间的算法$O(n^2)$邻接矩阵存图、二维 DP 表等$O(2^n)$递归子集枚举等在递归树中层层累积空间的算法。在 06_graph 章节中可以看到空间复杂度的实际选择Graph-Adjacency-Matrix.py用 $n \times n$ 矩阵存图空间复杂度 $O(n^2)$而Graph-Adjacency-List.py用邻接表只存实际存在的边空间复杂度为 $O(n e)$$e$ 为边数这正是针对稀疏图用空间换出更优空间复杂度的典型取舍。4. 总结「算法复杂度」包括「时间复杂度」和「空间复杂度」用于衡量算法在输入规模 $n$ 增大时的资源消耗情况通常使用渐近符号如 $O$ 符号来描述算法复杂度的增长趋势。常见的时间复杂度有$O(1)$、$O(\log n)$、$O(n)$、$O(n \log n)$、$O(n^2)$、$O(n^3)$、$O(2^n)$、$O(n!)$。常见的空间复杂度有$O(1)$、$O(\log n)$、$O(n)$、$O(n^2)$。掌握复杂度分析后你可以对仓库中任意一份源码快速做出量级判断二分查找与堆操作是 $O(\log n)$单次线性遍历是 $O(n)$快排/归并/堆排是 $O(n \log n)$双重循环的简单排序是 $O(n^2)$而回溯枚举全排列则是 $O(n!)$ 级别——这为后续学习 01_array 排序、02_linked_list 链表、03_stack_queue_hash_table 栈与队列 乃至 08_dynamic_programming 动态规划 等章节提供了统一的分析语言与性能基准。参考资料【书籍】数据结构C 语言版- 邓俊辉 著【书籍】算法导论 第三版中文版- 殷建平等 译【书籍】算法艺术与信息学竞赛 - 刘汝佳、黄亮 著【书籍】数据结构C 语言版- 严蔚敏 著【书籍】趣学算法 - 陈小玉 著赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐JavaScript算法复杂度分析时间复杂度与空间复杂度详解指南JavaScript算法复杂度分析时间复杂度与空间复杂度详解指南 在JavaScript开发中理解 算法复杂度分析 是写出高效代码的关键。无论是前端交互还是示例工程Hello 算法时间复杂度分析全解——从大 O 记号推算到算法效率判断Hello 算法时间复杂度分析全解——从大 O 记号推算到算法效率判断 本文基于 Hello 算法hello algo教程中的「时间复杂度」章节展开完整教程文档示例工程教育CAVA算法复杂度分析时间与空间复杂度的优化CAVA算法复杂度分析时间与空间复杂度的优化 引言音频可视化背后的计算挑战 在实时音频可视化领域性能优化是决定用户体验的关键因素。CAVACross p音视频桌面应用上一篇安装下一篇终极Flutter国际化实践gsy_github_app_flutter多语言切换与资源配置完全指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考