我更喜欢尽可能少的正式定义和简单的数学。
当前回答
大 O 描述一类功能。
它描述了大输入值的快速功能的增长方式。
对于一个特定的函数f,O(f)分解了所有函数g(n),您可以找到一个n0和一个恒定的c,以便与n>=n0的g(n)的所有值都低于或相当于c*f(n)。
在较少的数学词语中,O(f)是一组函数,即所有函数,从某些值 n0 向前,增长缓慢或像 f 一样快。
如果 f(n) = n 那么
g(n) = 3n 是 O(f) 。 因为恒定的因素不重要 h(n) = n+1000 是 O(f) 因为它可能比所有值小于 1000 但对于大 O 只有大输入物质。
然而,i(n) = n^2不在O(f)中,因为一个四方函数比一个线性函数增长得更快。
其他回答
我最喜欢的英语词来描述这个概念是你为一个任务付出的代价,因为它越来越大。
既然这些常态在长期内并不重要,这种语言允许我们讨论超越我们正在运行的基础设施之外的任务,所以工厂可以到任何地方,工人可以到任何地方 - 它都是可怕的,但是工厂的大小和工人的数量是我们在长期内可以改变的事情,因为您的输入和输出增长。
由于时间和空间是经济量(即它们是有限的)在这里,它们都可以用这个语言表达。
技术笔记: 时间复杂性的一些例子 - O(n) 一般意味着如果一个问题是“n”的大小,我至少必须看到一切。 O(log n) 一般意味着我减半问题的大小,检查并重复,直到任务完成。
一个简单的答案可以是:
大 O 代表了这个算法可能最糟糕的时间/空间. 算法永远不会超过这个限制的空间/时间. 大 O 代表了极端情况下的时间/空间复杂性。
要做一个字面类似,你不关心跑者能跑到100米,甚至跑到5K的速度,你更关心马拉松人,最好是超级马拉松人(除此之外,跑的类似性会崩溃,你必须转向“长跑”的形象意义)。
关于所有这些数学逻辑和多元化是什么? 显然算法与这些数学术语内在相关。 如果你测量区块上的所有孩子的高度,它会花费你那么多时间,因为有孩子。 这是内在相关的 n^1 或只是 n 的概念,在那里 n 是区块上的孩子数量。
我希望我已经解释说,大O的评级仅仅是关于长期,数学与计算方式有内在的联系,数学术语和其他简化与长期有相当常见的联系。
我找到了一个非常好的解释关于大O评分,特别是对于一个没有太多的数学的人。
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
在计算机科学中使用Big O评分来描述算法的性能或复杂性。Big O具体描述了最糟糕的情况,并且可以用来描述一个算法所需的执行时间或使用的空间(例如在内存或磁盘上)。
上述说法是一个很好的开始,但不是完全真实的。
更准确的解释(数学)
n = 输入参数数
T(n) = 表达算法运行时间的实际函数为 n 的函数
c = 常态
f(n)= 表达算法运行时间为 n 的函数的约定函数
接下来,在大O方面,接近f(n)被认为足够好,只要下面的条件是真实的。
lim T(n) ≤ c×f(n)
n→∞
方程式是如 n 接近无限, T 的 n 是少于或等于 c 次 f 的 n。
T(n)∈O(n)
回到英语
基于上面的数学定义,如果你说你的算法是一个大O的n,这意味着它是一个函数的n(输入参数的数量)或更快。
Big O of n 意味着我的算法运行至少如此之快. 你不能看你的算法的 Big O 评分,并说它很慢. 你只能说它很快。