算法的时间复杂度

整理了下算法的时间复杂度，跟大家一起分享下。

时间复杂度O是表示算法运行时间与输入数据规模（通常用 n 表示）之间的关系。算法执行时间随输入数据规模增长的变化趋势。

1、O(1) — 常数时间

• 无论输入数据多大，执行时间固定不变。
• 典型场景：数组按索引访问、哈希表查询。

2、O(log n) — 对数时间

• 执行时间随数据量增长，但增速远慢于线性增长。
• 典型场景：二分查找、平衡二叉搜索树操作。

3、O(n) — 线性时间

• 执行时间与数据量成正比。
• 典型场景：遍历数组/链表、线性搜索。

4、O(n log n) — 线性对数时间

• 比线性慢，但比平方快，常见于高效排序算法。
• 典型场景：快速排序、归并排序、堆排序。

5、O(n²) — 平方时间

• 执行时间与数据量的平方成正比，数据量大时性能急剧下降。
• 典型场景：冒泡排序、选择排序、暴力搜索（如两数之和的暴力解法）。

6、O(2ⁿ) — 指数时间

• 执行时间呈指数级增长，仅适用于极小规模数据
• 典型场景：暴力穷举、未优化的递归（如斐波那契数列原始递归）。

7、O(n!) — 阶乘时间

• 最慢的时间复杂度，通常用于全排列问题。
• 典型场景：全排列生成。

排序从最优到最差：O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)。

空间复杂度的表示与时间复杂度的表示基本一致。时间复杂度关注的是运行时间，空间复杂度关注的是内存消耗。

现在内存比以前便宜，大家更追求时间的优化了。

此心光明，亦复何言。-- 烟沙九洲