算法的时间复杂度

整理了下算法的时间复杂度，跟大家一起分享下。
时间复杂度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!)。
空间复杂度的表示与时间复杂度的表示基本一致。时间复杂度关注的是运行时间，空间复杂度关注的是内存消耗。
现在内存比以前便宜，大家更追求时间的优化了。
此心光明，亦复何言。-- 烟沙九洲

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！