algorithm -大O,你如何计算/近似它?

Translate

大多数拥有CS学位的人肯定会知道大O代表。它有助于我们评估算法的效率(效率)以及您是否知道算法的效率。您要解决的问题属于哪一类您可以弄清楚是否仍有可能挤出那一点点额外的性能。1

但我很好奇,怎么办计算或近似算法的复杂度?

1 但正如他们所说,不要过度使用它,过早的优化是万恶之源,并且没有正当理由的优化也应使用该名称。

This question and all comments follow the "Attribution Required."

所有的回答

vz0
Translate

我会尽力在这里简单地解释它,但要注意,这个话题需要我的学生花几个月的时间才能最终掌握。您可以在第2章中找到更多信息。Java中的数据结构和算法书。


没有机械程序可以用来获取BigOh。

作为“食谱”,获得大哦从一段代码中,您首先需要意识到,您正在创建一个数学公式来计算给定大小的输入后执行多少计算步骤。

目的很简单:从理论的角度比较算法,而无需执行代码。步骤数越少,算法越快。

例如,假设您有这段代码:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

此函数返回数组所有元素的总和,我们想创建一个公式来计算计算复杂度该功能的:

Number_Of_Steps = f(N)

所以我们有f(N),用于计算计算步数的函数。函数的输入是要处理的结构的大小。这意味着将调用该函数,例如:

Number_Of_Steps = f(data.length)

参数N需要data.length值。现在我们需要函数的实际定义f()。这是从源代码完成的,其中每个有趣的行从1到4编号。

有许多方法可以计算BigOh。从现在开始,我们将假设不依赖于输入数据大小的每个句子都采用一个常数C数量计算步骤。

我们将添加函数的各个步骤,并且本地变量声明和return语句都不依赖于函数的大小。data数组。

这意味着第1行和第4行每个都执行C步,并且函数有点像这样:

f(N) = C + ??? + C

下一部分是定义for声明。请记住,我们是在计算计算步骤的数量,这意味着for语句被执行N次。这与添加相同C, N时间:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

没有机械规则来计算身体的多少次for在执行之后,您需要通过查看代码的作用来对其进行计数。为了简化计算,我们忽略了变量的初始化,条件和增量部分。for声明。

要获得实际的BigOh,我们需要渐近分析功能的大致是这样完成的:

  1. 带走所有常数C.
  2. f()得到多项式在其standard form.
  3. 除以多项式的项,然后按增长率对其进行排序。
  4. 保持增长的时候N方法infinity.

我们的f()有两个术语:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

带走所有C常量和冗余部分:

f(N) = 1 + N ^ 1

因为最后一个学期是当f()接近无穷大(想一想极限),这是BigOh参数,sum()函数的BigOh为:

O(N)

有一些技巧可以解决一些棘手的问题:使用总结随时你可以。

例如,可以使用求和轻松地解决此代码:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

您需要问的第一件事是执行的顺序foo()。虽然通常是O(1),您需要向教授询问。O(1)表示(几乎,大部分)常量C,与大小无关N.

for关于第一句的陈述很棘手。当索引结束于2 * N,增量是2。这意味着第一个for仅执行N步骤,我们需要将计数除以二。

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

句子编号更加棘手,因为它取决于i。看一下:索引i取值:0、2、4、6、8,...,2 * N,第二个for被执行:第一个N倍,第二个N-2,第三个N-4 ...直到N / 2阶段,第二个for永远不会被执行。

在公式上,这意味着:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

再次,我们在数步数。并且根据定义,每次求和应始终始于一个,并以大于或等于1的数字结束。

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(我们假设foo()O(1)并采取C脚步。)

我们这里有一个问题:何时i取值N / 2 + 1向上,内部求和结尾为负数!那是不可能的,也是错误的。我们需要将求和一分为二,这是关键时刻i需要N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

自关键时刻i > N / 2,内在for不会被执行,我们假设其主体上的C执行复杂度恒定。

