8岁儿童的大O？

Question

我问的更多关于这对我的代码意味着什么.我在数学上理解这些概念,我只是很难在概念上围绕它们的意思.例如,如果要对数据结构执行O(1)操作,我理解它必须执行的操作量不会增加,因为有更多项.而O(n)操作意味着您将对每个元素执行一组操作.有人可以在这里填空吗？

• 就像O(n ^ 2)操作究竟会做什么一样？
• 如果一个操作是O(n log(n)),这意味着什么呢？
• 有人必须抽烟才能写出O(x!)？

Answer 1

一种思考方式是这样的:

O(N ^ 2)意味着对于每个元素,您正在对每个其他元素执行某些操作,例如比较它们.冒泡排序就是一个例子.

O(N log N)意味着对于每个元素,你正在做一些只需要查看元素的log N的东西.这通常是因为您了解了可以让您做出有效选择的元素.最有效的排序就是这样的一个例子,例如合并排序.

O(N!)表示对N个元素的所有可能排列做一些事情.旅行推销员就是一个例子,那里有N!访问节点的方法,暴力解决方案是查看每个可能的排列的总成本,以找到最佳的排列.

Answer 2

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(n log(n))vs冒泡排序,即O(n ^ 2).排序10件事时,quicksort比冒泡排序快3倍.但是当排序100件事时,它快了14倍!显然,选择最快的算法非常重要.当您到达具有百万行的数据库时,它可能意味着您的查询在0.2秒内执行与使用小时之间的差异.

另一件需要考虑的事情是,糟糕的算法是摩尔定律无法帮助的一件事.例如,如果你有一些科学的计算是O(n ^ 3)并且它每天可以计算100件事,那么加倍处理器的速度只能让你在一天内完成125件事.但是,将计算结果敲到O(n ^ 2),你每天要做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

Answer 3

您可能会发现将其可视化很有用:

此外,在 LogY/LogX比例上,函数n ^1/2,n,n ² 都看起来像直线,而在LogY/X比例2 ⁿ,e ⁿ,10 ⁿ 是直线和n!是线性的(看起来像n log n).

Answer 4

这可能太数学了,但这是我的尝试.(我是一名数学家.)

如果某些东西是O(f(n)),那么它在n个元素上的运行时间将等于A f(n)+ B (在时钟周期或CPU操作中测量).理解你还有这些常量A和B是关键,这些常量来自具体的实现.B基本上表示操作的"常量开销",例如,您执行的某些预处理不依赖于集合的大小.A表示实际项目处理算法的速度.

但关键是,你使用大O符号来计算出某些东西的扩展程度.所以这些常数并不重要:如果你想弄清楚如何从10个项目扩展到10000个项目,谁关心不断的开销B？同样,其他问题(见下文)肯定会超过乘法常数A的权重.

所以真正的交易是f(n).如果˚F增长并不与ñ,如˚F(ñ)= 1,那么你会扩展飞驰---你的运行时间将永远只是一个 + 乙.如果f与n线性增长,即f(n)= n,那么你的运行时间将达到最佳值 - 如果你的用户等待10 ns的10个元素,他们将等待10000 ns为10000元素(忽略加性常数).但如果它变得更快,就像n ²那你就麻烦了; 当你收到更大的收藏品时,事情会开始放慢太多.f(n)= n log(n)是一个很好的折衷方案,通常:你的操作不能简单到给出线性缩放,但是你已经设法削减了它,以便它比f更好地扩展(n)= n ².

实际上,这里有一些很好的例子:

• O(1):从数组中检索元素.我们确切地知道它在内存中的位置,所以我们就去了.如果集合有10个项目或10000个则无关紧要; 它仍然在索引(比方说)3,所以我们只是跳到内存中的位置3.
• O(n):从链表中检索元素.在这里,A = 0.5,因为平均而言,在找到您正在寻找的元素之前,您必须经过1/2的链表.
• O(n ²):各种"哑"排序算法.因为通常他们的策略涉及,对于每个元素(n),你看所有其他元素(所以另一个n,给n ²),然后将自己定位在正确的位置.
• O(n log(n)):各种"智能"排序算法.事实证明,你只需要看看,比如说,10元在10 ¹⁰ -元素集合相对于智能排序自己大家其他的收藏.因为其他人也会查看10个元素,并且紧急行为恰好正确编排,这样就足以生成排序列表.
• O(n!):一种"尝试一切"的算法,因为它与n成比例!可能解决给定问题的n个元素的可能组合.所以它只是遍历所有这样的组合,尝试它们,然后只要它成功就停止.

Answer 5

don.neufeld的答案非常好,但我可能会分两部分来解释:首先,大多数算法属于O()的粗略层次结构.然后,您可以查看其中的每一个,以得出时间复杂度的典型算法的草图.

出于实际目的,唯一似乎重要的O()是:

