哪里可以找到O（n^2）和O（n）等的含义？

我一直在注意堆栈溢出的使用这些条款的答案，但我不知道他们的意思。他们叫什么，有没有一个很好的资源可以用简单的术语来解释它们？哪里可以找到O（n^2）和O（n）等的含义？

2010-08-23 adam0101

我不会称它为完全重复的，因为你问的是什么符号被称为，但检查出答案[简单英语解释大O]（http://stackoverflow.com/questions/487258/纯英语的解释 - 中 - 大-O）。 – 2010-08-23 13:21:57

相关：http://stackoverflow.com/questions/107165，http://stackoverflow.com/questions/487258，等。 – Gumbo 2010-08-23 13:22:28

这个网站太棒了。我喜欢我如何快速获得最佳答案！ – adam0101 2010-08-23 13:37:58

这符号被称为Big O notation，并且被用作速记以表达算法复杂性（基本上定algorithim将花费多长时间的输入大小上运行（n）的增长）

一般来说，你会碰上下列主要类型algorithims的：

O（1） - 常量 - 的时间，这需要algorithim完成的长度不依赖于该algorithim必须处理的项目的数目。
O（log n） - 对数 - 此算法需要完成的时间长度取决于该算法必须处理的项目数。随着输入尺寸变大，每个新输入需要更少的时间。
O（n） - 线性 - 此算法需要完成的时间长度直接取决于该算法必须处理的项目数。随着输入规模的增长，所需时间也会相应增长。
O（n^2） - Polynominal - 随着输入大小的增加，处理输入所花费的时间越来越大 - 这意味着大输入大小变得难以解决。
O（2^n） - 指数 - 最复杂的问题类型。处理时间根据输入大小增加到极端程度。

一般来说，您可以通过查看它的使用方式来粗略判断算法的复杂性。例如，在看下面的方法：

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

有有在这里做了几件事情：

初始化变量称为总和
初始化变量叫我
对于i的每次迭代：添加x [i]求和，给i加1，检查我是否小于x。长度
返回总和

有，在固定的时间在这里（前两个和最后一个）上运行一些操作，因为x的大小也不会影响他们需要多长时间才能运行。而且，有些操作在线性时间内运行（因为它们对x中的每个条目运行一次）。随着大O符号，在algorithim被简化到最复杂的，所以这笔钱algorithim将在运行为O（n）

来源

2010-08-23 13:19:14

瑞恩，你的意思是O（n）的数字3。 – 2010-08-23 13:28:32

感谢您的支持:) – 2010-08-23 13:32:42

我认为O（n * ln（n））也是不值得的，因为这是许多排序算法的复杂性 – 2010-08-23 13:36:12

先阅读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]); 
}

有时，估计函数/算法的大O表示法复杂性并不那么简单h使用amortized analysis。以上代码只能用作快速入门。

来源

2010-08-23 13:18:35 jethro

这就是所谓的Big O notation，用来量化算法的复杂性。（1）表示无论处理多少数据，该算法都需要一个恒定的时间。 O（n）表示算法速度随着数据量的增加而线性增长。

等等...

所以在O符号n次方越低越好你的算法是要解决的问题。最好的情况是O（1）（n = 0）。但是在许多问题中存在固有的复杂性，因此几乎在所有情况下都不会找到这样一种理想的算法。

来源

2010-08-23 13:19:20 jdehaan

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

“someformula是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)。

来源

2010-08-23 13:42:33

哪里可以找到O（n^2）和O（n）等的含义？

回答

相关问题