现在,可以使用一些标识规则来简化求和:

  1. 求和(w从1到N)(C)= N * C
  2. 求和(w从1到N)(A(+/-)B)=求和(w从1到N)(A)(+/-)求和(w从1到N)(B)
  3. 求和(w从1到N)(w * C)= C *求和(w从1到N)(w)(C是一个常数,独立于w)
  4. 求和(w从1到N)(w)=(N *(N + 1))/ 2

应用一些代数:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

BigOh是:

O(N²)
来源
Translate

大O给出算法时间复杂度的上限。它通常与处理数据集(列表)结合使用,但可以在其他地方使用。

有关如何在C代码中使用它的一些示例。

假设我们有n个元素的数组

int array[n];

如果我们想访问数组的第一个元素,则为O(1),因为数组的大小无关紧要,获取第一个元素总是需要相同的恒定时间。

x = array[0];

如果我们想在列表中找到一个数字:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

这将是O(n),因为至多我们将不得不浏览整个列表以找到我们的数字。尽管Big-O仍然是O(n),尽管我们可能会第一次尝试找到我们的数字并循环运行一次,因为Big-O描述了算法的上限(omega代表下限,theta代表紧密边界) 。

当我们进入嵌套循环时:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

这是O(n ^ 2),因为对于外循环(O(n))的每次通过,我们都必须再次遍历整个列表,因此n的乘积将n平方。

这勉强可以触及表面,但是当您要分析更复杂的算法时,涉及证明的复杂数学就会发挥作用。希望这至少使您熟悉基础知识。

来源
Translate

虽然知道如何计算出解决特定问题的时间是很有用的,但了解一些一般情况对于帮助您在算法中做出决策可能会大有帮助。

以下是一些最常见的案例,它们是从http://zh.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1)-确定数字是偶数还是奇数;使用恒定大小的查找表或哈希表

O(logn)-使用二进制搜索在排序数组中查找项目

O(n)-在未排序的列表中查找项目;加两个n位数字

2)-用一个简单的算法将两个n位数字相乘;加两个n×n矩阵;气泡排序或插入排序

3)-通过简单算法将两个n×n矩阵相乘

n)-使用动态编程找到旅行商问题的(精确)解决方案;使用蛮力确定两个逻辑语句是否等效

O(n!)-通过蛮力搜索解决旅行商问题

n)-通常用于代替O(n!)来得出渐近复杂度的更简单公式

来源
Translate

小提醒:big O表示法是用来表示渐近的复杂性(也就是说,当问题的规模扩大到无穷大时),它隐藏了一个常数。

这意味着在O(n)中的算法和O(n)中的算法之间2),最快的方法并不总是第一个(尽管总是存在n的值,使得对于大小大于n的问题,第一个算法是最快的)。

注意,隐藏常量在很大程度上取决于实现!

另外,在某些情况下,运行时不是确定性函数尺寸输入的n。以使用快速排序的排序为例:对n个元素的数组进行排序所需的时间不是常数,而是取决于数组的起始配置。

时间复杂度不同:

  • 最坏的情况(通常最简单,尽管并不总是很有意义)
  • 一般情况(通常很难弄清楚...)

  • ...

一个很好的介绍是算法分析导论由R. Sedgewick和P. Flajolet撰写。

正如你所说,premature optimisation is the root of all evil和(如果可能)剖析在优化代码时,应该始终使用它。它甚至可以帮助您确定算法的复杂性。

来源
Translate

在这里看到答案,我认为我们可以得出结论,我们大多数人确实确实通过看着并使用常识而不是用例如主法正如我们在大学时所想。话虽如此,我必须补充一点,就是即使教授也鼓励我们(后来)认为关于它,而不只是计算它。

我也想补充一下递归函数:

假设我们有一个类似(方案代码):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

递归计算给定数字的阶乘。

第一步是尝试确定以下产品的性能特征:仅功能的主体在这种情况下,体内没有什么特别的事情,只是一个乘法(或返回值1)。

所以身体的表现为:O(1)(不变)。

接下来,尝试确定递归调用数。在这种情况下,我们有n-1个递归调用。

