我最喜欢的英语词来描述这个概念是你为一个任务付出的代价,因为它越来越大。

既然这些常态在长期内并不重要,这种语言允许我们讨论超越我们正在运行的基础设施之外的任务,所以工厂可以到任何地方,工人可以到任何地方 - 它都是可怕的,但是工厂的大小和工人的数量是我们在长期内可以改变的事情,因为您的输入和输出增长。

由于时间和空间是经济量(即它们是有限的)在这里,它们都可以用这个语言表达。

技术笔记: 时间复杂性的一些例子 - O(n) 一般意味着如果一个问题是“n”的大小,我至少必须看到一切。 O(log n) 一般意味着我减半问题的大小,检查并重复,直到任务完成。

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

大 O 评级告诉你解决一个无限大的问题的成本。

此外,

常见因素不可忽视

如果你升级到一个可以运行你的算法的计算机两倍的速度,大 O 评级不会注意到这一点. 持续的因素改进太小,甚至在大 O 评级工作的规模中也会注意到。

然而,任何“大”比恒定的因素都可以被检测到。

---

如果上面的没有意义,那么你头脑中没有相容的直观的无限观念,你可能应该忽略上面的所有观念;我唯一知道如何使这些观念严格,或者解释它们是否已经是直观的有用,就是先教你大O评分或类似的东西。

大 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 在平式英语是如<=(少于或等)。当我们说为两个函数f 和 g,f = O(g) 它意味着f <= g。

但是,这并不意味着任何 n f(n) <= g(n) 事实上,它意味着 f 是增长方面低于或等于 g 的,这意味着在一个点 f(n) <= c*g(n) 之后,如果 c 是恒定的,然后一个点意味着所有 n >= n0 在那里 n0 是另一个恒定的。

Big-O 是由程序所消耗的资源增加率,即问题例大小。

资源:可能是CPU时间,可能是最大 RAM 空间。

说问题是“找到金额”,

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 iterations-in-loop = 5

说问题是“找到组合”,

    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是N2以O(n2)表达。

---

最简单的定义我可以给大 Oh 评分是:

智者可能已经意识到,我们可以表达操作的数量如:n2 + 2n. 但是,正如你从我们的例子中看到的两个数字的百万数字左右,第二个术语(2n)变得毫无意义(计算为0.0002%的总操作在这个阶段)。

因此,要找到一个名字给了电话号码(逆转搜索):

最佳案例:O(1);预期案例:O(n)(为500,000);最糟糕案例:O(n)(为1000,000)。

旅行卖家

听起来很简单吗?再想一想。

聚合物时间

另一个我想快速提到的是,任何具有O(na)复杂性的算法都说具有多元复杂性,或者在多元时间可溶解。