什么是"大O"符号的简单英语解释?

Arec Barrwin 4851 algorithm complexity-theory big-o computer-science time-complexity

我更喜欢尽可能少的正式定义和简单的数学.

cletus.. 6487

快速注意,这几乎肯定会混淆Big O符号(这是一个上限)与Theta符号(这是一个双边界限).根据我的经验,这实际上是非学术环境中的典型讨论.对所引起的任何混乱道歉.


使用此图可以显示Big O复杂度:

大O分析

我可以为Big-O表示法给出的最简单的定义是:

Big-O表示法是算法复杂性的相对表示.

在这句话中有一些重要且刻意选择的词:

  • 亲戚:你只能比较苹果和苹果.您无法将算法与算术乘法进行比较,而是对整数列表进行排序.但是比较两个算法进行算术运算(一次乘法,一次加法)会告诉你一些有意义的东西;
  • 表示: Big-O(最简单的形式)减少了算法与单个变量之间的比较.该变量基于观察或假设来选择.例如,通常基于比较操作来比较排序算法(比较两个节点以确定它们的相对排序).这假设比较昂贵.但是,如果比较便宜但交换费用昂贵呢?它改变了比较; 和
  • 复杂性:如果需要一秒钟才能对10,000个元素进行排序,那么我需要多长时间才能排序一百万个元素?在这种情况下,复杂性是对其他事物的相对衡量.

当你读完其余部分后,回过头来重读上面的内容.

我能想到的Big-O最好的例子就是做算术.取两个数字(123456和789012).我们在学校学到的基本算术运算是:

  • 加成;
  • 减法;
  • 乘法; 和
  • 师.

这些都是操作或问题.解决这些问题的方法称为算法.

增加是最简单的.您将数字向上排列(向右)并在列中添加数字,在结果中写入该添加的最后一个数字.该数字的"十"部分将转移到下一列.

让我们假设添加这些数字是该算法中最昂贵的操作.按理说,要将这两个数字加在一起,我们必须将6位数加在一起(并且可能带有7位数).如果我们将两个100位数字加在一起,我们必须做100次加法.如果我们添加两个 10,000位数字,我们必须添加10,000个.

看模式?的复杂性(即操作的次数)正比于数字数量Ñ在较大的数量.我们称之为O(n)线性复杂度.

减法是类似的(除了你可能需要借用而不是随身携带).

乘法是不同的.你将数字排成一行,取下面数字中的第一个数字,然后依次将它与顶部数字中的每个数字相乘,依此类推.因此,要将两个6位数相乘,我们必须进行36次乘法运算.我们可能需要多做10或11列添加才能获得最终结果.

如果我们有两个100位数字,我们需要进行10,000次乘法和200次加法.对于两百万个数字,我们需要进行一万亿(10 12)次乘法和两百万次加法.

当算法按n 平方缩放时,这是O(n 2)二次复杂度.这是介绍另一个重要概念的好时机:

我们只关心复杂性中最重要的部分.

精明的人可能已经意识到我们可以将操作次数表示为:n 2 + 2n.但正如你从我们的例子中看到的那样,每个数字有两个数字,第二个词(2n)变得微不足道(占该阶段总操作的0.0002%).

人们可以注意到我们已经假设了最糟糕的情况.如果其中一个是4位数而另一个是6位数,则乘以6位数字,那么我们只有24次乘法.我们仍然计算'n'的最坏情况,即当两者都是6位数时.因此,Big-O表示法是关于算法的最坏情况

电话簿

我能想到的下一个最好的例子是电话簿,通常称为白页或类似的,但它会因国家而异.但我说的是那个按姓氏列出人名,然后是姓名首字母或名字,可能是地址,然后是电话号码的人.

现在,如果您指示计算机在包含1,000,000个名字的电话簿中查找"John Smith"的电话号码,您会怎么做?忽略一个事实,你可以猜到S的开始有多远(让我们假设你不能),你会做什么?

一个典型的实现可能是开到中间,拿50万,并把它比作"史密斯".如果恰好是"史密斯,约翰",我们真的很幸运.更有可能的是,"约翰史密斯"将在该名称之前或之后.如果是在我们之后,我们将电话簿的后半部分分成两半并重复.如果是在那之前,我们将电话簿的前半部分分成两半并重复.等等.

这称为二进制搜索,无论您是否意识到,它每天都会在编程中使用.

因此,如果您想在一百万个名字的电话簿中找到一个名字,您最多可以通过这样做20次来找到任何名称.在比较搜索算法时,我们认为这种比较是我们的'n'.

  • 对于3个名字的电话簿,它需要进行2次比较(最多).
  • 对于7最多需要3个.
  • 15岁需要4个.
  • ...
  • 1,000,000需要20.

那是惊人的好不是吗?

在Big-O术语中,这是O(log n)对数复杂度.现在,所讨论的对数可以是ln(基数e),log 10,log 2或其他一些基数.无论如何它仍然是O(log n)就像O(2n 2)和O(100n 2)仍然都是O(n 2).

在这一点上值得解释的是Big O可用于通过算法确定三种情况:

  • 最佳案例:在电话簿搜索中,最好的情况是我们在一次比较中找到了名称.这是O(1)不变的复杂性 ;
  • 预期案例:如上所述,这是O(log n); 和
  • 最坏情况:这也是O(log n).

通常我们不关心最好的情况.我们对预期和最坏的情况感兴趣.有时这些中的一个或另一个将更重要.

回到电话簿.

如果您有电话号码并想要找到名字怎么办?警方有一本反向电话簿,但这些查询被公众拒绝.或者是他们?从技术上讲,您可以在普通电话簿中反向查找数字.怎么样?

您从名字开始并比较数字.如果它是一场比赛,那么很棒,如果没有,你继续前进.你必须这样做,因为电话簿是无序的(无论如何通过电话号码).

所以要给出一个给出电话号码的名字(反向查询):

  • 最佳案例: O(1);
  • 预期案例: O(n)(500,000); 和
  • 最坏情况: O(n)(1,000,000).

旅行推销员

这是计算机科学中一个非常着名的问题,值得一提.在这个问题上你有N个城镇.这些城镇中的每一个都通过一定距离的道路与一个或多个其他城镇相连.旅行推销员的问题是找到访问每个城镇的最短旅行.

听起来很简单?再想想.

如果您有3个城镇A,B和C,所有城市之间都有道路,那么您可以去:

  • A→B→C
  • A→C→B
  • B→C→A
  • B→A→C
  • C→A→B
  • C→B→A

实际上还不到那个,因为其中一些是等价的(例如,A→B→C和C→B→A是等价的,因为它们使用相同的道路,正好相反).

实际上有3种可能性.

  • 把它带到4个城镇,你有(iirc)12种可能性.
  • 5岁就是60岁.
  • 6变为360.

这是称为阶乘的数学运算的函数.基本上:

  • 5!= 5×4×3×2×1 = 120
  • 6!= 6×5×4×3×2×1 = 720
  • 7!= 7×6×5×4×3×2×1 = 5040
  • ...
  • 25!= 25×24×...×2×1 = 15,511,210,043,330,985,984,000,000
  • ...
  • 50!= 50×49×...×2×1 = 3.04140932×10 64

因此,旅行商问题的大O是O(n!)阶乘或组合复杂性.

当你到达200个城镇时,宇宙中没有足够的时间来解决传统计算机的问题.

需要考虑的事情.

多项式时间

我想要快速提及的另一点是,任何具有O(n a)复杂度的算法都被认为具有多项式复杂性或者在多项式时间内是可解的.

O(n),O(n 2)等都是多项式时间.有些问题在多项式时间内无法解决.因此,世界上使用了某些东西.公钥加密是一个很好的例子.在计算上很难找到两个非常大的素数因子.如果不是,我们就无法使用我们使用的公钥系统.