所以递归调用的性能为:O(n-1)(顺序为n,因为我们丢弃了无关紧要的部分)。

然后将这两个放在一起,就可以得到整个递归函数的性能:

1 *(n-1)= O(n)


彼得, 回答您提出的问题;我在这里描述的方法实际上可以很好地解决这个问题。但是请记住,这仍然是近似而不是完整的数学正确答案。这里描述的方法也是我们在大学里教过的方法之一,如果我没记错的话,它用于比本例中使用的阶乘更高级的算法。
当然,这完全取决于您可以估计函数主体的运行时间和递归调用的数量,但是其他方法也是如此。

来源
Translate

如果您的成本是多项式,则只需保留最高阶项,而无需乘数。例如:

O((n / 2 + 1)*(n / 2))= O(n2/ 4 + n / 2)= O(n2/ 4)= O(n2)

请注意,这不适用于无限系列。尽管在某些常见情况下,以下不等式适用于一般情况,但没有一个单一的配方:

O(对数N)<O(N)<O(N日志N)<O(N2)<O(Nk)<O(en)<O(n!)

来源
Translate

我从信息方面考虑。任何问题都包括学习一定数量的位。

您的基本工具是决策点及其熵的概念。决策点的熵是它将为您提供的平均信息。例如,如果程序包含具有两个分支的决策点,则它的熵是每个分支的概率与对数的和2分支的逆概率。这就是您执行该决定所学到的东西。

例如,if具有两个均等可能的分支的语句的熵为1/2 * log(2/1)+ 1/2 * log(2/1)= 1/2 * 1 + 1/2 * 1 = 1。它的熵是1位。

假设您正在搜索N个项目的表,例如N = 1024。那是一个10位的问题,因为log(1024)= 10位。因此,如果您可以使用具有相同可能结果的IF语句进行搜索,则应该做出10个决策。

这就是二进制搜索的结果。

假设您正在执行线性搜索。您查看第一个元素,并询问它是否是您想要的元素。概率是1/1024,不是1023/1024。该决策的熵为1/1024 * log(1024/1)+ 1023/1024 * log(1024/1023)= 1/1024 * 10 + 1023/1024 *大约0 =大约0.01位。您学到的很少!第二个决定并不更好。这就是线性搜索如此缓慢的原因。实际上,它是您需要学习的位数的指数。

假设您正在建立索引。假设该表已预先分类为很多bin,并且您使用键中的所有位中的一些直接索引到表项。如果有1024个bin,则对于所有1024个可能的结果,熵为1/1024 * log(1024)+ 1/1024 * log(1024)+...。这是1/1024 * 10乘以1024个结果,或该索引操作的10位熵。这就是为什么索引搜索速度快的原因。

现在考虑排序。您有N个项目,并且有一个列表。对于每个项目,您必须搜索该项目在列表中的位置,然后将其添加到列表中。因此,排序大约需要基础搜索步骤数的N倍。

因此,基于具有大致相同可能性结果的二元决策进行的排序全都需要O(N log N)个步骤。如果O(N)排序算法基于索引搜索,则可能是可行的。

我发现几乎所有算法性能问题都可以通过这种方式解决。

来源
Translate

让我们从头开始。

首先,接受以下原则:可以对数据进行某些简单的操作O(1)时间,即与输入大小无关的时间。这些在C中的原始运算包括

  1. 算术运算(例如+或%)。
  2. 逻辑运算(例如&&)。
  3. 比较操作(例如,<=)。
  4. 结构访问操作(例如,像A [i]这样的数组索引,或者跟随->运算符的指针)。
  5. 简单分配,例如将值复制到变量中。
  6. 调用库函数(例如scanf,printf)。

要证明此原理的正确性,需要对典型计算机的机器指令(原始步骤)进行详细研究。所描述的每个操作都可以使用少量的机器指令来完成。通常只需要一两个指令。因此,可以在C中执行多种C语句O(1)时间,即与输入无关的恒定时间。这些简单的包括

  1. 在表达式中不包含函数调用的赋值语句。
  2. 阅读声明。
  3. 编写不需要函数调用来评估参数的语句。
  4. 跳转语句中断,继续,转到和返回表达式,其中表达式不包含函数调用。

