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

Question

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

Answer 1

这种表示法称为Big O表示法,用作表达算法复杂性的简写(基本上,当输入大小(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,将i加1,检查i是否小于x.length
• 归还总和

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