algorithm - 在哪里可以找到 O(n^2) 和 O(n) 等的含义？

Question

我一直注意到堆栈溢出的答案使用了这些术语，但我不知道它们是什么意思。它们叫什么？是否有好的资源可以用简单的术语解释它们？

Answer 1

该符号称为 Big O notation , 并用作表达算法复杂性的简写(基本上是给定算法随着输入大小 (n) 的增长需要运行多长时间)

一般来说，您会遇到以下主要类型的算法:

1. O(1) - 常量 - 该算法完成所需的时间长度与算法必须处理的项目数无关。
2. O(log n) - 对数 - 该算法完成所需的时间长度取决于算法必须处理的项目数。随着输入尺寸变大，每个新输入所需的时间越来越少。
3. O(n) - 线性 - 该算法完成所需的时间长度直接取决于算法必须处理的项目数。随着输入大小的增加，所需时间也会相应增加。
4. O(n^2) - 多项式 - 随着输入大小的增长，处理输入所需的时间越来越长 - 这意味着大输入规模变得非常难以解决.
5. O(2^n) - 指数 - 最复杂的问题类型。处理时间根据输入大小增加到极端程度。

通常，您可以通过查看算法的使用方式来大致了解算法的复杂性。例如，查看以下方法:

function sum(int[] x) {
    int sum = 0;
    for (int i = 0; i < x.length; i++) {
        sum += x[i];
    } 
    return sum;
}

这里有几件事必须要做:

• 初始化一个名为sum的变量
• 初始化一个名为 i 的变量
• 对于i的每次迭代:将x[i]加到sum上，将1加到i上，检查i是否小于x.length
• 返回金额

这里有一些操作在恒定时间内运行(前两个和最后一个)，因为 x 的大小不会影响它们运行的​​时间。同样，有些操作在线性时间内运行(因为它们对 x 中的每个条目运行一次)。使用大 O 表示法，算法被简化为最复杂的，因此该求和算法将在 O(n)

中运行