• 时间复杂度
• 空间复杂度
• 认知复杂度

1. 时间复杂度 (Time Complexity)

定义：

• 时间复杂度表示算法执行所需的时间，随着输入规模的增大，算法执行时间的增长趋势。
• 用大O符号表示，例如 O(n)，O(n^2) 等。

常见的时间复杂度：

• O(1)：常数时间复杂度

  • 执行时间不随输入规模变化，时间是固定的。
  • 例：访问数组元素 arr[i]。

• O(log n)：对数时间复杂度

  • 执行时间随着输入规模的增大而增长，但增长速度较慢。
  • 例：二分查找。

• O(n)：线性时间复杂度

  • 执行时间与输入规模成正比。
  • 例：线性查找。

• O(n log n)：线性对数时间复杂度

  • 执行时间是输入规模的线性与对数的乘积，较常见于高效排序算法。
  • 例：归并排序、快速排序。

• O(n^2)：平方时间复杂度

  • 执行时间与输入规模的平方成正比。通常见于嵌套循环。
  • 例：冒泡排序、选择排序。

• O(2^n)：指数时间复杂度

  • 执行时间随着输入规模的增加以指数级别增长，通常见于暴力算法。
  • 例：汉诺塔问题、递归解法。

总结：

• 时间复杂度帮助我们评估算法的效率，通常期望它尽可能低，特别是对于大规模输入时。
• 最优情况：最佳情况下的时间复杂度（例如数组已排序）。
• 最坏情况：最坏情况下的时间复杂度（例如数组逆序）。
• 平均情况：对于随机数据的时间复杂度。

---

2. 空间复杂度 (Space Complexity)

定义：

• 空间复杂度表示算法执行过程中所需的额外内存空间，它衡量的是算法随着输入规模增大时，需要的存储空间如何变化。
• 同样使用大O符号来表示。

常见的空间复杂度：

• O(1)：常数空间复杂度

  • 算法使用的内存空间不随着输入规模的变化而变化。
  • 例：简单的交换操作，或是只用常数个变量。

• O(n)：线性空间复杂度

  • 算法需要的额外空间与输入数据规模成正比。
  • 例：归并排序（需要额外的数组来存储排序的元素）。

• O(n^2)：平方空间复杂度

  • 算法需要的空间是输入规模的平方，通常见于二维数组、矩阵等。
  • 例：矩阵乘法的动态规划实现。

总结：

• 空间复杂度衡量的是算法的内存需求，特别关注额外的存储空间，例如临时数据结构、数组等。
• 空间复杂度优化有时比时间复杂度更为重要，特别是在内存受限的环境下。

---

3. 认知复杂度 (Cognitive Complexity)

定义：

• 认知复杂度是指理解和维护代码的难度，从程序员的角度评估代码的复杂度。
• 不像时间复杂度和空间复杂度有明确的数学公式，认知复杂度更加主观，依赖于代码的结构和可读性。

影响因素：

• 控制结构的嵌套深度：如深层嵌套的循环、条件判断等使得代码理解起来更加困难。
• 逻辑的复杂性：复杂的算法逻辑和边界条件判断增加了认知负担。
• 代码的清晰度和可读性：难以理解的代码、冗长的函数、复杂的命名都增加认知复杂度。
• 函数/方法的职责不单一：一个方法执行了过多任务，使得代码理解起来更为困难。

总结：

• 认知复杂度关注代码的可理解性和维护性。
• 影响代码质量的因素包括结构清晰性、函数职责单一以及命名规范。
• 对于我们开发人员来说，尽量保持代码简洁、清晰、结构化，避免过度嵌套和复杂逻辑，以提高认知舒适度。

---

总结对比：

复杂度类型	描述	关键因素
时间复杂度	衡量算法执行所需时间，随着输入规模增大，执行时间如何变化	执行时间随输入规模的变化
空间复杂度	衡量算法执行所需的内存空间，随着输入规模增大，所需空间如何变化	使用的额外内存空间
认知复杂度	衡量理解和维护代码的难度，关注代码的可读性和可维护性	代码结构、逻辑复杂度、清晰度

---

扩展：

• 时间复杂度与空间复杂度的权衡： 有时为了优化时间复杂度，可能需要牺牲空间复杂度。例如，某些算法可能会使用更多内存来减少计算量（如缓存技术）。
• 认知复杂度与开发效率： 代码的可读性与团队的开发效率密切相关，代码的认知复杂度过高可能导致更长的开发时间和更高的维护成本。