无论如何,这就是我对Big O(修订版)的解释(希望是简单的英语).

  • 而其他答案则侧重于解释O(1),O(n ^ 2)等人之间的差异......你的问题是详细说明如何将算法分类为n ^ 2,nlog(n)等.+ 1是一个很好的答案,帮助我理解Big O符号 (571认同)
  • -1:这是明显错误的:_"BigOh是算法复杂性的相对表示".不,BigOh是一个渐近的上界,并且很好地独立于计算机科学.O(n)是线性的.不,你把BigOh与theta混淆了.log n是O(n).1是O(n).这个答案(以及评论)的赞成数量,这使得将Theta与BigOh混淆的基本错误令人非常尴尬...... (167认同)
  • _"当你到达200个城镇时,宇宙中没有足够的时间来解决传统计算机的问题."_当宇宙即将结束时? (72认同)
  • 有人可能想补充一点,大O代表一个上界(由算法给出),大欧米茄给出一个下界(通常作为独立于特定算法的证明)和大-Theta意味着一个"最优"算法达到那个下限是众所周知的. (22认同)
  • 如果你正在寻找最长的答案,这是很好的,但不是以最简单的方式解释Big-O的答案. (21认同)
  • 我关注的是@jimifiki.Big-O仅在N很大时才有用.当N很小时,前因子通常很重要.一个很好的例子是[插入排序](http://en.wikipedia.org/wiki/Insertion_sort).插入排序是O(N ^ 2),但具有非常好的缓存局部性.当列表很小(<10个元素)时,这使得它比许多O(N log N)算法更快.类似地,对于小N,在二叉树中查找通常比哈希表更快.良好的散列函数可以咀嚼很多循环,使前因非常重要. (8认同)
  • @Moberg f(n)为O(g(n))的事实不排除f(n)对于与g(n)不同的h(n)为O(h(n))的可能性.平凡地,n是O(n)并且n也是O(2n).实际上,O(log(n))是O(n)的子集.所以在log(n)的例子中,log(n)都在O(log(n))和O(n)中.你混淆了Theta符号和大O符号. (7认同)
  • @Isaac这并不重要:`200!纳秒〜= 1.8×10 ^ 348×宇宙年龄`https://www.wolframalpha.com/input/?i=200%21+nanoseconds (5认同)
  • 观众,不要忘记这个答案中的错误让Big-O,Omega和Theta感到困惑.阅读这个答案,欣赏它,然后查找Theta(粗略预期案例)和Omega(粗略下限); 因为Big-O完全是粗糙的上限. (4认同)
  • @Paul Fisher:NP-hard并不意味着"比最难的NP完全问题更难",它意味着"至少和NP完全问题一样难".有一个很大的区别! (2认同)
  • 我猜他应该回答Omega和Theta,以便上面的所有评论都会得到回答,也会建议将问题改为bigOh和omega以及theta之间的差异. (2认同)
  • @Aryabhatta你的意思是log(n)是O(n)?log(n)显然是O(log(n)),不是吗?(见http://en.wikipedia.org/wiki/Big_oh_notation) (2认同)
  • @JacobAkkerboom啊,是的,这也是事实.我正在以正确的方式阅读帖子.事情并不是那么清楚.虽然,我并没有把它与Theta混淆.因为我之前从未听说过Theta.但显然它是平均值而不是上限. (2认同)
  • `传统计算机可以解决多项式时间问题.他们可以或不可以吗? (2认同)
  • 当j是常数时,@ Josh`log(n ^ c)= c*log(n)`和`O(c*log(n))= O(log(n))`.所以,`O(log(n ^ 2))= O(log(n ^ 3))= O(log(n))`.因此,更改日志库不会影响大O表示法,并且您引用的语句是正确的. (2认同)

Ray Hidayat.. 711

它显示了算法如何扩展.

O(n 2):称为二次复杂度

  • 1项:1秒
  • 10项:100秒
  • 100项:10000秒

注意,项目数由10倍的增加,但通过10倍的时间增加2.基本上,n = 10,因此O(n 2)给出了比例因子n 2,即10 2.

O(n):称为线性复杂度

  • 1项:1秒
  • 10项:10秒
  • 100项:100秒

这次项目数量增加了10倍,时间也增加了10倍.n = 10,所以O(n)的比例因子是10.

O(1):称为常数复杂度

  • 1项:1秒
  • 10项:1秒
  • 100项:1秒

项目数仍然增加10倍,但O(1)的比例因子始终为1.

O(log n):称为对数复杂度

  • 1项:1秒
  • 10项:2秒
  • 100项:3秒
  • 1000项:4秒
  • 10000项:5秒

计算次数仅增加输入值的对数.因此,在这种情况下,假设每次计算需要1秒n,因此输入的日志是所需的时间log n.

这是它的要点.他们减少了数学,因此它可能不是n 2或它们所说的任何东西,但这将是缩放的主要因素.

  • 不是秒,操作.而且,你错过了阶乘和对数时间. (102认同)
  • 这并不能很好地解释O(n ^ 2)可能正在描述一个精确运行的算法.01*n ^ 2 + 999999*n + 999999.重要的是要知道算法是用这个比例进行比较的,那个当n'足够大'时,比较有效.Python的timsort实际上对小型数组使用插入排序(最差/平均情况O(n ^ 2)),因为它的开销很小. (7认同)
  • 这个答案也混淆了大O符号和Theta符号.对于所有输入(通常简写为1)返回1的n的函数实际上是O(n ^ 2)(即使它也在O(1)中).类似地,仅需要执行花费恒定时间量的一个步骤的算法也被认为是O(1)算法,但也被认为是O(n)和O(n ^ 2)算法.但也许数学家和计算机科学家不同意这个定义: - /. (6认同)
  • 这个定义到底意味着什么?(项目数仍然增加10倍,但O(1)的比例因子始终为1.) (4认同)

ninjagecko.. 393

当你忽略原点附近的常数因子和东西时, Big-O表示法(也称为"渐近增长"表示法)是"看起来像"的功能.我们用它来谈论事物的规模.


基本

对于"足够"的大输入......

  • f(x) ? O(upperbound)意思是f"增长不快"upperbound
  • f(x) ? ?(justlikethis)意思是f"长得很像"justlikethis
  • f(x) ? ?(lowerbound)意思是f"增长不慢"lowerbound

big-O notation doesn't care about constant factors: the function 9x² is said to "grow exactly like" 10x². Neither does big-O asymptotic notation care about non-asymptotic stuff ("stuff near the origin" or "what happens when the problem size is small"): the function 10x² is said to "grow exactly like" 10x² - x + 2.

Why would you want to ignore the smaller parts of the equation? Because they become completely dwarfed by the big parts of the equation as you consider larger and larger scales; their contribution becomes dwarfed and irrelevant. (See example section.)

Put another way, it's all about the ratio as you go to infinity. If you divide the actual time it takes by the O(...), you will get a constant factor in the limit of large inputs. Intuitively this makes sense: functions "scale like" one another if you can multiply one to get the other. That is, when we say...

actualAlgorithmTime(N) ? O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... this means that for "large enough" problem sizes N (if we ignore stuff near the origin), there exists some constant (e.g. 2.5, completely made up) such that:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
?????????????????????? < constant            ????????????????????? < 2.5 
       bound(N)                                    N log(N)         

There are many choices of constant; often the "best" choice is known as the "constant factor" of the algorithm... but we often ignore it like we ignore non-largest terms (see Constant Factors section for why they don't usually matter). You can also think of the above equation as a bound, saying "In the worst-case scenario, the time it takes will never be worse than roughly N*log(N), within a factor of 2.5 (a constant factor we don't care much about)".

In general, O(...) is the most useful one because we often care about worst-case behavior. If f(x) represents something "bad" like processor or memory usage, then "f(x) ? O(upperbound)" means "upperbound is the worst-case scenario of processor/memory usage".


Applications

作为纯粹的数学结构,big-O表示法不仅限于讨论处理时间和内存.您可以使用它来讨论缩放有意义的任何事物的渐近性,例如:

  • N聚会中人们可能握手的次数(?(N²)具体而言N(N-1)/2,但重要的是它"按比例缩放" )
  • 概率预期的一些人将某些病毒式营销视为时间的函数
  • 网站延迟如何随CPU或GPU或计算机集群中的处理单元数量而变化
  • CPU上的热量输出如何随晶体管数量,电压等而变化.
  • 作为输入大小的函数,算法需要运行多长时间
  • 作为输入大小的函数,算法需要运行多少空间

For the handshake example above, everyone in a room shakes everyone else's hand. In that example, #handshakes ? ?(N²). Why?

Back up a bit: the number of handshakes is exactly n-choose-2 or N*(N-1)/2 (each of N people shakes the hands of N-1 other people, but this double-counts handshakes so divide by 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article. adjacency matrix

However, for very large numbers of people, the linear term N is dwarfed and effectively contributes 0 to the ratio (in the chart: the fraction of empty boxes on the diagonal over total boxes gets smaller as the number of participants becomes larger). Therefore the scaling behavior is order N², or the number of handshakes "grows like N²".

#handshakes(N)
?????????????? ? 1/2
     N²

It's as if the empty boxes on the diagonal of the chart (N*(N-1)/2 checkmarks) weren't even there (N2 checkmarks asymptotically).

(temporary digression from "plain English":) If you wanted to prove this to yourself, you could perform some simple algebra on the ratio to split it up into multiple terms (lim means "considered in the limit of", just ignore it if you haven't seen it, it's just notation for "and N is really really big"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ?????????? = lim ( ?????? - ??? ) = lim ??? = 1/2
N??     N²       N??     N²     N²      N??  1
                               ?????
             this is 0 in the limit of N??:
             graph it, or plug in a really large number for N

tl;dr: The number of handshakes 'looks like' x² so much for large values, that if we were to write down the ratio #handshakes/x², the fact that we don't need exactly x² handshakes wouldn't even show up in the decimal for an arbitrarily large while.

e.g. for x=1million, ratio #handshakes/x²: 0.499999...


Building Intuition

This lets us make statements like...

"For large enough inputsize=N, no matter what the constant factor is, if I double the input size...

  • ... I double the time an O(N) ("linear time") algorithm takes."

    N ? (2N) = 2(N)

  • ... I double-squared (quadruple) the time an O(N²) ("quadratic time") algorithm takes." (e.g. a problem 100x as big takes 100²=10000x as long... possibly unsustainable)

    ? (2N)² = 4()

  • ... I double-cubed (octuple) the time an O(N³) ("cubic time") algorithm takes." (e.g. a problem 100x as big takes 100³=1000000x as long... very unsustainable)

    cN³ ? c(2N)³ = 8(cN³)

  • ... I add a fixed amount to the time an O(log(N)) ("logarithmic time") algorithm takes." (cheap!)

    c log(N) ? c log(2N) = (c log(2))+(c log(N)) = (fixed amount)+(c log(N))

  • ... I don't change the time an O(1) ("constant time") algorithm takes." (the cheapest!)

    c*1 ? c*1

  • ... I "(basically) double" the time an O(N log(N)) algorithm takes." (fairly common)

    it's less than O(N1.000001), which you might be willing to call basically linear

  • ... I ridiculously increase the time a O(2N) ("exponential time") algorithm takes." (you'd double (or triple, etc.) the time just by increasing the problem by a single unit)

    2N ? 22N = (4N)............put another way...... 2N ? 2N+1 = 2N21 = 2 2N

[for the mathematically inclined, you can mouse over the spoilers for minor sidenotes]

(with credit to /sf/ask/17360801/ )

(technically the constant factor could maybe matter in some more esoteric examples, but I've phrased things above (e.g. in log(N)) such that it doesn't)

These are the bread-and-butter orders of growth that programmers and applied computer scientists use as reference points. They see these all the time. (So while you could technically think "Doubling the input makes an O(?N) algorithm 1.414 times slower," it's better to think of it as "this is worse than logarithmic but better than linear".)


Constant factors

Usually we don't care what the specific constant factors are, because they don't affect the way the function grows. For example, two algorithms may both take O(N) time to complete, but one may be twice as slow as the other. We usually don't care too much unless the factor is very large, since optimizing is tricky business ( When is optimisation premature? ); also the mere act of picking an algorithm with a better big-O will often improve performance by orders of magnitude.

Some asymptotically superior algorithms (e.g. a non-comparison O(N log(log(N))) sort) can have so large a constant factor (e.g. 100000*N log(log(N))), or overhead that is relatively large like O(N log(log(N))) with a hidden + 100*N, that they are rarely worth using even on "big data".


Why O(N) is sometimes the best you can do, i.e. why we need datastructures

O(N) algorithms are in some sense the "best" algorithms if you need to read all your data. The very act of reading a bunch of data is an O(N) operation. Loading it into memory is usually O(N) (or faster if you have hardware support, or no time at all if you've already read the data). However if you touch or even look at every piece of data (or even every other piece of data), your algorithm will take O(N) time to perform this looking. Nomatter how long your actual algorithm takes, it will be at least O(N) because it spent that time looking at all the data.

The same can be said for the very act of writing. All algorithms which print out N things will take N time, because the output is at least that long (e.g. printing out all permutations (ways to rearrange) a set of N playing cards is factorial: O(N!)).

This motivates the use of data structures: a data structure requires reading the data only once (usually O(N) time), plus some arbitrary amount of preprocessing (e.g. O(N) or O(N log(N)) or O(N²)) which we try to keep small. Thereafter, modifying the data structure (insertions/deletions/etc.) and making queries on the data take very little time, such as O(1) or O(log(N)). You then proceed to make a large number of queries! In general, the more work you're willing to do ahead of time, the less work you'll have to do later on.

For example, say you had the latitude and longitude coordinates of millions of roads segments, and wanted to find all street intersections.

  • Naive method: If you had the coordinates of a street intersection, and wanted to examine nearby streets, you would have to go through the millions of segments each time, and check each one for adjacency.
  • If you only needed to do this once, it would not be a problem to have to do the naive method of O(N) work only once, but if you want to do it many times (in this case, N times, once for each segment), we'd have to do O(N²) work, or 1000000²=1000000000000 operations. Not good (a modern computer can perform about a billion operations per second).
  • If we use a simple structure called a hash table (an instant-speed lookup table, also known as a hashmap or dictionary), we pay a small cost by preprocessing everything in O(N) time. Thereafter, it only takes constant time on average to look up something by its key (in this case, our key is the latitude and longitude coordinates, rounded into a grid; we search the adjacent gridspaces of which there are only 9, which is a constant).
  • Our task went from an infeasible O(N²) to a manageable O(N), and all we had to do was pay a minor cost to make a hash table.
  • analogy: The analogy in this particular case is a jigsaw puzzle: We created a data structure which exploits some property of the data. If our road segments are like puzzle pieces, we group them by matching color and pattern. We then exploit this to avoid doing extra work later (comparing puzzle pieces of like color to each other, not to every other single puzzle piece).

The moral of the story: a data structure lets us speed up operations. Even more advanced data structures can let you combine, delay, or even ignore operations in incredibly clever ways. Different problems would have different analogies, but they'd all involve organizing the data in a way that exploits some structure we care about, or which we've artificially imposed on it for bookkeeping. We do work ahead of time (basically planning and organizing), and now repeated tasks are much much easier!


Practical example: visualizing orders of growth while coding

Asymptotic notation is, at its core, quite separate from programming. Asymptotic notation is a mathematical framework for thinking about how things scale, and can be used in many different fields. That said... this is how you apply asymptotic notation to coding.

The basics: Whenever we interact with every element in a collection of size A (such as an array, a set, all keys of a map, etc.), or perform A iterations of a loop, that is a multiplcative factor of size A. Why do I say "a multiplicative factor"?--because loops and functions (almost by definition) have multiplicative running time: the number of iterations, times work done in the loop (or for functions: the number of times you call the function, times work done in the function). (This holds if we don't do anything fancy, like skip loops or exit the loop early, or change control flow in the function based on arguments, which is very common.) Here are some examples of visualization techniques, with accompanying pseudocode.

(here, the xs represent constant-time units of work, processor instructions, interpreter opcodes, whatever)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Example 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Example 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

If we do something slightly complicated, you might still be able to imagine visually what's going on:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Here, the smallest recognizable outline you can draw is what matters; a triangle is a two dimensional shape (0.5 A^2), just like a square is a two-dimensional shape (A^2); the constant factor of two here remains in the asymptotic ratio between the two, however we ignore it like all factors... (There are some unfortunate nuances to this technique I don't go into here; it can mislead you.)

Of course this does not mean that loops and functions are bad; on the contrary, they are the building blocks of modern programming languages, and we love them. However, we can see that the way we weave loops and functions and conditionals together with our data (control flow, etc.) mimics the time and space usage of our program! If time and space usage becomes an issue, that is when we resort to cleverness, and find an easy algorithm or data structure we hadn't considered, to reduce the order of growth somehow. Nevertheless, these visualization techniques (though they don't always work) can give you a naive guess at a worst-case running time.

Here is another thing we can recognize visually:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

We can just rearrange this and see it's O(N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

Or maybe you do log(N) passes of the data, for O(N*log(N)) total time:

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Unrelatedly but worth mentioning again: If we perform a hash (e.g. a dictionary/hashtable lookup), that is a factor of O(1). That's pretty fast.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

If we do something very complicated, such as with a recursive function or divide-and-conquer algorithm, you can use the Master Theorem (usually works), or in ridiculous cases the Akra-Bazzi Theorem (almost always works) you look up the running time of your algorithm on Wikipedia.

But, programmers don't think like this because eventually, algorithm intuition just becomes second nature. You will start to code something inefficient, and immediately think "am I doing something grossly inefficient?". If the answer is "yes" AND you foresee it actually mattering, then you can take a step back and think of various tricks to make things run faster (the answer is almost always "use a hashtable", rarely "use a tree", and very rarely something a bit more complicated).


Amortized and average-case complexity

There is also the concept of "amortized" and/or "average case" (note that these are different).

Average Case: This is no more than using big-O notation for the expected value of a function, rather than the function itself. In the usual case where you consider all inputs to be equally likely, the average case is just the average of the running time. For example with quicksort, even though the worst-case is O(N^2) for some really bad inputs, the average case is the usual O(N log(N)) (the really bad inputs are very small in number, so few that we don't notice them in the average case).

Amortized Worst-Case: Some data structures may have a worst-case complexity that is large, but guarantee that if you do many of these operations, the average amount of work you do will be better than worst-case. For example you may have a data structure that normally takes constant O(1) time. However, occasionally it will 'hiccup' and take O(N) time for one random operation, because maybe it needs to do some bookkeeping or garbage collection or something... but it promises you that if it does hiccup, it won't hiccup again for N more operations. The worst-case cost is still O(N) per operation, but the amortized cost over many runs is O(N)/N = O(1) per operation. Because the big operations are sufficiently rare, the massive amount of occasional work can be considered to blend in with the rest of the work as a constant factor. We say the work is "amortized" over a sufficiently large number of calls that it disappears asymptotically.

The analogy for amortized analysis:

You drive a car. Occasionally, you need to spend 10 minutes going to the gas station and then spend 1 minute refilling the tank with gas. If you did this every time you went anywhere with your car (spend 10 minutes driving to the gas station, spend a few seconds filling up a fraction of a gallon), it would be very inefficient. But if you fill up the tank once every few days, the 11 minutes spent driving to the gas station is "amortized" over a sufficiently large number of trips, that you can ignore it and pretend all your trips were maybe 5% longer.

Comparison between average-case and amortized worst-case:

  • Average-case: We make some assumptions about our inputs; i.e. if our inputs have different probabilities, then our outputs/runtimes will have different probabilities (which we take the average of). Usually we assume that our inputs are all equally likely (uniform probability), but if the real-world inputs don't fit our assumptions of "average input", the average output/runtime calculations may be meaningless. If you anticipate uniformly random inputs though, this is useful to think about!
  • Amortized worst-case: If you use an amortized worst-case data structure, the performance is guaranteed to be within the am

    • 据推测,OP以外的人可能会对这个问题的答案感兴趣.这不是网站的指导原则吗? (38认同)
    • 一个很好的数学答案,但OP要求一个简单的英语答案.这种水平的数学描述不是理解答案所必需的,尽管对于特别注重数学的人来说,理解它可能比"普通英语"简单得多.然而OP要求后者. (25认同)
    • 虽然我可以看到为什么人们会撇开我的答案,并认为它太蹩脚(特别是"数学是新的普通英语"讽刺言论,自从删除),原始问题询问关于函数的大O,所以我试图明确地以一种补充普通英语直觉的方式谈论功能.这里的数学经常可以被掩盖,或者用高中数学背景来理解.我确实觉得人们最后可能会看到数学附录,并认为这是答案的一部分,当它只是在那里看到*真实*数学的样子. (6认同)
    • 这是一个很棒的答案; 比投票最多的IMO要好得多.所需的"数学"不会超出理解"O"之后括号中的表达式所需要的,没有使用任何示例的合理解释可以避免. (5认同)

Jon Skeet.. 242

编辑:快速注意,这几乎肯定会混淆Big O符号(这是一个上限)与Theta符号(这是一个上限和下限).根据我的经验,这实际上是非学术环境中的典型讨论.对所引起的任何混乱道歉.

用一句话:随着工作规模的增加,完成工作需要多长时间?

显然,只使用"大小"作为输入,"时间"作为输出 - 如果你想谈论内存使用等,同样的想法也适用.

这是一个我们想要干燥的N T恤的例子.我们假设让它们处于干燥位置非常快(即人类的相互作用可以忽略不计).现实情况并非如此,当然......

  • 在外面使用清洗线:假设你有一个无限大的后院,洗涤在O(1)时间内干燥.无论你有多少,它都会得到相同的阳光和新鲜空气,因此尺寸不会影响干燥时间.

  • 使用滚筒式烘干机:每次装入10件衬衫,然后一小时后完成.(忽略这里的实际数字 - 它们是无关紧要的.)因此,干燥50件衬衫所需的时间约为干燥10件衬衫的5倍.

  • 将所有东西放在一个通风橱中:如果我们将所有东西都放在一个大堆中,只是让一般的温暖,它将需要很长时间才能使中间衬衫变干.我不想猜测细节,但我怀疑这至少是O(N ^ 2) - 随着你增加洗涤负荷,干燥时间增加得更快.

"大O"符号的一个重要方面是它没有说明给定大小的哪种算法会更快.获取哈希表(字符串键,整数值)与对数组(字符串,整数).基于字符串,在哈希表或数组中的元素中查找键是否更快?(即对于数组,"找到字符串部分与给定键匹配的第一个元素.")哈希表通常是摊销的(〜="平均")O(1) - 一旦它们被设置,它应该采取同时在100条目表中查找条目,如1,000,000条目表中所示.在数组中查找元素(基于内容而不是索引)是线性的,即O(N) - 平均而言,您将不得不查看一半条目.

这是否使哈希表比查找数组更快?不必要.如果你有一个非常小的条目集合,一个数组可能会更快 - 你可以在计算你正在查看的哈希码的时间内检查所有字符串.然而,随着数据集变大,哈希表最终会击败数组.

  • jon的解释对我认为的问题非常重要.这正是一个人可以向某个妈妈解释它的方式,她最终会理解它我认为:)我喜欢衣服的例子(特别是最后一个,它解释了复杂性的指数增长) (7认同)
  • 哈希表需要运行算法来计算实际数组的索引(取决于实现).数组只有O(1),因为它只是一个地址.但这与问题无关,只是一个观察:) (6认同)
  • Filip:我不是在谈论通过索引来解决数组,我在谈论在数组中找到匹配的条目.你能重新阅读答案,看看是否仍然不清楚? (4认同)
  • @Filip Ekberg我想你正在考虑一个直接地址表,其中每个索引直接映射到一个键,因此是O(1),但我相信Jon正在讨论一个未排序的键/值对数组,你必须搜索通过线性. (3认同)
  • @RBT:不,这不是二元查询.只需基于从哈希码到桶索引的转换,它就可以立即获得正确的哈希*桶*.之后,在存储桶中找到正确的哈希码可能是线性的,也可能是二进制搜索...但到那时你只需要字典总大小的一小部分. (2认同)

starblue.. 124

Big O描述了当输入变大时函数的增长行为的上限,例如程序的运行时.

例子:

  • O(n):如果我将输入大小加倍,则运行时间加倍

  • O(n 2):如果输入大小加倍运行时四倍

  • O(log n):如果输入大小加倍,则运行时间增加1

  • O(2 n):如果输入大小增加1,则运行时间加倍

输入大小通常是表示输入所需的位数.

  • 不正确!例如O(n):如果我将输入大小加倍,则运行时将乘以有限非零常数.我的意思是O(n)= O(n + n) (7认同)
  • 我在谈论f(n)= O(g(n))中的f,而不是你似乎理解的g. (7认同)
  • 您应该为O(n log n)添加一个示例. (5认同)

cdiggins.. 104

程序员最常使用Big O表示法作为计算(算法)完成所需时间的近似度量,表示为输入集大小的函数.

Big O可用于比较两种算法随着输入数量的增加而扩展的程度.

更准确地说,Big O表示法用于表示函数的渐近行为.这意味着函数在接近无穷大时的行为方式.

在许多情况下,算法的"O"将属于以下情况之一:

  • O(1) - 无论输入集的大小如何,完成时间都是相同的.一个例子是通过索引访问数组元素.
  • O(Log N) - 完成时间大致与log2(n)一致.例如,1024个项目大约需要32个项目的两倍,因为Log2(1024)= 10并且Log2(32)= 5.例如,在二叉搜索树(BST)中查找项目.
  • O(N) - 完成时间与输入集的大小成线性比例.换句话说,如果您将输入集中的项目数加倍,则算法大约需要两倍的时间.一个例子是计算链表中的项目数.
  • O(N Log N) - 完成时间增加项目数乘以Log2(N)的结果.一个例子是堆排序快速排序.
  • O(N ^ 2) - 完成时间大致等于项目数的平方.一个例子是冒泡排序.
  • O(N!) - 完成时间是输入集的阶乘.这方面的一个例子是旅行商问题暴力解决方案.

当输入大小朝向无穷大增加时,Big O忽略了对函数的增长曲线没有有意义贡献的因素.这意味着简单地忽略了添加到函数或乘以函数的常量.


Filip Ekberg.. 81

Big O只是一种以一种常见方式"表达"自己的方式,"运行我的代码需要多少时间/空间?".

您可能经常看到O(n),O(n 2),O(nlogn)等等,所有这些只是展示的方式; 算法如何改变?

O(n)意味着大O是n,现在你可能会想,"什么是n!?" "n"是元素的数量.想要在阵列中搜索项目的图像.您必须查看每个元素并将其视为"您是正确的元素/项目吗?" 在最坏的情况下,该项目位于最后一个索引,这意味着它花费的时间与列表中的项目一样多,因此为了通用,我们说"哦,嘿,n是一个公平的给定数量的值!" .

那么你可能会理解"n 2 "意味着什么,但更具体地说,你可以想到你有一个简单,最简单的排序算法; 冒泡.该算法需要查看每个项目的整个列表.

我的列表

  1. 1
  2. 6
  3. 3

这里的流程将是:

  • 比较1和6,哪个最大?Ok 6处于正确的位置,向前迈进!
  • 比较6和3,哦,3更少!让我们动起来吧,好的清单改变了,我们需要从现在开始!

这是O n 2因为,您需要查看列表中的所有项目都有"n"项.对于每个项目,您再次查看所有项目,为了进行比较,这也是"n",因此对于每个项目,您看起来"n"次意味着n*n = n 2

我希望这就像你想要的一样简单.

但请记住,Big O只是一种以时间和空间的方式超越自我的方式.


Wedge.. 54

Big O描述了算法的基本缩放特性.

Big O没有告诉你有关给定算法的大量信息.它切入骨骼并仅提供有关算法的缩放性质的信息,特别是算法的资源使用(思考时间或内存)如何根据"输入大小"进行缩放.

考虑蒸汽机和火箭之间的区别.它们不仅仅是同一种物品的不同品种(例如,普锐斯发动机与兰博基尼发动机),但它们的核心是不同类型的推进系统.蒸汽机可能比玩具火箭更快,但没有蒸汽活塞发动机能够达到轨道运载火箭的速度.这是因为这些系统在达到给定速度("输入尺寸")所需的燃料关系("资源使用")方面具有不同的缩放特性.

为什么这个这么重要?因为软件处理的问题可能因数据大小不同而有所不同.考虑一下.前往月球所需的速度与人类行走速度之间的比率小于10,000:1,与软件可能面临的输入尺寸范围相比,这是非常小的.而且由于软件可能面临输入大小的天文范围,因此算法的Big O复杂性可能会超越任何实现细节,这是基本的扩展性质.

考虑规范排序示例.冒泡排序为O(n 2),而合并排序为O(n log n).假设您有两个排序应用程序,即使用冒泡排序的应用程序A和使用合并排序的应用程序B,并且假设对于大约30个元素的输入大小,应用程序A在排序时比应用程序B快1,000倍.如果您不必排序超过30个元素,那么您应该更喜欢应用程序A,因为它在这些输入大小上要快得多.但是,如果您发现可能需要对一千万个项目进行排序,那么您所期望的是,在这种情况下,应用程序B实际上最终比应用程序A快数千倍,这完全取决于每种算法的扩展方式.


Andrew Prock.. 39

这是在解释Big-O的常见变种时我倾向于使用的普通英语动物

在所有情况下,更喜欢列表中较高的算法到列表中较低的算法.但是,迁移到更昂贵的复杂性类别的成本差别很大.

O(1):

没有增长.无论问题有多大,您都可以在相同的时间内解决问题.这有点类似于广播,其中在给定距离上广播需要相同的能量,而不管广播范围内的人数.

O(log n):

这种复杂性与O(1)相同,只是它稍微差一点.出于所有实际目的,您可以将其视为非常大的常量缩放.处理1千到10亿件物品之间的工作差异只是因素六.

O(n):

解决问题的成本与问题的大小成正比.如果您的问题规模增加一倍,那么解决方案的成本会翻倍.由于大多数问题必须以某种方式扫描到计算机中,如数据输入,磁盘读取或网络流量,这通常是一个负担得起的缩放因子.

O(n log n):

这种复杂性与O(n)非常相似.出于所有实际目的,这两者是等价的.这种复杂程度通常仍被认为是可扩展的.通过调整假设,可以将一些O(n log n)算法转换为O(n)算法.例如,限制键的大小会减少从O(n log n)O(n)的排序.

O(n 2):

生长为正方形,其中n是正方形边长.这与"网络效应"的增长率相同,网络中的每个人都可能知道网络中的其他人.增长是昂贵的.大多数可扩展的解决方案不能使用具有这种复杂程度的算法,而无需进行重要的体操.这通常适用于所有其他多项式复杂度 - O(n k) - .

O(2 n):

不规模.你没有希望解决任何非平凡的问题.有助于知道要避免什么,以及专家找到O(n k)中的近似算法.

  • 你能否考虑一下O(1)的另一个类比?我的工程师想要讨论由于障碍物造成的射频阻抗. (2认同)
  • 我确实使用了"有点"这个词. (2认同)

Brownie.. 36

Big O是算法相对于其输入大小使用的时间/空间的度量.

如果算法是O(n),那么时间/空间将以与其输入相同的速率增加.

如果算法是O(n 2),则时间/空间以其输入平方的速率增加.

等等.

  • 我一直相信它可以是时间或空间.但不是两个同时. (13认同)
  • 复杂性绝对可以是空间.看看这个:http://en.wikipedia.org/wiki/PSPACE (9认同)
  • 这个答案是这里最"平淡"的答案.以前的人实际上假设读者已经足够了解他们,但作家并不知道.他们认为他们很简单,但绝对不是.用漂亮的格式编写大量文本并制作难以为非CS人员制作的花哨的人工例子并不简单明了,对于大多数CS人来说非常有吸引力.用简单的英语解释CS术语根本不需要代码和数学.这个答案的+1虽然还不够好. (4认同)
  • 这不是空间.这是关于复杂性,这意味着时间. (2认同)

James Oravec.. 32

什么是Big O的简单英语解释?尽可能少的正式定义和简单的数学.

关于Big-O符号需要的简单英语解释:

当我们编程时,我们正试图解决问题.我们编码的是一种算法.Big O表示法允许我们以标准化方式比较算法的最差情况.硬件规格随时间而变化,硬件的改进可以减少算法运行所需的时间.但是替换硬件并不意味着我们的算法随着时间的推移会更好或改进,因为我们的算法仍然相同.因此,为了让我们比较不同的算法,以确定一个是否更好,我们使用Big O表示法.

什么是大O符号的简单英语解释:

并非所有算法都在相同的时间内运行,并且可以根据输入中的项目数量而变化,我们称之为n.基于此,我们考虑更糟糕的案例分析,或者随着n变得越来越大,运行时的上限.我们必须知道n是什么,因为许多Big O符号都引用了它.


William Payn.. 32

测量软件程序的速度非常困难,当我们尝试时,答案可能非常复杂,并且充满异常和特殊情况.这是一个大问题,因为当我们想要将两个不同的程序相互比较以找出哪个是"最快的"时,所有这些异常和特殊情况都会分散注意力并且无益.

由于所有这些无益的复杂性,人们试图用尽可能最小和最不复杂(数学)的表达来描述软件程序的速度.这些表达式是非常粗略的近似值:虽然运气不错,但它们将捕获一个软件是快还是慢的"本质".

因为它们是近似值,所以我们在表达式中使用字母"O"(Big Oh)作为一种惯例,向读者发出信号,表明我们正在粗略地过度简化.(并确保没有人错误地认为表达方式是否准确).

如果您将"哦"视为"按顺序"或"近似",则不会出错.(我认为Big-Oh的选择可能是幽默的尝试).

这些"Big-Oh"表达式尝试做的唯一事情就是描述软件在增加软件必须处理的数据量时减慢了多少.如果我们将需要处理的数据量增加一倍,那么软件需要两倍的时间才能完成它的工作吗?十倍的时间?在实践中,您将遇到的数量非常有限的大喔表达式需要担心:

好处:

  • O(1) 常量:无论输入多大,程序都会运行相同的时间.
  • O(log n) 对数:即使输入大小大幅增加,程序运行时也只会缓慢增加.

坏事:

  • O(n) 线性:程序运行时间与输入的大小成比例增加.
  • O(n^k) 多项式: - 随着输入大小的增加,处理时间越来越快 - 作为多项式函数.

......丑陋的:

  • O(k^n) 指数即使问题的大小适度增加,程序运行时也会非常快速地增加 - 使用指数算法处理小数据集是切实可行的.
  • O(n!) 因子程序运行时间将比你能够等待除了最小和最琐碎的数据集之外的任何东西都要长.

  • 我也听说过Linearithmic这个术语 - "O(n log n)"这个词会被认为是好的. (4认同)

Ajeet Ganga.. 28

好的,我的2cents.

Big-O,是程序消耗的资源增加率,wrt problem-instance-size

资源:可能是总CPU时间,可能是最大RAM空间.默认情况下指CPU时间.

说问题是"找到总和",

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instance = {5,10,15} ==> problem-instance-size = 3,iterations-in-loop = 3

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5次迭代循环= 5

对于大小为"n"的输入,程序以阵列中的"n"次迭代的速度增长.因此Big-O是N,表示为O(n)

说问题是"找到组合",

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instance = {5,10,15} ==> problem-instance-size = 3,total-iterations = 3*3 = 9

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5,total-iterations = 5*5 = 25

对于大小为"n"的输入,程序以阵列中"n*n"次迭代的速度增长.因此Big-O是N 2,表示为O(n 2)

  • `while(size - > 0)`我希望[this](http://stackoverflow.com/questions/1642028/what-is-the-name-of-this-operator)不会再问. (3认同)

AlienOnEarth.. 28

一个简单明了的答案可以是:

Big O表示该算法的最差可能时间/空间.该算法永远不会占用超过该限制的更多空间/时间.Big O代表极端情况下的时间/空间复杂性.


John C Earls.. 26

Big O表示法是一种根据空间或运行时间来描述算法上限的方法.n是问题中元素的数量(即数组的大小,树中节点的数量等).我们有兴趣描述n变大的运行时间.

当我们说某些算法是O(f(n))时,我们说该算法的运行时间(或所需的空间)总是低于某些常数f(n).

要说二进制搜索的运行时间为O(logn),就是说存在一些常数c,你可以将log(n)乘以它常常大于二进制搜索的运行时间.在这种情况下,您将始终有一些log(n)比较的常数因子.

换句话说,当g(n)是算法的运行时间时,当n> k时g(n)= O(f(n))当g(n)= = c*f(n)时,我们说g(n)= O(f(n)) c和k是一些常数.


Joseph Myers.. 24

" Big O的简单英语解释是什么?尽可能少的正式定义和简单的数学. "

这样一个非常简单和简短的问题似乎至少应该得到一个同样简短的答案,就像学生在课外辅导时一样.

Big O表示法仅仅根据输入数据量**来说明算法可以在其中运行多少时间**.

(*在一个美好的,无单位的时间感!)
(**这是重要的,因为人们总是想要更多,无论他们今天或明天生活)

那么,如果它的作用是什么,Big O符号有多么美妙?

  • 实际上,Big O分析是如此有用和重要,因为Big O将重点放在算法本身的复杂性上,并完全忽略任何仅仅是比例常量的东西 - 如JavaScript引擎,CPU的速度,Internet连接和所有那些迅速变得像模型T一样过时的过时的东西.Big O专注于表现,只对生活在现在或未来的人们同样重要.

  • Big O符号也直接关注计算机编程/工程的最重要原则,这一事实激励所有优秀的程序员不断思考和梦想:实现超越技术前进的结果的唯一方法就是发明更好的技术算法.

  • 被要求在没有数学的情况下解释数学的东西对我来说总是个人的挑战,作为一个真正的博士学位.数学家和老师认为这样的事实际上是可能的.作为一名程序员,我希望没有人会在没有数学的情况下回答这个特殊的问题,这是一个完全不可抗拒的挑战. (5认同)

Khaled.K.. 22

算法示例(Java):

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

算法描述:

  • 该算法逐项搜索列表,查找密钥,

  • 迭代列表中的每个项目,如果它是键,则返回True,

  • 如果循环已完成而未找到该键,则返回False.

Big-O表示法代表复杂性的上限(时间,空间,......)

要找到大时间复杂性:

  • 计算最坏情况需要多少时间(关于输入大小):

  • 最坏情况:列表中不存在密钥.

  • 时间(最坏情况)= 4n + 1

  • 时间:O(4n + 1)= O(n)| 在Big-O中,常数被忽略了

  • O(n)〜线性

还有Big-Omega,它代表了Best-Case的复杂性:

  • 最佳案例:关键是第一项.

  • 时间(最佳情况)= 4

  • 时间:Ω(4)= O(1)~Instant\Constant

  • 你的常数4来自哪里? (2认同)

Alexey.. 18

大O.

当x变为a(例如,a = +∞)时,f(x)= O(g(x))意味着存在函数k,使得:

  1. f(x)= k(x)g(x)

  2. k在a的某个邻域中有界(如果a = +∞,这意味着存在数N和M,使得对于每个x> N,| k(x)| <M).

换句话说,用简单的英语:f(x)= O(g(x)),x→a,意味着在a的邻域中,f分解成g和某个有界函数的乘积.

小o

顺便说一下,这里是为了比较小o的定义.

当x到达a时,f(x)= o(g(x))表示存在函数k,使得:

  1. f(x)= k(x)g(x)

  2. 当x变为a时,k(x)变为0.

例子

  • 当x→0时,sin x = O(x).

  • 当x→+∞时,sin x = O(1)

  • 当x→0时,x 2 + x = O(x),

  • 当x→+∞时,x 2 + x = O(x 2),

  • 当x→+∞时,ln(x)= o(x)= O(x).

注意!带有等号"="的符号使用"假等式":o(g(x))= O(g(x)),但是假(O(g(x))= o(g) (X)).类似地,可以在x→+∞时写"ln(x)= o(x)",但公式​​"o(x)= ln(x)"没有意义.

更多例子

  • 当n→+∞时,O(1)= O(n)= O(n 2)(但不是相反,相等是"假的"),

  • 当n→+∞时,O(n)+ O(n 2)= O(n 2)

  • 当n→+∞时,O(O(n 2))= O(n 2)

  • 当n→+∞时,O(n 2)O(n 3)= O(n 5)


这是维基百科的文章:https://en.wikipedia.org/wiki/Big_O_notation

  • 你说的是"大O"和"小o"而没有解释它们是什么,引入了大量的数学概念,却没有说出它们为什么重要,而维基百科的链接在这种情况下可能对于这类问题来说太明显了. (3认同)
  • 嗨#Alexey,请看一下接受的答案:它很长但是它构造得很好并且格式很好.它以简单的定义开始,不需要数学背景.在这样做的同时,他引入了3个"技术"词,他立即解释(相对,表现,复杂).在深入研究这个领域的同时,这也是一步一步的. (2认同)
  • Big O用于理解算法的渐近行为,原因与它用于理解函数的渐近行为相同(渐近行为是无穷远处的行为).这是一个方便的符号,用于比较复杂函数(算法采用的实际时间或空间)与无穷大附近或其他任何附近的简单函数(任何简单的,通常是幂函数).我只解释了它是什么(给出了定义).如何用大O计算是一个不同的故事,也许我会添加一些例子,因为你感兴趣. (2认同)

Brian.. 18

Big O表示法是一种描述给定任意数量的输入参数的算法运行速度的方法,我们将其称为"n".它在计算机科学中很有用,因为不同的机器以不同的速度运行,并且简单地说算法需要5秒钟并不能告诉你太多,因为当你运行一个带有4.5 Ghz八核处理器的系统时,我可能正在运行一个15岁的800 Mhz系统,无论算法如何,都可能需要更长的时间.因此,我们不是指定算法在时间上运行的速度,而是根据输入参数的数量或"n"来说它运行的速度有多快.通过以这种方式描述算法,我们能够比较算法的速度,而不必考虑计算机本身的速度.


Priidu Neemr.. 11

不确定我是否正在为这个主题做出进一步的贡献,但仍然认为我会分享:我曾经发现这篇博文在Big O上有一些非常有帮助的(虽然非常基本的)解释和示例:

通过例子,这有助于将基本的基本部分放入我的玳瑁般的头骨中,所以我认为这是一个非常下降的10分钟阅读,让你朝着正确的方向前进.


johnwbyrd.. 11

你想知道大O的所有知识吗?我也是.

所以谈到大O,我将使用只有一个节拍的单词.每个单词一个声音.小词很快.你知道这些话,我也一样.我们会用一个声音的单词.他们很小.我相信你会知道我们将使用的所有词语!

现在,让我们和你谈谈工作.大多数时候,我不喜欢工作.你喜欢上班吗?你可能会这样,但我相信我不这样做.

我不喜欢去上班.我不喜欢在工作上花时间.如果我有自己的方式,我只想玩,做有趣的事情.你觉得和我一样吗?

有时,我必须去上班.这很难过,但却是真的.所以,当我在工作时,我有一个规则:我尝试做更少的工作.我尽可能无法工作.然后我去玩!

所以这是一个重大新闻:大O可以帮助我不做工作!我可以玩更多的时间,如果我知道大O.少工作,多玩!这就是大O帮助我做的事情.

现在我有一些工作.我有这个清单:一,二,三,四,五,六.我必须在此列表中添加所有内容.

哇,我讨厌工作.但是哦,我必须这样做.所以我走了.

一加二是三......加三是六......四是......我不知道.我迷路了.我脑子里很难做到这一点.我不太关心这种工作.

所以,我们不要做这项工作.让我和你思考它有多难.我需要做多少工作才能添加六个数字?

好的,我们等着瞧.我必须添加一个和两个,然后将其添加到三个,然后将其添加到四个...总而言之,我计算六个添加.我必须做六个补充来解决这个问题.

这里有大O,告诉我们这个数学有多难.

Big O说:我们必须做六个补充来解决这个问题.一个补充,每个东西从一到六.六小部分工作......每一项工作都是一个补充.

好吧,我现在不会去做它们的工作.但我知道它会有多难.这将是六个补充.

哦不,现在我有更多的工作.啧.谁做这种东西?!

现在他们要我加一到十!我为什么要这么做?我不想添加一到六个.从一到十加......好吧......那会更难!

会有多难?我还需要做多少工作?我需要更多或更少的步骤吗?

好吧,我想我必须做十次补充......一次从一到十.十分超过六分.我必须工作更多,从一到十,而不是一到六!

我现在不想加.我只是想想加入那么多可能有多难.并且,我希望,尽快发挥.

从一到六添加,这是一些工作.但是,你看,从一到十,这是更多的工作吗?

Big O是你的朋友和我的朋友.Big O帮助我们思考我们需要做多少工作,所以我们可以计划.而且,如果我们是大O的朋友,他可以帮助我们选择不那么难的工作!

现在我们必须做新的工作.不好了.我根本不喜欢这件事.

新工作是:将所有内容从一个添加到n.

等待!什么是n?我错过了吗?如果你不告诉我什么是n,我如何从一个添加到n?

好吧,我不知道n是什么.我没有被告知.是吗?没有?那好吧.所以我们不能做这项工作.呼.

但是,虽然我们现在不会做这项工作,但如果我们知道n,我们可以猜到它会有多难.我们必须加起来,对吗?当然!

现在来了大O,他会告诉我们这项工作有多难.他说:将所有东西从一个添加到N,一个接一个,是O(n).要添加所有这些东西,[我知道我必须添加n次.] [1]那是大O!他告诉我们做某种工作有多难.

对我而言,我认为大O就像一个又大又慢的老板.他在工作上思考,但他没有这样做.他可能会说,"这项工作很快." 或者,他可能会说,"这项工作是如此缓慢而艰难!" 但他不做这项工作.他只是看着作品,然后他告诉我们需要花多少时间.

我非常关心大O.为什么?我不喜欢上班!没有人喜欢工作.这就是为什么我们都喜欢大O!他告诉我们我们的工作速度有多快.他帮助我们思考如何努力工作.

哦,哦,更多的工作.现在,我们不做这项工作.但是,让我们一步一步地制定计划.

他们给了我们一张十张牌.他们都混在一起:七,四,二,六......根本不直.而现在......我们的工作就是对它们进行排序.

Ergh.这听起来像是很多工作!

我们怎样才能对这副牌进行排序 我有个计划.

我将从头到尾看看每对卡片,一副一对地穿过甲板.如果一对中的第一张卡很大而且该对中的下一张卡很小,我会换掉它们.否则,我会去下一对,依此类推......很快,甲板就完成了.

当甲板完成后,我问:我是否在那张通行证中换了牌?如果是这样,我必须再次从顶部完成所有操作.

在某些时候,在某个时候,将没有互换,我们的甲板将完成.这么多工作!

那么,用这些规则对卡片进行分类会有多少工作呢?

我有十张牌.而且,大部分时间 - 也就是说,如果我没有很多运气 - 我必须通过整个牌组十次,每次通过牌组最多十次换卡.

大O,救救我!

Big O进来并说:对于一副n张牌,这样排序将以O(N平方)时间完成.

为什么他说n平方?

嗯,你知道n平方是n倍n.现在,我得到它:n卡检查,直到可能是通过甲板n次.这是两个循环,每个循环有n个步骤.这是很多工作要做的事情.很多工作,当然!

现在,当大O说它将需要O(n平方)工作时,他并不意味着n平方加在鼻子上.在某些情况下,它可能会少一些.但在最糟糕的情况下,它将接近n平方的工作量来对甲板进行分类.

现在,大O是我们的朋友.

Big O指出了这一点:随着n变得越来越大,当我们对卡片进行分类时,这项工作比旧的只是添加这些工作要困难得多.我们怎么知道呢?

好吧,如果n变得很大,我们不关心我们可能添加到n或n平方.

对于大n,n平方比n大.

Big O告诉我们,对东西进行排序比添加东西更难.对于大n,O(n平方)大于O(n).这意味着:如果n变得很大,那么对n个混合的东西进行排序必须花费更多的时间,而不是只添加n个混合的东西.

Big O并没有为我们解决问题.Big O告诉我们工作有多难.

我有一副纸牌.我对它们进行了排序.你帮忙了 谢谢.

是否有更快的方式对卡片进行排序?大O可以帮助我们吗?

是的,有一种更快的方式!这需要一些时间来学习,但它的工作原理......它的工作速度非常快.您也可以尝试,但每走一步都要花时间,不要失去你的位置.

在这种对甲板进行排序的新方法中,我们不像前一段时间那样检查成对卡片.以下是您对此套牌进行排序的新规则:

一:我现在在甲板上选择一张牌.如果你愿意,你可以选择一个.(我们第一次这样做,"我们现在工作的甲板部分"当然是整个甲板.)

二:我在你选择的那张牌上张开了牌组.这是什么意思; 我该如何施展?好吧,我一个接一个地从开始卡开始,我寻找一张比插卡更高的卡片.

三:我从终端卡开始,我找到一张比张卡更低的卡.

一旦我找到这两张卡,我就换掉它们,继续寻找更多的牌来交换.也就是说,我回到第二步,然后在你选择的卡上张开更多.

在某些时候,这个循环(从两到三)将结束.当此搜索的两半在展开卡处相遇时结束.然后,我们刚刚用你在第一步中选择的牌张开了牌组.现在,开始附近的所有卡都比低位卡更低; 并且靠近末端的卡比展开的卡更高.酷戏!

四个(这是有趣的部分):我现在有两个小甲板,一个比展开卡低一个,还有一个高.现在我走到每个小甲板上的第一步!也就是说,我从第一个小甲板上的第一步开始,当这项工作完成后,我从下一个小甲板上的第一步开始.

我将甲板分成几部分,然后对每个部分进行分类,更小,更小,有时候我没有更多的工作要做.现在这可能看起来很慢,包含所有规则.但请相信我,它根本不慢.这比排序第一种方式要少得多!

这叫什么?它被称为快速排序!那种叫做CAR Hoare的人称之为" 快速排序".现在,Quick Sort一直被使用!

快速排序打破了小型的大型甲板.也就是说,它打破了小任务中的大任务.

嗯.我认为可能存在规则.要使大任务变小,请将其分解.

这种很快.多快?Big O告诉我们:在这种情况下,这种类型需要完成O(n log n)工作.

它比第一种更快还是更快?大O,请帮忙!

第一种是O(n平方).但快速排序是O(n log n).你知道n log n小于n平方,对于大n,对吗?好吧,这就是我们知道Quick Sort快速的方式!

如果你必须排序甲板,最好的方法是什么?好吧,你可以做你想做的事,但我会选择快速排序.

为什么选择快速排序?当然,我不喜欢工作!我希望我能尽快完成工作.

我如何知道Quick Sort工作量少?我知道O(n log n)小于O(n平方).O更小,因此Quick Sort工作量更少!

现在你认识我的朋友Big O.他帮助我们减少工作量.如果你知道大O,你也可以做更少的工作!

你跟我学到了这一切!你太聪明了!非常感谢!

现在工作完成了,让我们去吧!


[1]:有一种方法可以欺骗并将所有东西从一个添加到n,一次全部.一个名叫高斯的小孩在八岁的时候发现了这个.我不是那么聪明,所以不要问我是怎么做到的.


Kjartan.. 9

假设我们正在谈论算法A,它应该对大小为n的数据集做一些事情.

然后O( <some expression X involving n> )用简单的英语表示:

如果您在执行A时不幸,则可能需要完成X(n)操作.

碰巧,有一定的函数(把它们当作实现X(N) ),往往会经常发生.这些是众所周知的,并且容易地进行比较(例如:1,Log N,N,N^2,N!,等.)

通过谈论比较时,这些一个和其它算法,很容易根据他们的操作次数排名算法可以(最坏情况)需要完成.

一般来说,我们的目标是找到或构造算法A,使其具有X(n)尽可能低的数量的函数.


nitin kumar.. 9

我有更简单的方法来理解时间复杂度,他最常用的计算时间复杂度的指标是Big O表示法.这消除了所有常数因子,因此当N接近无穷大时,可以相对于N估计运行时间.一般来说,你可以这样想:

statement;

是不变的.声明的运行时间不会相对于N发生变化

for ( i = 0; i < N; i++ )
  statement;

是线性的.循环的运行时间与N成正比.当N加倍时,运行时间也是如此.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

是二次的.两个循环的运行时间与N的平方成比例.当N加倍时,运行时间增加N*N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

是对数的.算法的运行时间与N可以除以2的次数成比例.这是因为算法将工作区域与每次迭代分成两半.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

是N*log(N).运行时间由对数的N个循环(迭代或递归)组成,因此算法是线性和对数的组合.

一般来说,对一个维度中的每个项目执行某些操作是线性的,对二维中的每个项目执行某些操作是二次的,将工作区域分成两半是对数的.还有其他Big O指标,如立方,指数和平方根,但它们并不常见.Big O表示法被描述为O(),其中是度量.快速排序算法将被描述为O(N*log(N)).

注意:这些都没有考虑最佳,平均和最坏情况的措施.每个都有自己的Big O表示法.另请注意,这是一个非常简单的解释.Big O是最常见的,但它也显示得更复杂.还有其他符号,如大欧米茄,小o和大theta.您可能不会在算法分析课程之外遇到它们.


raaz.. 9

说你订购哈利波特:从亚马逊完成8-Film Collection [Blu-ray]并同时在线下载相同的电影收藏.您想测试哪种方法更快.交付大约需要一天到达,下载大约提前30分钟完成.大!所以这是一场紧张的比赛.

如果我订购了诸如指环王,暮光之城,黑暗骑士三部曲等几部蓝光电影并同时在线下载所有电影怎么办?这一次,交付仍需要一天时间才能完成,但在线下载需要3天才能完成.对于在线购物,购买的商品数量(输入)不会影响交货时间.输出是不变的.我们称之为O(1).

对于在线下载,下载时间与电影文件大小(输入)成正比.我们称之为O(n).

从实验中我们知道,网上购物比在线下载更好.了解大O表示法非常重要,因为它可以帮助您分析算法的可扩展性效率.

注意: Big O表示法表示算法的最坏情况.假设O(1)O(n)是上述示例的最坏情况.

参考:http://carlcheo.com/compsci


小智.. 8

如果你头脑中有一个合适的无限概念,那么有一个非常简短的描述:

Big O表示法告诉您解决无限大问题的成本.

而且

常数因素可以忽略不计

如果您升级到可以以两倍的速度运行算法的计算机,那么大O表示法将不会注意到这一点.恒定因子的改进太小,甚至在大O符号的工作范围内都没有被注意到.请注意,这是大O符号设计的有意部分.

但是,虽然可以检测到比常数因子"更大"的任何东西.

当有兴趣进行大小"足够大"的计算时,那么大O符号大约是解决问题的成本.


如果上面没有意义,那么你的头脑中没有兼容的无限直觉概念,你应该忽视以上所有内容; 我所知道的唯一方法就是让这些想法严谨,或者解释它们,如果它们还没有直观的用处,那就是首先教你大概念或类似的东西.(虽然,一旦你很好地理解了未来的大O符号,重新考虑这些想法可能是值得的)


Algebra.. 7

什么是"大O"符号的简单英语解释?

很快注意:

"大O"中的O表示为"顺序"(或者恰恰是"顺序"),
因此您可以从字面上理解它用于命令比较它们的东西.

  • "大O"做两件事:

    1. 估计计算机应用于完成任务的方法的步数.
    2. 促进过程与他人比较,以确定它是否好?
    3. "大O"通过标准化实现了上述两个目标Notations.
  • 有七种最常用的符号

    1. O(1),意味着你的计算机完成了1一步完成的任务,它非常好,订购了No.1
    2. O(logN),表示您的计算机完成了一个带有logN步骤的任务,它是好的,有序的No.2
    3. O(N),完成任务N步骤,公平,第3号命令
    4. O(NlogN),用O(NlogN)步骤结束任务,不好,订单号4
    5. O(N ^ 2),用N^2步骤完成一项任务,这很糟糕,订单号为5
    6. O(2 ^ N),用2^N步骤完成任务,这太可怕了,订单No.6
    7. O(N!),通过N!步骤完成任务,这很糟糕,订单No.7

在此输入图像描述

假设你得到了符号O(N^2),不仅你清楚该方法需要N*N步骤来完成一项任务,你也会发现它的O(NlogN)排名并不好.

请注意在行尾的订单,只是为了更好地理解.如果考虑所有可能性,则有超过7种符号.

在CS中,完成任务的一组步骤称为算法.
在术语中,Big O表示法用于描述算法的性能或复杂性.

此外,Big O建立最坏情况或测量上限步骤.
您可以参考Big-Ω(Big-Omega)获得最佳案例.

Big-Ω(Big-Omega)表示法(文章)| 可汗学院

  • 摘要
    "Big O"描述了算法的性能并对其进行了评估.

    或者正式解决它,"Big O"对算法进行分类并使比较过程标准化.


developer747.. 6

最简单的方式(简单的英文)

我们试图看看输入参数的数量如何影响算法的运行时间.如果应用程序的运行时间与输入参数的数量成正比,则称其为n的Big O.

上述陈述是一个良好的开端,但并非完全正确.

更准确的解释(数学)

假设

n =输入参数的数量

T(n)=表示作为n的函数的算法运行时间的实际函数

c =常数

f(n)=表示作为n的函数的算法运行时间的近似函数

然后就Big O而言,只要下面的条件为真,则近似f(n)被认为是足够好的.

lim     T(n) ? c×f(n)
n??

该方程被读作As n接近无穷大,n的T小于或等于n的c乘以f.

在大O表示法中,这写为

T(n)?O(n)

这是因为n的T在n的大O中.

回到英文

根据上面的数学定义,如果你说你的算法是n的大O,那就意味着它是n(输入参数的数量)或更快的函数.如果你的算法是n的大O,那么它也自动是n平方的大O.

N的大O意味着我的算法运行至少与此一样快.您无法查看算法的Big O表示法,并说它很慢.你只能说它快.

检查对来自加州大学伯克利分校的大O的视频教程.这实际上是一个简单的概念.如果你听到Shewchuck教授(又名神级教师)解释它,你会说"哦,就是这样!".


SIW.. 5

我发现了有关大O表示法的很好的解释,特别是对于一个数学不多的人。

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Big O符号在计算机科学中用于描述算法的性能或复杂性。Big O特别描述了最坏的情况,可用于描述算法所需的执行时间或使用的空间(例如,内存或磁盘中的空间)。

读过Programming Pearls或任何其他计算机科学书籍且没有数学基础的任何人,在到达提及O(N log N)或其他看似疯狂的语法的章节时都会碰壁。希望本文能帮助您了解Big O和对数的基础。

作为程序员的第一位,然后是数学家的第二位(或者也许是第三位或第四位),我发现透彻理解Big O的最佳方法是编写一些示例代码。因此,以下是一些常见的增长顺序以及可能的描述和示例。

O(1)

O(1)描述了一种算法,无论输入数据集的大小如何,该算法将始终在同一时间(或空间)执行。

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

上)

O(N)描述了一种算法,其性能将线性增长,并且与输入数据集的大小成正比。下面的示例还演示了Big O如何支持最坏情况下的性能情况;在for循环的任何迭代过程中都可以找到匹配的字符串,并且该函数将尽早返回,但是Big O表示法将始终假定算法将执行最大迭代次数的上限。

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O(N 2

O(N 2)表示一种算法,其性能与输入数据集的大小的平方成正比。这在涉及对数据集进行嵌套迭代的算法中很常见。更深层的嵌套迭代将导致O(N 3),O(N 4)等。

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O(2 N

O(2 N)表示一种算法,每增加一个输入数据集,其增长量就会增加一倍。O(2 N)函数的增长曲线是指数的-从非常浅的位置开始,然后在气象上上升。O(2 N)函数的一个示例是斐波那契数的递归计算:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

对数

对数解释起来有些棘手,因此我将使用一个常见示例:

二进制搜索是一种用于搜索排序的数据集的技术。它通过选择数据集的中间元素(实际上是中位数)进行工作,并将其与目标值进行比较。如果值匹配,它将返回成功。如果目标值高于探针元素的值,它将获取数据集的上半部分并对其执行相同的操作。同样,如果目标值低于探针元素的值,它将对下半部分执行操作。在每次迭代之前,它将继续将数据集减半,直到找到该值或无法再拆分数据集为止。

这种算法称为O(log N)。二元搜索示例中描述的数据集的迭代减半产生一条增长曲线,该曲线在开始时达到峰值,然后随着数据集大小的增加而逐渐变平,例如,包含10个项目的输入数据集需要一秒钟才能完成,一个数据集包含100个项目的数据将花费2秒,而包含1000个项目的数据集将花费3秒。将输入数据集的大小加倍对其增长几乎没有影响,因为在算法的单次迭代之后,数据集将减半,因此与输入数据集大小的一半相等。这使得诸如二进制搜索之类的算法在处理大型数据集时极为有效。


归档时间:

查看次数:

673615 次

最近记录:

11 月,1 周 前