• O(1)"恒定的时间" - 所需的时间不依赖于输入的大小的.作为一个粗略的分类,我就包括算法,如哈希查找,并在这里联盟查找,即使没有这些其实都是O(1).
• O(日志(n))的"对数" - 它变慢,你得到更大的投入,但一旦你输入变得相当大,它不会改变足够的理由担心.如果你的运行是确定与合理大小的数据,你可以尽可能多的附加数据淹没了它,只要你想和它仍然是好的.
• O(n)"线性" - 在均衡权衡中输入越多,所需的时间越长.输入尺寸的三倍大约需要三倍的时间.
• O(n log(n))"优于二次" - 增加输入大小会受到伤害,但它仍然可以管理.该算法可能是不错的,只是潜在的问题比在线性时间内可以解决的问题更难(决策相对于输入数据的本地化程度更低).如果您的输入大小正在上升,请不要假设您必须处理两倍大小而不改变您的体系结构(例如,将事物移动到隔夜批处理计算中,或者不执行每帧操作).但是,如果输入大小稍微增加,则可以.只要注意倍数.
• O(n ^ 2)"二次" - 它实际上只能达到你输入的一定大小,所以要注意它的大小.此外,你的算法可能很糟糕 - 想想是否有一个O(n log(n))算法可以满足你的需要.一旦你来到这里,我们非常感谢我们所拥有的令人惊叹的硬件.不久前,你想要做的事情对于所有实际目的都是不可能的.
• O(n ^ 3)"立方" - 不是定性地与O(n ^ 2)不同.同样的评论也适用,但更多.有一个很好的机会,一个更聪明的算法可以把这个时间削减到更小的东西,例如O(n ^ 2 log(n))或O(n ^ 2.8 ......),但是再次,它很有可能不值得的麻烦.(你的实际输入大小已经受到限制,因此更聪明的算法可能需要的常数因素可能会淹没它们在实际情况下的优势.而且,思考速度慢;让计算机咀嚼它可能会节省你的时间总体.)
• O(2 ^ n)"指数" - 问题要么从根本上计算上很难,要么你是一个白痴.这些问题对他们来说具有可识别的风味.您的输入大小限制在相当具体的硬限制.你会很快知道你是否符合这个限制.

就是这样.还有许多其他可能性适合这些(或大于O(2 ^ n)),但它们通常不会在实践中发生,并且它们与其中之一在质量上没有太大差异.立方算法已经有点延伸了; 我只把它们包括在内,因为我经常遇到它们,值得一提(例如矩阵乘法).

这些类算法实际上发生了什么？好吧,我认为你有一个良好的开端,尽管有许多例子不适合这些特征.但对于上述情况,我会说它通常类似于:

• O(1) - 您只能查看固定大小的输入数据块,而且可能没有.示例:排序列表的最大值.
  • 或者您的输入大小有限.示例:添加两个数字.(注意,N个数字的加法是线性时间.)
• O(log n) - 输入的每个元素都告诉您足够忽略输入的其余部分.示例:当您在二进制搜索中查看数组元素时,它的值告诉您可以忽略数组的"一半"而不查看任何数组.或者类似地,您看到的元素为您提供了足够的剩余输入的一小部分摘要,您不需要查看它.
  • 但是,对于一半没什么特别的 - 如果你在每一步都只能忽略10%的输入,那么它仍然是对数的.
• O(n) - 你为每个输入元素做一些固定的工作量.(但见下文.)
• O(n log(n)) - 有一些变体.
  • 您可以将输入分成两堆(不超过线性时间),在每一堆上独立解决问题,然后将两个桩组合成最终解.两桩的独立性是关键.示例:经典递归合并.
  • 每次线性时间传递数据都会使您获得解决方案的一半.示例:如果您根据每个分区步骤中每个元素与其最终排序位置的最大距离来考虑,请快速排序(是的,我知道它实际上是O(n ^ 2),因为退化的枢轴选择.但实际上,它落入我的O(n log(n))类别.)
• O(n ^ 2) - 您必须查看每对输入元素.
  • 或者你没有,但你认为你这样做,而你使用的是错误的算法.
• O(n ^ 3) - 嗯......我没有对这些进行快速表征.它可能是以下之一:
  • 你正在乘以矩阵
  • 您正在查看每对输入,但您执行的操作需要再次查看所有输入
  • 输入的整个图形结构是相关的
• O(2 ^ n) - 您需要考虑输入的每个可能子集.

这些都不严谨.特别是不是线性时间算法(O(n)):我可以提出一些例子,你必须看看所有的输入,然后是一半的输入,然后是其中的一半,等等.或者反过来说 - - 将输入对折叠在一起,然后递归输出.这些不符合上面的描述,因为你没有看过每个输入一次,但它仍然以线性时间出现.仍有99.2%的时间线性时间意味着每次输入一次.

Answer 6

很多这些都很容易用非编程的东西来展示,比如洗牌.

通过穿过整个甲板找到黑桃王牌,然后通过整个甲板找到黑桃2,等等,如果甲板已经向后排序,那么最坏情况n ^ 2将一副纸牌排序.你看了所有52张牌52次.