在C语言中,通过将索引变量初始化为某个值,并在每次循环时将该变量递增1,从而形成许多for循环。当索引达到某个限制时,for循环结束。例如,for循环

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

使用索引变量i。每次在循环中将i递增1,并且当i达到n − 1时,迭代将停止。

不过,目前,我们只关注简单的for循环形式,最终值和初始值之间的差除以index变量递增的数量,可以告诉我们循环执行了多少次。除非有某种方法可以通过跳转语句退出循环,否则该计数是准确的。在任何情况下,它都是迭代次数的上限。

例如,for循环迭代((n − 1) − 0)/1 = n − 1 times,因为0是i的初始值,所以n-1是i达到的最大值(即,当i达到n-1时,循环停止,并且在i = n-1时不发生迭代),并且将1加到我在循环的每次迭代。

在最简单的情况下,每次迭代在循环主体中花费的时间相同,我们可以将身体的大哦上限乘以循环的次数。严格来说,我们必须添加O(1)时间以初始化循环索引,并添加O(1)时间以将循环索引与限制进行第一次比较,因为我们比循环测试多了一个时间。但是,除非可以执行零次循环,否则初始化循环和测试极限一次的时间是可以由求和规则删除的低阶项。


现在考虑以下示例:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

我们知道行(1)需要O(1)时间。显然,我们绕了n次循环,因为我们可以通过从第(1)行中找到的上限减去下限然后加1来确定。由于主体(2)行花费了O(1)时间,我们可以忽略增加j的时间以及将j与n进行比较的时间,两者均为O(1)。因此,第(1)行和第(2)行的运行时间为n和O(1)的乘积,这是O(n).

同样,我们可以限制由(2)到(4)行组成的外部循环的运行时间,即

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

我们已经确定线(3)和(4)的循环需要O(n)时间。因此,我们可以忽略O(1)的时间来增加i并在每次迭代中测试i <n,从而得出结论,外循环的每次迭代都花费O(n)时间。

外循环的初始化i = 0和条件i <n的第(n + 1)次测试同样需要O(1)时间,因此可以忽略。最后,我们观察到我们绕着外循环运行了n次,每次迭代花费O(n)时间,得出O(n^2)运行时间。


一个更实际的例子。

enter image description here

来源
Translate

如果您想凭经验估计代码的顺序而不是通过分析代码,则可以坚持使用一系列递增的n值和时间来增加代码时间。在对数刻度上绘制您的时间。如果代码为O(x ^ n),则值应落在斜率n的直线上。

与仅研究代码相比,这具有多个优点。一方面,您可以看到您是否处于运行时间接近其渐近顺序的范围内。同样,您可能会发现某些您认为是阶O(x)的代码实际上是阶O(x ^ 2),例如,由于在库调用中花费了时间。

来源
Translate

基本上,90%的时间都收获的东西只是分析循环。您是否有单,双,三嵌套循环?您有O(n),O(n ^ 2),O(n ^ 3)运行时间。

