我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
我在问更多关于这对我的代码意味着什么。我能从数学上理解这些概念,只是很难理解它们在概念上的含义。例如,如果有人要对一个数据结构执行O(1)操作,我知道它必须执行的操作数量不会增长,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人能帮我填一下吗?
比如O(n²)的运算会怎样? 如果一个操作是O(nlog (n))这是什么意思? 有人必须吸可卡因才能写出O(x!)吗?
当前回答
我会试着为一个真正的八岁男孩写一个解释,除了专业术语和数学概念。
比如O(n²)的运算会怎样?
如果你在一个聚会上,包括你在内有n个人。需要多少次握手才能让每个人都和其他人握手,因为人们可能会在某个时候忘记他们握手的人是谁。
注意:这近似于产生n(n-1)的单形,这足够接近于n²。
如果一个操作是O(nlog (n))这是什么意思?
你最喜欢的球队赢了,他们站在队伍里,队伍里有n名球员。你需要和每个玩家握手多少次,假设你要和每个玩家握手多次,多少次,玩家的号码n中有多少位数字。
注意:这将产生n * log n的10次方。
有人必须吸可卡因才能写出O(x!)吗?
你是一个富二代,你的衣柜里有很多衣服,每种衣服有x个抽屉,抽屉一个挨着一个,第一个抽屉里有一件衣服,每个抽屉里有和左边抽屉一样多的衣服,所以你有一顶帽子,两顶假发,…(x-1)条裤子,然后是x件衬衫。现在,用每个抽屉里的一件物品,你能装扮出多少种风格呢?
注意:这个例子表示一个决策树中有多少个叶结点,其中子结点数=深度,通过1 * 2 * 3 *完成。* x
其他回答
你可能会发现把它形象化很有用:
同样,在LogY/LogX尺度上,函数n1/2, n, n2都看起来像直线,而在LogY/X尺度上,2n, en, 10n是直线和n!是线性的(看起来像n log n)
好吧,这里有一些非常好的答案,但几乎所有的答案似乎都犯了同样的错误,这是一个普遍的常见用法。
非正式地,我们写f(n) = O(g(n))如果,直到一个比例因子,对于所有n大于某个n0, g(n)大于f(n)。也就是说,f(n)的增长速度并不比g(n)快,或者从上到下以g(n)为界。这并没有告诉我们f(n)增长有多快,除了它保证不会比g(n)差。
一个具体的例子:n = O(2^n)我们都知道n的增长速度比2^n慢得多,所以我们可以说它的上界是指数函数。在n和2^n之间有很大的空间,所以它不是一个很紧的边界,但它仍然是一个合理的边界。
为什么我们(计算机科学家)使用边界而不是精确?因为a)边界通常更容易证明,b)它为我们提供了一种表达算法属性的简便方法。如果我说我的新算法是O(n.log n),这意味着在最坏的情况下,它的运行时间将在n个输入上以n.log n为界,对于足够大的n(尽管请参阅下面我的评论,当我可能不是指最坏情况时)。
如果相反,我们想说一个函数的增长速度与其他函数一样快,我们用theta来说明这一点(我将T(f(n))写成markdown表示\ (f(n))。T(g(n))是上下以g(n)为界的缩写,直到一个比例因子且渐近。
这是f (n) = T (g (n)) < = > f (n) = O (g (n))和g (n) = O (f (n))。在我们的例子中,我们可以看到n != T(2^n)因为2^n != O(n)。
为什么要担心这个呢?因为在你的问题中,你写了“一个人必须吸可卡因才能写出一个O(x!)?”答案是否定的——因为基本上你写的所有东西都会以阶乘函数为界。快速排序的运行时间是O(n!) -这不是一个严格的界限。
这里还有另一个微妙的维度。通常我们用O(g(n))表示最坏情况的输入,这样我们就得到了一个复合语句:在最坏情况下运行时间不会比g(n)步的算法差,同样是模缩放,而且n足够大,但有时我们想讨论平均情况甚至最佳情况的运行时间。
香草快速排序就是一个很好的例子。在最坏的情况下是T(n²)(实际上至少需要n²步,但不会多很多),但在平均情况下是T(n.log n),也就是说期望的步数与n.log n成正比。在最好的情况下也是T(n.log n) -但你可以改进它,例如,检查数组是否已经排序在哪种情况下,最佳运行时间将是T(n)。
How does this relate to your question about the practical realisations of these bounds? Well, unfortunately, O( ) notation hides constants which real-world implementations have to deal with. So although we can say that, for example, for a T(n^2) operation we have to visit every possible pair of elements, we don't know how many times we have to visit them (except that it's not a function of n). So we could have to visit every pair 10 times, or 10^10 times, and the T(n^2) statement makes no distinction. Lower order functions are also hidden - we could have to visit every pair of elements once, and every individual element 100 times, because n^2 + 100n = T(n^2). The idea behind O( ) notation is that for large enough n, this doesn't matter at all because n^2 gets so much larger than 100n that we don't even notice the impact of 100n on the running time. However, we often deal with 'sufficiently small' n such that constant factors and so on make a real, significant difference.
例如,快速排序(平均成本T(n.log n))和堆排序(平均成本T(n.log n))都是具有相同平均成本的排序算法——但快速排序通常比堆排序快得多。这是因为堆排序比快速排序对每个元素做了更多的比较。
这并不是说O()符号是无用的,只是不精确。对于小n来说,这是一个相当钝的工具。
(作为本文的最后一个注意事项,请记住O()表示法只是描述任何函数的增长——它不一定是时间,它可以是内存、分布式系统中交换的消息或并行算法所需的cpu数量。)
我试图用c#和JavaScript给出简单的代码示例来解释。
C#
For List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};
O(1)看起来像
return numbers.First();
O(n)看起来像
int result = 0;
foreach (int num in numbers)
{
result += num;
}
return result;
O(nlog (n))是这样的
int result = 0;
foreach (int num in numbers)
{
int index = numbers.Count - 1;
while (index > 1)
{
// yeah, stupid, but couldn't come up with something more useful :-(
result += numbers[index];
index /= 2;
}
}
return result;
O(n2)是这样的
int result = 0;
foreach (int outerNum in numbers)
{
foreach (int innerNum in numbers)
{
result += outerNum * innerNum;
}
}
return result;
O(n!)看起来,嗯,太累了,想不出任何简单的东西。 但我希望你能明白大意?
JavaScript
对于const数= [1,2,3,4,5,6,7,12,543,7];
O(1)看起来像
numbers[0];
O(n)看起来像
let result = 0;
for (num of numbers){
result += num;
}
O(nlog (n))是这样的
let result = 0;
for (num of numbers){
let index = numbers.length - 1;
while (index > 1){
// yeah, stupid, but couldn't come up with something more useful :-(
result += numbers[index];
index = Math.floor(index/2)
}
}
O(n2)是这样的
let result = 0;
for (outerNum of numbers){
for (innerNum of numbers){
result += outerNum * innerNum;
}
}
big - o符号对代码的重要意义在于,当它所操作的“事物”数量增加一倍时,它将如何扩展。这里有一个具体的例子:
Big-O | computations for 10 things | computations for 100 things ---------------------------------------------------------------------- O(1) | 1 | 1 O(log(n)) | 3 | 7 O(n) | 10 | 100 O(n log(n)) | 30 | 700 O(n^2) | 100 | 10000
快速排序是O(nlog (n))而冒泡排序是O(n²)当排序10个东西时,快速排序比冒泡排序快3倍。但当对100个东西进行排序时,速度要快14倍!显然,选择最快的算法很重要。当您访问具有数百万行的数据库时,这可能意味着您的查询在0.2秒内执行,而不是花费数小时。
另一件需要考虑的事情是,糟糕的算法是摩尔定律无法帮助的事情。例如,如果你有一个O(n^3)的科学计算,它一天可以计算100个东西,处理器速度翻倍一天只能计算125个东西。然而,计算到O(n²),你每天要做1000件事情。
澄清: 实际上,Big-O并没有说不同算法在同一特定大小点上的性能比较,而是说同一算法在不同大小点上的性能比较:
computations computations computations Big-O | for 10 things | for 100 things | for 1000 things ---------------------------------------------------------------------- O(1) | 1 | 1 | 1 O(log(n)) | 1 | 3 | 7 O(n) | 1 | 10 | 100 O(n log(n)) | 1 | 33 | 664 O(n^2) | 1 | 100 | 10000
要理解O(n log n),请记住log n意味着log-base-2 (n)。然后看看每一部分:
O(n)是,当你对集合中的每一项进行操作时。
O(log n)是指操作的次数与取2的指数相同,以得到项目的数量。例如,二分搜索必须将集合切成log n的一半。
O(nlogn)是一个组合——你在对集合中的每一项进行二分搜索。高效的排序通常是对每个项目进行一次循环,并在每个循环中进行良好的搜索,以找到放置相关项目或组的正确位置。因此是n * log n。