什么是“大O”笔记的明确英语解释?

我想强调“大O”评分的驱动动力是一件事,当算法的输入尺寸变得太大时,算法的某些部分(即恒数、比例、术语)的方程式描述算法的尺寸变得如此无意义,以至于我们忽略它们。

因此,如果输入尺寸不太大,那么“大O”评分(上限)的想法将毫无意义。

Lets say you want to quantify the performance of the following algorithm

int sumArray (int[] nums){
    int sum=0;   // here we've 1 operation
    for(int i=0; i < nums.length;i++){   // we've n times
        sum += nums[i]; // taking initialization and assignments, 3 ops
    }
    return sum;
}

在上面的算法中,让我们说你发现T(n)如下(时间复杂性):

T(n) = 3*n + 2

n= 1,000,000   -> T(1,000,000) = 3,000,002
n=1,000,000,000  -> T(1,000,000,000) = 3,000,000,002
n=10,000,000,000  -> T(10,000,000,000) = 30,000,000,002

将此类输入给另一个函数 F(n) = n

n= 1,000,000   -> F(1,000,000) = 1,000,000 
n=1,000,000,000  -> F(1,000,000,000) = 1,000,000,000
n=10,000,000,000  -> F(10,000,000,000) = 10,000,000,000

因为你可以看到输入尺寸变得太大,T(n)大约相当于或接近F(n),所以连续2和比例3变得太不重要,现在大O“评级的想法来了,

O(T(n)) = F(n)
O(T(n)) = n

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)表达。

O(n2):被称为四方复杂性

1 件: 1 件 10 件: 100 件 100 件: 10,000 件

请注意,物品的数量增加了10个因素,但时间增加了102个因素。

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

1 件: 1 操作 10 件: 10 操作 100 件: 100 操作

这一次,元素的数量增加了10个因素,所以时间n=10,所以O(n)的规模因素是10。

O(1):被称为恒久复杂性

1 件: 1 操作 10 件: 2 操作 100 件: 3 操作 1000 件: 4 操作 10,000 件: 5 操作

他们降低了数学,所以它可能不是准确的n2或他们说它是什么,但这将是规模的支配因素。

大 O 描述了一个功能的增长行为上限,例如一个程序的运行时间,当输入变得大。

例子:

O(n):如果我翻倍输入大小,运行时间将翻倍O(n2):如果输入大小将翻倍运行时间四倍O(log n):如果输入大小翻倍运行时间将增加一倍O(2n):如果输入大小增加一倍,运行时间将翻倍

输入尺寸通常是比特所需的空间来代表输入。

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

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

此外,

常见因素不可忽视

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

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

---

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

定义 : 大 O 评级是指如果数据输入增加,算法性能将如何表现的评级。

当我们谈论算法时,有3个重要柱子 算法输入、输出和处理 大 O 是象征性的评分,如果数据输入增加到什么速度,算法处理的性能将有所不同。

例如,请参见下面的函数“函数1”,该函数收集并在第一个记录中进行处理,现在该函数的性能将是相同的,无论您放置1000、10万或100000记录。

void Function1(List<string> data)
{
string str = data[0];
}

void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

因此,通过查看Big O评级,我们分类算法的好和坏区域。

此分類上一篇

https://www.youtube.com/watch?v=k6kxtzICG_g