极少数情况下(除非您正在编写带有扩展基础库的平台(例如.NET BCL或C ++的STL),否则您会遇到比仅查看循环(对于语句,语句,goto,等等...)

来源
Gustave Lee
Translate

大O表示法很有用,因为它易于使用并隐藏了不必要的复杂性和细节(对于不必要的定义)。树法是解决分而治之算法复杂性的一种不错的方法。假设您有一个带有中值过程的quicksort版本,因此每次都将数组拆分为完全平衡的子数组。

现在构建一个与您使用的所有阵列相对应的树。在根目录下,您拥有原始数组,在根目录下,有两个子数组,它们是子数组。重复此操作,直到底部有单个元素数组。

由于我们可以找到O(n)时间的中位数,并在O(n)时间中将数组分为两部分,因此每个节点的工作量为O(k),其中k是数组的大小。树的每个级别最多包含整个数组,因此每个级别的工作量为O(n)(子数组的大小总计为n,并且由于每个级别有O(k),因此我们可以将其相加) 。自从我们每次将输入减半后,树中只有log(n)级别。

因此,我们可以通过O(n * log(n))来限制工作量。

但是,Big O隐藏了一些有时我们无法忽略的细节。考虑使用以下方法计算斐波那契数列

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

并假设a和b是Java中的BigIntegers或可以处理任意大数的东西。大多数人会说这是一种O(n)算法,不会退缩。原因是在for循环中有n次迭代,而O(1)在循环中起作用。

但是斐波那契数很大,第n个斐波那契数在n中是指数的,因此仅存储它就需要n个字节的顺序。用大整数执行加法将需要O(n)的工作量。因此,此过程中完成的总工作量为

1 + 2 + 3 + ... + n = n(n-1)/ 2 = O(n ^ 2)

因此,该算法运行在四基时间!

来源
Translate

我认为总体上来说有用性较低,但是为了完整起见,大欧米茄Ω,它定义了算法复杂度的下限,并且大θ,它定义了上限和下限。

来源
Translate

将算法分解为您知道大O表示法的部分,并通过大O运算符进行组合。那是我唯一知道的方法。

有关更多信息,请检查维基百科页面就此主题而言。

来源
Translate

熟悉我使用的算法/数据结构和/或快速嵌套嵌套浏览分析。困难在于您可能多次调用库函数-您常常不确定是否有时会不必要地调用该函数或它们正在使用哪种实现。也许库函数应该具有复杂性/效率度量,无论是Big O还是其他度量标准,都可以在文档中找到,甚至可以使用智能感知.

来源
Translate

关于“您如何计算”大O,这是计算复杂度理论。对于某些(许多)特殊情况,您可能可以使用一些简单的启发式方法(例如,将循环计数乘以嵌套循环),尤其是。当您想要的只是任何上限估计,而您也不介意它是否过于悲观-我想这可能是您的问题所在。

如果您真的想回答任何算法的问题,那么您最好的方法就是运用理论。除了简单的“最坏情况”分析,我发现摊销分析在实践中非常有用。

来源
Translate

对于第一种情况,执行内部循环n-i次,因此执行的总次数是i0n-1(因为低于,不低于或等于)n-i。你终于得到了n*(n + 1) / 2,所以O(n²/2) = O(n²).

对于第二个循环,i在。。。之间0n包含在外循环中;然后在执行内部循环时j严格大于n,那么这是不可能的。

来源
Translate

除了使用master方法(或其专业之一)之外,我还通过实验测试了我的算法。这不能证明可以实现任何特定的复杂度等级,但可以保证数学分析是适当的。为了保证这种安全,我将代码覆盖率工具与实验结合使用,以确保我能正确执行所有案例。

举一个非常简单的例子,您想对.NET框架的列表排序速度进行完整性检查。您可以编写类似以下内容的内容,然后在Excel中分析结果以确保它们不超过n * log(n)曲线。

在此示例中,我测量了比较的数量,但是检查每种样本大小所需的实际时间也是谨慎的。但是,然后您必须更加小心,仅在测量算法而不包括测试基础结构中的工件。

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);
来源
Translate

不要忘记也要考虑空间复杂性,如果内存资源有限,这也可能引起人们的关注。因此,例如,您可能听到有人想要一个恒定空间算法,这基本上是一种说法,即算法占用的空间量不取决于代码内的任何因素。

有时,复杂性可能来自于所谓的调用次数,循环执行的频率,内存分配的频率等等,这是回答此问题的另一部分。

最后,大O可以用于最坏情况,最佳情况和摊销情况,其中通常使用最坏情况来描述算法可能有多糟糕。

来源
Translate

经常被忽视的是预期算法的行为。它不会改变算法的Big-O,但确实与“过早优化……”语句有关。

算法的预期行为-非常笨拙-可以预期算法在最有可能看到的数据上运行的速度。

例如,如果要在列表中搜索值,则为O(n),但是如果您知道大多数列表中都预先包含了值,则算法的典型行为会更快。

