什么是算法中的大 O 符号？

大 O 符号是一种数学符号，用于计算机科学中描述算法的效率，特别是时间复杂度和空间复杂度。

它提供了一个上限，描述了随着输入数据大小增加，算法的运行时间或内存使用量的增长速度。

大 O 符号主要用于表达以下内容：

• 时间复杂度：衡量算法的运行时间如何随着输入大小的变化而变化。例如，时间复杂度为 O(n) 的算法表示其运行时间随着输入大小的线性增长。
• 空间复杂度：衡量算法的内存使用量如何随着输入大小的变化而变化。例如，空间复杂度为 O(n) 的算法表示其内存使用量随着输入大小的线性增长。

01 O(1) - 恒定时间

运行时间恒定，不随输入大小变化。

典型应用

• 通过索引访问数组中的元素。
• 插入或删除哈希表中的一个元素（平均）。

02 O(n) - 线性时间

运行时间随输入大小线性增加。

典型应用

• 遍历列表或数组。
• 查找未排序数组中的最大或最小元素。
• 检查未排序数组中是否存在元素。

03 O(log n) - 对数时间

运行时间随输入大小的增加而对数增加。

典型应用

• 排序数组上的二进制搜索。
• 平衡二叉搜索树（如 AVL 树、红黑树）上的操作。
• 查找二进制堆中最大或最小的元素。

04 O(n^2) - 二次方时间

运行时间随输入的大小呈二次方增长。

典型应用

• 简单的排序算法，如冒泡排序、选择排序和插入排序。
• 涉及输入内容嵌套循环的算法（例如，比较所有元素对）。
• 解决某些动态编程问题，如矩阵链式乘法的 native 实现。

05 O(n^3) - 立方时间

运行时间随输入的大小呈立方增长。

典型应用

• 更复杂的动态编程问题，如 Floyd-Warshall 最短路径算法的天真实现。
• 使用 native 算法计算两个密集矩阵的乘法。

06 O(n log n) - 线性时间

运行时间以线性对数方式增长，结合了线性增长和对数增长。

典型应用

• 高效排序算法，如合并排序、快速排序（平均情况）和堆排序。
• 从排序数组构建二叉搜索树。

07 O(2^n) - 指数时间

输入每增加一个元素，运行时间就增加一倍。

典型应用

• 将问题分成多个子问题来解决的递归算法，例如旅行推销员问题的 native 解法。
• 利用递归解决子集和问题。
• 生成集合的所有子集。

08 O(n!) - 因式分解时间

运行时间随输入大小的因子增长。

典型应用

• 排列生成问题。
• 旅行推销员问题的暴力解法。
• 解决涉及生成集合所有可能排序的问题。

09 O(sqrt(n)) - 平方根时间

运行时间与输入大小的平方根成比例增长。

典型应用

• 涉及在一定范围内搜索的算法，如查找 n 以内所有素数的 Eratosthenes 筛法。
• 计算几何中的某些算法。