一般来说,真正糟糕的算法不一定是有意的,它们通常是对其他东西的误用,比如在一些其他方法中调用线性方法,这种方法在线性上重复同一组.

Answer 7

好的 - 这里有一些非常好的答案,但几乎所有这些答案似乎都犯了同样的错误,这是一个普遍存在的问题.

非正式地,我们写f(n)= O(g(n)),如果,直到比例因子,并且对于大于某些n0的所有n,g(n)大于 f(n).也就是说,f(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))来表示降价时f(n)的\ Theta) .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.但有时我们想谈谈平均甚至最佳案例的运行时间.

像往常一样,Vanilla quicksort就是一个很好的例子.在最坏的情况下它是T(n ^ 2)(它实际上至少需要n ^ 2步,但不会显着更多),但在平均情况下为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.

例如,quicksort(平均成本T(n.log n))和heapsort(平均成本T(n.log n))都是具有相同平均成本的排序算法 - 但快速排序通常比heapsort快得多.这是因为heapsort对每个元素进行了一些比quicksort更多的比较.

这并不是说O()符号是无用的,只是不精确.对于小n来说,这是一个非常直率的工具.

(作为本文的最后一点,请记住O()符号只描述任何函数的增长 - 它不一定是时间,可能是内存,在分布式系统中交换的消息或者需要的CPU数量.并行算法.)

Answer 8

我尝试通过在C#中提供简单的代码示例来解释.

对于 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(n log(n))看起来像

int result = 0;
foreach (int num in numbers)
{
    int index = numbers.length - 1;
    while (index > 1)
    {
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index /= 2;
    }
}
return result;

O(n ^ 2)看起来像

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;

O(n!)看起来像,呃,厌倦了想出任何简单的东西.
但我希望你得到一般意见？

Answer 9

我向非技术朋友描述的方式是这样的:

考虑多位数添加.良好的老式,铅笔和纸张添加.你在7-8岁时学到的那种.给定两个三位或四位数字,您可以相当容易地找出它们相加的内容.

如果我给你两个100位数的数字,然后问你他们加起来了什么,即使你不得不使用铅笔纸,弄清楚它也会非常简单.一个聪明的孩子可以在几分钟内完成这样的补充.这只需要大约100次操作.

现在,考虑多位乘法.你可能在大约8或9岁时就知道了.你(希望)做了很多重复练习来学习它背后的机制.

现在,想象一下,我给了你那两个100位的数字并告诉你将它们相乘.这将是一个很大,很多艰巨的任务,这东西会带你小时做-而且你不可能不出差错的事情.原因是(这个版本的)乘法是O(n ^ 2); 底部数字中的每个数字必须乘以顶部数字中的每个数字,总共大约n ^ 2个操作.在100位数字的情况下,这是10,000次乘法.

Answer 10

不,O(n)算法并不意味着它将对每个元素执行操作.Big-O表示法为您提供了一种方法,可以独立于您的实际机器来讨论算法的"速度".

O(n)表示算法采用的时间随着输入的增加而线性增长.O(n ^ 2)表示算法占用的时间随着输入的平方而增长.等等.

Answer 11

我想到的方式是,你的任务是清理一个挑选N的邪恶恶棍V引起的问题,你必须估计当他增加N时你需要多长时间才能完成你的问题.

O(1) - >增加N确实没有任何差别

O(log(N)) - >每当V加倍N时,你需要花费额外的时间T来完成任务.V再次加倍N,你花费相同的金额.

O(N) - >每当V加倍N时,你花费的时间是原来的两倍.

O(N ^ 2) - >每当V加倍N时,你花费的时间就是4倍.(这不公平!!!)

O(N log(N)) - >每当V加倍N时,你花费两倍的时间加上一点点.

这些是算法的界限; 计算机科学家想要描述它需要多长时间才能获得大的N.(当你考虑加密中使用的数字时,这一点很重要 - 如果计算机加速10倍,那么多少比特就会你必须使用它来确保它仍然需要100年才能打破你的加密而不仅仅是1年？)

如果某些界限对所涉及的人有所影响,则可能会有一些奇怪的表达.对于某些算法,我在Knuth的计算机编程艺术中看到过像O(N log(N)log(log(N))这样的东西.(不记得我的头顶哪一个)

Answer 12

由于某种原因尚未触及的一件事：

当您看到 O(2^n) 或 O(n^3) 或其他令人讨厌的值的算法时，通常意味着您将不得不接受问题的不完美答案才能获得可接受的性能。

在处理优化问题时，像这样爆炸的正确解决方案很常见。在合理的时间内给出的几乎正确的答案比机器腐烂很久之后给出的正确答案要好。

考虑国际象棋：我不知道正确的解决方案是什么，但它可能类似于 O(n^50) 甚至更糟。理论上，任何计算机都不可能真正计算出正确的答案——即使你使用宇宙中的每个粒子作为计算元素，在宇宙生命周期的最短可能时间内执行运算，你仍然剩下很多零。（量子计算机能否解决这个问题是另一回事。）