要真正确定下来,您需要能够描述“输入空间”的概率分布(如果您需要对列表进行排序,那么该列表将被排序的频率是多少?完全颠倒的频率是多少?通常知道它是大多数排序的吗?)知道这一点并不总是可行的,但有时您知道。

来源
Translate

好问题!

免责声明:此答案包含错误的陈述,请参阅以下评论。

如果您使用的是Big O,则是在谈论最坏的情况(稍后会详细介绍)。此外,一般情况下有资本theta,最好情况下有大欧米茄。

在此站点上查看Big O的漂亮正式定义:https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n)= O(g(n))表示存在正常数c和k,使得对于所有n≥k,0≤f(n)≤cg(n)。 c和k的值必须对于函数f是固定的,并且不得依赖于n。


好的,那么现在我们所说的“最佳情况”和“最坏情况”复杂度是什么意思?

通过示例可以最清楚地说明这一点。例如,如果我们使用线性搜索在排序数组中查找数字,则最坏的情况下当我们决定搜索最后一个元素数组的数量,因为这将花费与数组中所有项目一样多的步骤。的最好的情况就是当我们搜索第一要素因为我们会在第一次检查后完成。

所有这些的重点形容词-case的复杂性是我们正在寻找一种方法来根据特定变量的大小来绘制假设程序运行到完成所需的时间。但是,对于许多算法,您可能会争辩说,特定大小的输入不会一次出现。请注意,这与功能的基本要求相矛盾,任何输入最多只能有一个输出。所以我们想出了函数来描述算法的复杂性。现在,即使搜索大小为n的数组可能会花费不同的时间,具体取决于您在数组中寻找的内容以及与n成正比的关系,我们仍可以使用最佳情况,平均情况来创建该算法的详尽描述和最坏情况的类。

抱歉,这是如此糟糕,并且缺乏很多技术信息。但是希望它将使时间复杂度类更容易考虑。一旦您对这些感到满意,那么就很简单了,可以通过程序进行解析,然后查找诸如for循环之类的事情,这些事情取决于数组的大小,并根据您的数据结构进行推理,什么样的输入会导致微不足道的情况,什么输入会导致结果。在最坏的情况下。

来源
Translate

我不知道如何以编程方式解决此问题,但人们要做的第一件事是我们对完成的操作数中的某些模式进行算法采样,例如4n ^ 2 + 2n + 1,我们有2条规则:

  1. 如果我们有一个术语的总和,则保留增长率最高的术语,而省略其他术语。
  2. 如果我们有几个因子的乘积,则常量因子将被忽略。

如果简化f(x),其中f(x)是完成的操作数的公式,(上面解释的4n ^ 2 + 2n + 1),我们将获得big-O值[O(n ^ 2)案件]。但这将不得不考虑程序中的拉格朗日插值,这可能很难实现。而且,如果真正的big-O值为O(2 ^ n),又可能有O(x ^ n)之类的东西,那么该算法可能就无法编程。但是如果有人证明我错了,请给我密码。 。 。 。

来源
Translate

对于代码A,外部循环将针对n+1次,“ 1”时间表示检查我是否仍满足要求的过程。和内循环运行n时间,n-2时间....因此,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

对于代码B,尽管内部循环不会介入并执行foo(),但内部循环将执行n次,具体取决于外部循环的执行时间,即O(n)

来源
HmT
Translate

我想从一些不同的方面来解释Big-O。

Big-O只是用来比较程序的复杂性,这意味着输入增加时它们增长的速度,而不是执行该操作所花费的确切时间。

恕我直言,在big-O公式中,您最好不要使用更复杂的方程式(您可能只是坚持下图中的方程式。)但是,您仍然可以使用其他更精确的公式(例如3 ^ n,n ^ 3,.. 。),但有时可能会误导他人!因此最好使其尽可能简单。

enter image description here

我想再次强调,这里我们不想为我们的算法获得确切的公式。我们只想显示输入增长时它是如何增长的,并在这种意义上与其他算法进行比较。否则,您最好使用不同的方法,例如基准测试。

来源