尧图网站建设 
Hello 算法时间复杂度全解析从操作计数到渐近上界与常见复杂度速查【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo《Hello 算法》官方俄文版第 2.3 节time_complexity.md系统阐述了时间复杂度这一衡量算法效率的核心度量。本文以该章节为骨架结合仓库内 C 与 Python 等源码实现完整讲解为什么不能直接计时 → 如何统计增长趋势 → 渐近上界的数学定义 → 两步推导法 → 七大常见复杂度这条主线帮你建立一套从代码到O(...)表示的可复现分析方法。为什么精确计时既不合理也不现实从直觉上讲算法快不快直接测量运行时间最直观。但章节开篇指出若要精确估计一段代码的运行时间需要依次完成三件麻烦事确定运行平台硬件配置、编程语言、系统环境都会影响代码执行效率同一段代码在不同机器上耗时差异巨大估算每种运算的耗时例如加法约 1 纳秒、乘法*约 10 纳秒、print()输出约 5 纳秒——这些数值本身依赖平台难以精确测定统计代码中的全部运算并把耗时求和才能得到总运行时间。以原文给出的在某平台上示例Python 版def algorithm(n: int): a 2 # 1 纳秒 a a 1 # 1 纳秒 a a * 2 # 10 纳秒 for _ in range(n): # 每次循环 1 纳秒 print(0) # 每次循环 5 纳秒按上述假设逐项累加总耗时为1 1 10 (1 5) × n 6n 12纳秒。这个表达式看似严谨但仔细推敲就能发现其脆弱性一旦换一台机器、换一种语言6n 12中的系数立刻失效。因此章节给出明确结论实际应用中逐条统计每条指令的真实耗时既不合理也不现实——这为引入按趋势统计的分析方法埋下伏笔。统计增长趋势时间复杂度要回答的真正问题时间复杂度的分析目标并不是算法运行时间的绝对值而是运行时间随数据量 $n$ 增大而呈现的增长趋势。章节用算法A、B、C三组对比直观说明趋势的含义Python 版def algorithm_A(n: int): print(0) # 时间复杂度常数级 def algorithm_B(n: int): for _ in range(n): # 时间复杂度线性级 print(0) def algorithm_C(n: int): for _ in range(1000000): # 时间复杂度常数级 print(0)三者的对比要点值得仔细咀嚼算法A只执行一次输出运行时间不随 $n$ 增大而增长 →常数级算法B在循环内输出 $n$ 次时间随 $n$线性增长算法C固定执行一百万次输出虽然总耗时很长但与输入规模 $n$ 无关因此与A一样属于常数级。结合上图横轴为输入规模纵轴为运行时间A/C 为水平线、B 为过原点直线可以得出三条对分析实践极具指导意义的结论趋势能高效评估算法优劣B线性增长当 $n 1$ 时慢于A当 $n 1000000$ 时慢于C只要输入规模足够大常数级算法必然优于线性级——这正是增长趋势的意义所在推导过程更简单平台与运算类型不影响增长趋势因此分析时可以把每次运算都当作等价的单位时间把统计耗时简化为统计操作次数存在固有局限A与C同为常数级但真实耗时差一百万倍B复杂度高于C在小 $n$ 下却明显更快。不过复杂度分析仍是目前评估算法最有效、最通用的手段。渐近上界函数时间复杂度背后的严格数学定义记输入规模为 $n$ 时算法的操作次数为 $T(n)$。对如下函数逐行累计注释为每行贡献的操作数def algorithm(n: int): a 1 # 1 a a 1 # 1 a a * 2 # 1 for i in range(n): # 1 print(0) # 1可得操作总数$$ T(n) 3 2n $$$T(n)$ 是线性函数意味着运行时间的增长趋势是线性的因此该算法的时间复杂度为线性级写作 $O(n)$。这里的 $O$ 记号称为大 $O$ 记号big-$O$ notation表示的正是 $T(n)$ 的渐近上界asymptotic upper bound。渐近上界有严格的数学定义!!! note 渐近上界定义 若存在正实数 $c$ 与实数 $n_0$使得对所有 $n n_0$ 均满足 $T(n) \leq c \cdot f(n)$则认为 $f(n)$ 给出了 $T(n)$ 的渐近上界记作 $T(n) O(f(n))$。换句话说求渐近上界就是在无穷远处找到与 $T(n)$ 同阶增长、只相差一个常数系数 $c$ 的 $f(n)$其几何含义见下图两步推导法从代码到 O(…) 的可操作流程数学定义稍显形式化暂时理解不透也没关系更重要的是先掌握推导方法。整体分两步先统计操作次数再确定渐近上界。步骤一统计操作次数可偷懒由于 $c \cdot f(n)$ 中的常数系数 $c$ 可以任意大$T(n)$ 中的各项系数与常数项都可以忽略。据此原文归纳出三条简化技巧忽略 $T(n)$ 中的常数项它们与 $n$ 无关不影响时间复杂度省略所有系数2n次循环、5n 1次循环都可视为 $n$ 次嵌套循环用乘法总操作数 外层操作数 × 内层操作数每一层内部仍可套用技巧 1、2。应用示例Python 版def algorithm(n: int): a 1 # 0技巧 1 a a n # 0技巧 1 for i in range(5 * n 1): # n技巧 2 print(0) for i in range(2 * n): # n*n技巧 3 for j in range(n 1): print(0)完整统计与偷懒统计的结果对比如下最终得到的时间复杂度一致都是 $O(n^2)$$$ \begin{aligned} T(n) 2n(n 1) (5n 1) 2 \text{完整统计} \ 2n^2 7n 3 \ T(n) n^2 n \text{偷懒统计} \end{aligned} $$步骤二确定渐近上界时间复杂度由 $T(n)$ 中的最高次项决定——当 $n$ 趋于无穷时最高次项主导增长其余项可忽略。原文表格给出了几组刻意夸张的对应关系用来强调系数改变不了阶数操作数量 $T(n)$时间复杂度 $O(f(n))$$100000$$O(1)$$3n 2$$O(n)$$2n^2 3n 2$$O(n^2)$$n^3 10000n^2$$O(n^3)$$2^n 10000n^{10000}$$O(2^n)$注意最后一行的反直觉之处即使 $n^{10000}$ 的低阶项系数高达一万当 $n \to \infty$ 时指数项 $2^n$ 依然绝对主导故仍记作 $O(2^n)$。七大常见时间复杂度类型速查设输入规模为 $n$按从小到大常见时间复杂度排序为$$ O(1) O(\log n) O(n) O(n \log n) O(n^2) O(2^n) O(n!) $$常数级 对数级 线性级 线性对数级 平方级 指数级 阶乘级以下逐一讲解各类型的特征、来源场景与仓库源码中的对应实现C 源码见 time_complexity.cppPython 对应 time_complexity.py。常数级 $O(1)$操作次数与 $n$ 无关def constant(n: int) - int: 常数级复杂度 count 0 size 100000 for _ in range(size): count 1 return count尽管constant()实际执行了十万次自增但其次数固定、不随输入 $n$ 变化因此仍是 $O(1)$。线性级 $O(n)$单层循环def linear(n: int) - int: 线性级复杂度 count 0 for _ in range(n): count 1 return count def array_traversal(nums: list[int]) - int: 线性级复杂度遍历数组 count 0 for num in nums: # 迭代次数与数组长度成正比 count 1 return count数组/链表遍历都属于 $O(n)$此处的 $n$ 是数组或链表长度。这也提醒一个重要细节输入规模 $n$ 需要根据输入的具体类型界定——第一个示例中变量 $n$ 本身就是输入规模第二个示例的规模是数组长度。平方级 $O(n^2)$嵌套循环def quadratic(n: int) - int: 平方级复杂度 count 0 for i in range(n): for j in range(n): count 1 return count外层与内层各 $O(n)$相乘即 $O(n^2)$。以冒泡排序为例外层循环执行 $n-1$ 次内层循环分别执行 $n-1, n-2, \dots, 2, 1$ 次平均 $n/2$ 次故复杂度为 $O((n-1)n/2) O(n^2)$。仓库中的实现把每次元素交换计作 3 次基本操作见 bubble_sort。指数级 $O(2^n)$细胞分裂式增长生物中细胞分裂是典型的指数增长初始 1 个细胞1 轮分裂后变 2 个、2 轮后变 4 个……$n$ 轮后共 $2^n$ 个。Python 实现如下count累计分裂次数输入 $n$ 为分裂轮数def exponential(n: int) - int: 指数级复杂度迭代实现 count 0 base 1 # 每轮分裂为 2 倍1, 2, 4, 8, ..., 2^(n-1) for _ in range(n): for _ in range(base): count 1 base * 2 # count 1 2 4 8 ... 2^(n-1) 2^n - 1 return count递归形式同样常见——函数不断一分为二直至 $n$ 次分裂停止def exp_recur(n: int) - int: 指数级复杂度递归实现 if n 1: return 1 return exp_recur(n - 1) exp_recur(n - 1) 1指数级增长极快常见于暴力枚举、穷举与回溯类算法对大规模问题通常不可接受需要改用动态规划、贪心等策略。对数级 $O(\log n)$每轮把问题减半与指数级相对对数级描述的是每轮把问题规模减半的情况。规模每步减半迭代次数即 $\log_2 n$恰为 $2^n$ 的反函数def logarithmic(n: int) - int: 对数级复杂度迭代实现 count 0 while n 1: n n / 2 count 1 return count递归版本则构成高度为 $\log_2 n$ 的递归树def log_recur(n: int) - int: 对数级复杂度递归实现 if n 1: return 0 return log_recur(n / 2) 1对数级增长缓慢常见于分治类算法是除常数级外最受青睐的复杂度。!!! tip $O(\log n)$ 的底数是多少 严格说每次分成 $m$ 份对应 $O(\log_m n)$。但由换底公式不同底数只差常数倍 $$ O(\log_m n) O(\log_k n / \log_k m) O(\log_k n) $$ 底数 $m$ 可以随意更换而不影响复杂度阶数因此通常省略底数直接写作 $O(\log n)$。线性对数级 $O(n \log n)$递归划分 × 线性遍历线性对数级常见于递归划分场景——一层是 $O(\log n)$ 的划分深度另一层是 $O(n)$ 的遍历开销def linear_log_recur(n: int) - int: 线性对数级复杂度 if n 1: return 1 # 一分为二子问题规模减半 count linear_log_recur(n // 2) linear_log_recur(n // 2) # 当前子问题内还有 n 次操作 for _ in range(n): count 1 return count其直观结构是二叉树的每一层总操作数为 $n$树共有 $\log_2 n 1$ 层故总复杂度为 $O(n \log n)$。快排、归并排序、堆排序等主流排序算法的时间复杂度均为此量级。阶乘级 $O(n!)$全排列问题阶乘级对应数学中的全排列问题$n$ 个互异元素共有$$ n! n \times (n-1) \times (n-2) \times \dots \times 2 \times 1 $$种排列方式。递归实现中第 1 层分出 $n$ 个子问题、第 2 层分出 $n-1$ 个……直至第 $n$ 层def factorial_recur(n: int) - int: 阶乘级复杂度递归实现 if n 0: return 1 count 0 for _ in range(n): # 从 1 个分出 n 个 count factorial_recur(n - 1) return count注意由于 $n \geq 4$ 时恒有 $n! 2^n$阶乘级比指数级增长更快$n$ 稍大即不可接受。最差、最佳与平均时间复杂度同一算法为何有多个复杂度算法的运行效率通常并不固定而是取决于输入数据的分布。章节以在打乱顺序的数组nums内含 1 到 $n$ 各一次中查找元素 1 的下标为例完整实现见 worst_best_time_complexity.cpp 与 worst_best_time_complexity.py当nums [?, ?, ..., 1]即 1 在末尾时必须完整遍历数组 →最差时间复杂度 $O(n)$当nums [1, ?, ?, ...]即 1 在开头时无论数组多长都无需继续遍历 →最佳时间复杂度 $\Omega(1)$。最差复杂度对应渐近上界用大 $O$ 表示最佳复杂度对应渐近下界用 $\Omega$ 表示。章节特别提醒实践中最佳复杂度很少被使用——它往往只在概率极小的输入上出现容易造成误导最差复杂度更具实用价值它为算法效率提供了安全上界让人可以放心使用上述两个极端都只在特定数据分布下出现不一定真实反映算法效率平均时间复杂度用 $\Theta$ 表示才能体现随机输入下的典型表现。例如上例中数组被随机打乱、1 出现在任一位置的概率相等故平均迭代次数为 $n/2$平均时间复杂度为 $\Theta(n/2) \Theta(n)$。!!! question 为什么 $\Theta$ 记号如此少见 大概是因为 $O$ 太常用大家惯于用 $O$ 泛指平均复杂度。严格来说这并不规范——本书及多数资料中出现平均时间复杂度 $O(n)$这类表述时含义其实是 $\Theta(n)$。小结如何在本仓库中动手验证时间复杂度的完整分析链条可概括为识别输入规模 → 统计操作次数应用三条简化技巧→ 取最高次项确定 $O(f(n))$ → 结合输入分布辨析最差/最佳/平均情形。想动手验证可以直接运行仓库中带 driver 的多语言程序观察不同 $n$ 下各类复杂度的操作计数差异Ctime_complexity.cppmain()中内置n 8的计数演示Pythontime_complexity.pyC 语言版本见 time_complexity.c仓库ru/codes/下还提供 Java、Go、Swift、Rust、C#、JS、TS、Kotlin、Ruby、Dart、Zig 等多语言等价实现便于对照同一分析在不同语言下的写法。时间复杂度与空间复杂度共同构成算法的两大基本度量继续深入可阅读本仓库的 空间复杂度章节以及配套的 章节习题 进行巩固练习。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法时间复杂度全解析：从操作计数到渐近上界与常见复杂度速查
Hello 算法时间复杂度全解析从操作计数到渐近上界与常见复杂度速查【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo《Hello 算法》官方俄文版第 2.3 节time_complexity.md系统阐述了时间复杂度这一衡量算法效率的核心度量。本文以该章节为骨架结合仓库内 C 与 Python 等源码实现完整讲解为什么不能直接计时 → 如何统计增长趋势 → 渐近上界的数学定义 → 两步推导法 → 七大常见复杂度这条主线帮你建立一套从代码到O(...)表示的可复现分析方法。为什么精确计时既不合理也不现实从直觉上讲算法快不快直接测量运行时间最直观。但章节开篇指出若要精确估计一段代码的运行时间需要依次完成三件麻烦事确定运行平台硬件配置、编程语言、系统环境都会影响代码执行效率同一段代码在不同机器上耗时差异巨大估算每种运算的耗时例如加法约 1 纳秒、乘法*约 10 纳秒、print()输出约 5 纳秒——这些数值本身依赖平台难以精确测定统计代码中的全部运算并把耗时求和才能得到总运行时间。以原文给出的在某平台上示例Python 版def algorithm(n: int): a 2 # 1 纳秒 a a 1 # 1 纳秒 a a * 2 # 10 纳秒 for _ in range(n): # 每次循环 1 纳秒 print(0) # 每次循环 5 纳秒按上述假设逐项累加总耗时为1 1 10 (1 5) × n 6n 12纳秒。这个表达式看似严谨但仔细推敲就能发现其脆弱性一旦换一台机器、换一种语言6n 12中的系数立刻失效。因此章节给出明确结论实际应用中逐条统计每条指令的真实耗时既不合理也不现实——这为引入按趋势统计的分析方法埋下伏笔。统计增长趋势时间复杂度要回答的真正问题时间复杂度的分析目标并不是算法运行时间的绝对值而是运行时间随数据量 $n$ 增大而呈现的增长趋势。章节用算法A、B、C三组对比直观说明趋势的含义Python 版def algorithm_A(n: int): print(0) # 时间复杂度常数级 def algorithm_B(n: int): for _ in range(n): # 时间复杂度线性级 print(0) def algorithm_C(n: int): for _ in range(1000000): # 时间复杂度常数级 print(0)三者的对比要点值得仔细咀嚼算法A只执行一次输出运行时间不随 $n$ 增大而增长 →常数级算法B在循环内输出 $n$ 次时间随 $n$线性增长算法C固定执行一百万次输出虽然总耗时很长但与输入规模 $n$ 无关因此与A一样属于常数级。结合上图横轴为输入规模纵轴为运行时间A/C 为水平线、B 为过原点直线可以得出三条对分析实践极具指导意义的结论趋势能高效评估算法优劣B线性增长当 $n 1$ 时慢于A当 $n 1000000$ 时慢于C只要输入规模足够大常数级算法必然优于线性级——这正是增长趋势的意义所在推导过程更简单平台与运算类型不影响增长趋势因此分析时可以把每次运算都当作等价的单位时间把统计耗时简化为统计操作次数存在固有局限A与C同为常数级但真实耗时差一百万倍B复杂度高于C在小 $n$ 下却明显更快。不过复杂度分析仍是目前评估算法最有效、最通用的手段。渐近上界函数时间复杂度背后的严格数学定义记输入规模为 $n$ 时算法的操作次数为 $T(n)$。对如下函数逐行累计注释为每行贡献的操作数def algorithm(n: int): a 1 # 1 a a 1 # 1 a a * 2 # 1 for i in range(n): # 1 print(0) # 1可得操作总数$$ T(n) 3 2n $$$T(n)$ 是线性函数意味着运行时间的增长趋势是线性的因此该算法的时间复杂度为线性级写作 $O(n)$。这里的 $O$ 记号称为大 $O$ 记号big-$O$ notation表示的正是 $T(n)$ 的渐近上界asymptotic upper bound。渐近上界有严格的数学定义!!! note 渐近上界定义 若存在正实数 $c$ 与实数 $n_0$使得对所有 $n n_0$ 均满足 $T(n) \leq c \cdot f(n)$则认为 $f(n)$ 给出了 $T(n)$ 的渐近上界记作 $T(n) O(f(n))$。换句话说求渐近上界就是在无穷远处找到与 $T(n)$ 同阶增长、只相差一个常数系数 $c$ 的 $f(n)$其几何含义见下图两步推导法从代码到 O(…) 的可操作流程数学定义稍显形式化暂时理解不透也没关系更重要的是先掌握推导方法。整体分两步先统计操作次数再确定渐近上界。步骤一统计操作次数可偷懒由于 $c \cdot f(n)$ 中的常数系数 $c$ 可以任意大$T(n)$ 中的各项系数与常数项都可以忽略。据此原文归纳出三条简化技巧忽略 $T(n)$ 中的常数项它们与 $n$ 无关不影响时间复杂度省略所有系数2n次循环、5n 1次循环都可视为 $n$ 次嵌套循环用乘法总操作数 外层操作数 × 内层操作数每一层内部仍可套用技巧 1、2。应用示例Python 版def algorithm(n: int): a 1 # 0技巧 1 a a n # 0技巧 1 for i in range(5 * n 1): # n技巧 2 print(0) for i in range(2 * n): # n*n技巧 3 for j in range(n 1): print(0)完整统计与偷懒统计的结果对比如下最终得到的时间复杂度一致都是 $O(n^2)$$$ \begin{aligned} T(n) 2n(n 1) (5n 1) 2 \text{完整统计} \ 2n^2 7n 3 \ T(n) n^2 n \text{偷懒统计} \end{aligned} $$步骤二确定渐近上界时间复杂度由 $T(n)$ 中的最高次项决定——当 $n$ 趋于无穷时最高次项主导增长其余项可忽略。原文表格给出了几组刻意夸张的对应关系用来强调系数改变不了阶数操作数量 $T(n)$时间复杂度 $O(f(n))$$100000$$O(1)$$3n 2$$O(n)$$2n^2 3n 2$$O(n^2)$$n^3 10000n^2$$O(n^3)$$2^n 10000n^{10000}$$O(2^n)$注意最后一行的反直觉之处即使 $n^{10000}$ 的低阶项系数高达一万当 $n \to \infty$ 时指数项 $2^n$ 依然绝对主导故仍记作 $O(2^n)$。七大常见时间复杂度类型速查设输入规模为 $n$按从小到大常见时间复杂度排序为$$ O(1) O(\log n) O(n) O(n \log n) O(n^2) O(2^n) O(n!) $$常数级 对数级 线性级 线性对数级 平方级 指数级 阶乘级以下逐一讲解各类型的特征、来源场景与仓库源码中的对应实现C 源码见 time_complexity.cppPython 对应 time_complexity.py。常数级 $O(1)$操作次数与 $n$ 无关def constant(n: int) - int: 常数级复杂度 count 0 size 100000 for _ in range(size): count 1 return count尽管constant()实际执行了十万次自增但其次数固定、不随输入 $n$ 变化因此仍是 $O(1)$。线性级 $O(n)$单层循环def linear(n: int) - int: 线性级复杂度 count 0 for _ in range(n): count 1 return count def array_traversal(nums: list[int]) - int: 线性级复杂度遍历数组 count 0 for num in nums: # 迭代次数与数组长度成正比 count 1 return count数组/链表遍历都属于 $O(n)$此处的 $n$ 是数组或链表长度。这也提醒一个重要细节输入规模 $n$ 需要根据输入的具体类型界定——第一个示例中变量 $n$ 本身就是输入规模第二个示例的规模是数组长度。平方级 $O(n^2)$嵌套循环def quadratic(n: int) - int: 平方级复杂度 count 0 for i in range(n): for j in range(n): count 1 return count外层与内层各 $O(n)$相乘即 $O(n^2)$。以冒泡排序为例外层循环执行 $n-1$ 次内层循环分别执行 $n-1, n-2, \dots, 2, 1$ 次平均 $n/2$ 次故复杂度为 $O((n-1)n/2) O(n^2)$。仓库中的实现把每次元素交换计作 3 次基本操作见 bubble_sort。指数级 $O(2^n)$细胞分裂式增长生物中细胞分裂是典型的指数增长初始 1 个细胞1 轮分裂后变 2 个、2 轮后变 4 个……$n$ 轮后共 $2^n$ 个。Python 实现如下count累计分裂次数输入 $n$ 为分裂轮数def exponential(n: int) - int: 指数级复杂度迭代实现 count 0 base 1 # 每轮分裂为 2 倍1, 2, 4, 8, ..., 2^(n-1) for _ in range(n): for _ in range(base): count 1 base * 2 # count 1 2 4 8 ... 2^(n-1) 2^n - 1 return count递归形式同样常见——函数不断一分为二直至 $n$ 次分裂停止def exp_recur(n: int) - int: 指数级复杂度递归实现 if n 1: return 1 return exp_recur(n - 1) exp_recur(n - 1) 1指数级增长极快常见于暴力枚举、穷举与回溯类算法对大规模问题通常不可接受需要改用动态规划、贪心等策略。对数级 $O(\log n)$每轮把问题减半与指数级相对对数级描述的是每轮把问题规模减半的情况。规模每步减半迭代次数即 $\log_2 n$恰为 $2^n$ 的反函数def logarithmic(n: int) - int: 对数级复杂度迭代实现 count 0 while n 1: n n / 2 count 1 return count递归版本则构成高度为 $\log_2 n$ 的递归树def log_recur(n: int) - int: 对数级复杂度递归实现 if n 1: return 0 return log_recur(n / 2) 1对数级增长缓慢常见于分治类算法是除常数级外最受青睐的复杂度。!!! tip $O(\log n)$ 的底数是多少 严格说每次分成 $m$ 份对应 $O(\log_m n)$。但由换底公式不同底数只差常数倍 $$ O(\log_m n) O(\log_k n / \log_k m) O(\log_k n) $$ 底数 $m$ 可以随意更换而不影响复杂度阶数因此通常省略底数直接写作 $O(\log n)$。线性对数级 $O(n \log n)$递归划分 × 线性遍历线性对数级常见于递归划分场景——一层是 $O(\log n)$ 的划分深度另一层是 $O(n)$ 的遍历开销def linear_log_recur(n: int) - int: 线性对数级复杂度 if n 1: return 1 # 一分为二子问题规模减半 count linear_log_recur(n // 2) linear_log_recur(n // 2) # 当前子问题内还有 n 次操作 for _ in range(n): count 1 return count其直观结构是二叉树的每一层总操作数为 $n$树共有 $\log_2 n 1$ 层故总复杂度为 $O(n \log n)$。快排、归并排序、堆排序等主流排序算法的时间复杂度均为此量级。阶乘级 $O(n!)$全排列问题阶乘级对应数学中的全排列问题$n$ 个互异元素共有$$ n! n \times (n-1) \times (n-2) \times \dots \times 2 \times 1 $$种排列方式。递归实现中第 1 层分出 $n$ 个子问题、第 2 层分出 $n-1$ 个……直至第 $n$ 层def factorial_recur(n: int) - int: 阶乘级复杂度递归实现 if n 0: return 1 count 0 for _ in range(n): # 从 1 个分出 n 个 count factorial_recur(n - 1) return count注意由于 $n \geq 4$ 时恒有 $n! 2^n$阶乘级比指数级增长更快$n$ 稍大即不可接受。最差、最佳与平均时间复杂度同一算法为何有多个复杂度算法的运行效率通常并不固定而是取决于输入数据的分布。章节以在打乱顺序的数组nums内含 1 到 $n$ 各一次中查找元素 1 的下标为例完整实现见 worst_best_time_complexity.cpp 与 worst_best_time_complexity.py当nums [?, ?, ..., 1]即 1 在末尾时必须完整遍历数组 →最差时间复杂度 $O(n)$当nums [1, ?, ?, ...]即 1 在开头时无论数组多长都无需继续遍历 →最佳时间复杂度 $\Omega(1)$。最差复杂度对应渐近上界用大 $O$ 表示最佳复杂度对应渐近下界用 $\Omega$ 表示。章节特别提醒实践中最佳复杂度很少被使用——它往往只在概率极小的输入上出现容易造成误导最差复杂度更具实用价值它为算法效率提供了安全上界让人可以放心使用上述两个极端都只在特定数据分布下出现不一定真实反映算法效率平均时间复杂度用 $\Theta$ 表示才能体现随机输入下的典型表现。例如上例中数组被随机打乱、1 出现在任一位置的概率相等故平均迭代次数为 $n/2$平均时间复杂度为 $\Theta(n/2) \Theta(n)$。!!! question 为什么 $\Theta$ 记号如此少见 大概是因为 $O$ 太常用大家惯于用 $O$ 泛指平均复杂度。严格来说这并不规范——本书及多数资料中出现平均时间复杂度 $O(n)$这类表述时含义其实是 $\Theta(n)$。小结如何在本仓库中动手验证时间复杂度的完整分析链条可概括为识别输入规模 → 统计操作次数应用三条简化技巧→ 取最高次项确定 $O(f(n))$ → 结合输入分布辨析最差/最佳/平均情形。想动手验证可以直接运行仓库中带 driver 的多语言程序观察不同 $n$ 下各类复杂度的操作计数差异Ctime_complexity.cppmain()中内置n 8的计数演示Pythontime_complexity.pyC 语言版本见 time_complexity.c仓库ru/codes/下还提供 Java、Go、Swift、Rust、C#、JS、TS、Kotlin、Ruby、Dart、Zig 等多语言等价实现便于对照同一分析在不同语言下的写法。时间复杂度与空间复杂度共同构成算法的两大基本度量继续深入可阅读本仓库的 空间复杂度章节以及配套的 章节习题 进行巩固练习。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考