在哪里可以找到O(n^2)和O(n)etc的意思?

这个符号叫做 Big O notation ,并用作表示算法复杂性的速记(基本上是给定算法随着输入大小(n)的增长运行所需的时间)

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

1. O(1) -常量-此算法完成所需的时间长度不取决于算法必须处理的项目数。
2. O(对数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
• 返回和

这里有一些操作是以固定时间运行的(前两个和最后一个),因为x的大小不会影响它们运行的时间。另外,有些操作是以线性时间运行的(因为它们对x中的每个条目运行一次)。使用大O表示法,算法被简化为最复杂的,所以这个求和算法将在

了解 Computational Complexity 首先,尝试一些关于算法的书,比如 Introduction to Algorithms .

从维基百科页面:

大O表示法根据函数的增长率来表征函数

void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size

for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n)

for (int i=0;i<n;i++) { // this one runs O(n^2)
    for (int j=0;j<n;j++) {
        simpleFunction(element[i]);
    }
}

for (int i=0;i<n;i*=2) {  // O(lgn)
    simpleFunction(element[i]);
}

在这种情况下,有时估计函数/算法的复杂度并不是那么简单 amortized analysis 已使用。上面的代码只能用作快速入门。

这就是所谓的 Big O notation 用来量化算法的复杂度。

O(n)表示算法速度随数据量线性增长。

所以O符号中n的幂越低,你的算法就越适合解决这个问题。最佳情况是O(1)(n=0)。但许多问题都有其固有的复杂性,因此在几乎所有情况下都找不到如此理想的算法。

到目前为止,答案是好的。网络搜索的主要术语是“大O符号”。

“someformula is O(someterm)”数学背后的基本思想是,当变量变为无穷大时,“someterm”是公式中占主导地位的部分。

0.05*x^3 + 300*x^2 + 200000000*x + 10 . 对于x(x==1或x==2)的非常小的尺寸 200000000*x 将是目前为止最大的部分。在这一点上,公式的曲线图看起来是线性的。当你继续前进的时候,在某个时刻 300*x^2 部分会更大。然而,如果你继续把x做得更大,像你想做的那样大,那么 0.05*x^3 部分将是最大的,最终将完全超过公式的其他部分。从图中可以清楚地看出,这是一个立方函数。所以我们可以说公式是 O(x^3) .