运行时分析是根据时间和空间（内存）需求来确定算法计算效率的过程。本页面详细介绍了算法复杂度分析的理论概念、表示法和实际应用，这些对于技术面试和高效算法设计至关重要。
理解运行时分析有助于开发人员
运行时分析主要关注渐进行为——算法性能如何随着输入规模的增加而扩展——而不是绝对执行时间，后者取决于特定的硬件和实现细节。
来源： README.md330-353
描述算法效率使用几种数学表示法
大O表示法描述了算法运行时的上界——最坏情况。当我们说一个算法运行时间为O(f(n))时，我们指的是其运行时不会比f(n)增长得更快，因为输入规模n在增加。
例如，如果一个算法是O(n²)，则其运行时可能呈二次方或更慢增长，但绝不会比二次方增长得更快。
大Omega表示法描述了算法运行时的下界——最好情况。当我们说一个算法运行时间为Ω(f(n))时，我们指的是其运行时不会比f(n)增长得更慢，因为输入规模n在增加。
Theta表示法描述了算法运行时的上下界。当我们说一个算法运行时间为Θ(f(n))时，我们指的是其运行时将精确地以f(n)的速率增长——它同时是O(f(n))和Ω(f(n))。
这些提供了非紧界。小o提供了一个非渐进紧致的上界，而小omega提供了一个非渐进紧致的下界。
来源： README.md330-353
以下是按效率从高到低排列的常见时间复杂度
| 复杂性 | 姓名 | 示例操作 |
|---|---|---|
| O(1) | 常量 | 哈希表插入/查找，栈的压栈/弹栈 |
| O(log n) | 对数级 | 二分查找、平衡二叉搜索树操作 |
| O(n) | 线性级 | 数组遍历、线性搜索 |
| O(n log n) | 线性对数 | 高效排序（归并排序、快速排序平均情况） |
| O(n²) | 平方级 | 嵌套循环，冒泡排序，插入排序 |
| O(n³) | 立方 | Floyd Warshall算法 |
| O(2^n) | 指数级 | 递归斐波那契数列，幂集生成 |
| O(n!) | 阶乘 | 排列，旅行商问题（暴力解法） |
来源： README.md69-73 README.md79-83 README.md89-93 README.md110-114 README.md153-154 README.md194-198 README.md205-208
不同的数据结构在各种操作上的时间复杂度不同
| 数据结构 | 访问 | 搜索 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1) | O(1) |
| 栈 | O(n) | O(n) | O(1) | O(1) |
| 队列 | O(n) | O(n) | O(1) | O(1) |
| 哈希表 | O(1)* | O(1)* | O(1)* | O(1)* |
| 二叉搜索树 | O(log n)** | O(log n)** | O(log n)** | O(log n)** |
| 二叉堆 | O(1)*** | O(n) | O(log n) | O(log n) |
* 平均情况，在大量哈希冲突时可能为O(n)最坏情况
** 对于平衡树；对于不平衡树可能是O(n)
*** 仅用于获取最小/最大值
来源： README.md69-73 README.md79-83 README.md89-93 README.md110-114 README.md153-154 README.md194-198 README.md205-208
| 算法 | 最佳情况 | 平均情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n+k) |
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 深度优先搜索 | O(|V| + |E|) | O(|V|) |
| 广度优先搜索 | O(|V| + |E|) | O(|V|) |
| Dijkstra 算法 | O(|V|²) | O(|V|) |
| Bellman-Ford 算法 | O(|V|·|E|) | O(|V|) |
| Floyd-Warshall | O(|V|³) | O(|V|²) |
| 普里姆算法 | O(|V|²) | O(|V|) |
| 克鲁斯卡尔算法 | O(|E| log |V|) | O(|E| + |V|) |
来源： README.md194-198 README.md202-208 README.md234-236 README.md252-253 README.md261-262 README.md270-273 README.md275-278
空间复杂度衡量算法相对于其输入规模所需的内存量。与时间复杂度一样，我们也使用大O表示法来描述它。
空间复杂度的关键考虑因素
常见空间复杂度
空间-时间权衡在算法设计中很常见。许多算法可以通过牺牲空间来优化时间，反之亦然。
在分析算法的运行时复杂度时，请遵循以下步骤
这是对存储库中“房屋窃贼”问题的分析
在此算法中
来源： leetcode/dynamic-programming/HouseRobber.java5-26 company/airbnb/HouseRobber.java5-26 company/linkedin/HouseRobber.java5-26
识别这些常见模式有助于快速分析算法复杂度
简单循环遍历n个元素：O(n)
for (int i = 0; i < n; i++) {
// O(1) operations
}
嵌套循环：O(n^k)，其中k是嵌套循环的数量
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// O(1) operations
}
}
// O(n²) complexity
分治法：通常为O(n log n)
// Binary search example
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// O(log n) complexity
递归调用分解问题：通常为O(log n)或O(n log n)
// Typical mergesort pattern (pseudo-code)
mergeSort(array) {
if (array.length <= 1) return array;
left = mergeSort(first half of array);
right = mergeSort(second half of array);
return merge(left, right);
}
// O(n log n) complexity
理解运行时复杂度有助于识别优化机会
在面试中讨论运行时复杂度时
来源： README.md330-353
通过理解运行时分析，您可以有效地评估算法，做出明智的实现选择，并通过展示评估和优化解决方案的能力来在技术面试中取得成功。