为什么大Oh不总是算法的最坏情况分析?

大O?

首先让我们看看 Big O 正式指:

在计算机科学中,大O符号用于对算法进行分类 根据其运行时间或空间需求随 输入大小增加。

这意味着,大O表示法根据函数的增长率来表征函数: 具有相同增长率的不同函数可以使用相同的O表示法表示 .这里,O表示 函数的顺序 ,它只提供 上限 关于函数的增长率。

现在让我们看看大O的规则:

• 如果f(x)是几个项的和,如果有一项最大 增长率可以保持,其他都可以省略
• 如果f(x)是多个因子的乘积,则 不依赖于x)的产品可以省略。

示例:

f(x)=6x^4 2x^3+5

使用第一条规则,我们可以把它写成,f(x)=6x^4

使用第二条规则,它会给我们,O(x^4)

什么是 最坏情况 ?

最坏情况分析给出了 必须在算法执行期间执行。它假设 输入处于可能的最差状态,最大功必须 一定要把事情做对。

例如,对于旨在按升序对数组进行排序的排序算法,最坏的情况发生在输入数组按降序排序时。在这种情况下,必须执行最大数量的基本操作(比较和赋值),才能按升序设置数组。

这取决于很多因素,如:

• CPU(时间)使用率
• 内存使用情况
• 磁盘使用情况
• 网络使用情况

有什么区别?

Big-O通常用于对函数进行陈述,以衡量算法的最坏情况行为,但Big-O表示法并不意味着这类内容。

这里重要的一点是,我们谈论的是增长,而不是运营数量。然而,对于算法,我们确实讨论了与输入大小相关的操作数。

Big-O用于对函数进行声明。这些函数可以测量时间或空间,或者缓存岛上的未命中或兔子,或者任何东西或什么都不缓存。Big-O表示法并不重要。

事实上,当用于算法时,big-O几乎与时间无关。它是关于基本操作的。

当有人说MergeSort的时间复杂度是O(nlogn)时,他们通常意味着MergeSort进行的比较次数是O(nlogn)。这本身并没有告诉我们任何特定MergeSort的时间复杂性,因为这将取决于进行比较所需的时间。换句话说,O(nlogn)将比较称为原语操作。

这里重要的一点是,当big-O应用于算法时,总是有一个底层的计算模型。MergeSort的时间复杂度为O(nlogn)的说法隐含地引用了一种计算模型,其中比较需要恒定的时间,其他一切都是免费的。

示例-

如果我们对长度为kk字节的字符串进行排序,我们可能会将读取一个字节作为一个基本操作,该操作需要固定的时间,其他所有操作都是空闲的。

在此模型中,MergeSort进行O(nlogn)字符串比较,每个字符串进行O(k)字节比较,因此时间复杂度为O(k–nlogn)。RadixSort的一个常见实现将在n个字符串上进行k次传递,每次传递读取一个字节,因此时间复杂度为O(nk)。

这两者不是一回事。正如其他人所说,最坏情况分析是识别算法完成时间最长的实例(即,步骤最多),然后使用该方法制定增长函数。人们可以使用大Oh,甚至其他变量,如大Omega和大Theta,来分析最坏情况下的时间复杂度(事实上,大Theta通常是你想要的,尽管大Oh通常是为了便于那些不太懂理论的人理解)。最坏情况分析之所以有用的一个重要细节是,算法的运行速度不会比最坏情况下的运行速度慢。最坏情况分析是我们在分析算法时使用的一种分析方法。

大Oh本身是增长函数的渐近度量;这可以是完全独立的,因为人们可以使用大Oh甚至不测量算法的时间复杂度;它起源于数论。你说它是增长函数的渐近上界是正确的;但是你制定和构建增长函数的方式来自你的分析。生长函数本身的大Oh在没有上下文的情况下几乎没有意义,因为它只说明了您正在分析的函数。请记住,可以构建无限多个具有相同时间复杂性的算法(根据大Oh的定义,大Oh是一组增长函数)。

简而言之,最坏情况分析是如何构建增长函数,大Oh表示法是分析上述增长函数的一种方法。然后,我们可以将该结果与给定问题的竞争算法的其他最坏情况时间复杂性进行比较。如果正确地进行最坏情况分析,则会产生最坏情况下的运行时间(如果使用气压计,则可以省去很多弯路,仍然可以获得正确的渐近值),并且使用此增长函数会产生算法的最坏情况时间复杂度。仅凭Big Oh并不能保证最坏情况下的时间复杂性,因为您必须使增长函数本身。例如,我可以将大Oh符号用于任何其他类型的分析(例如,最佳情况、平均情况)。这真的取决于你想要捕捉什么。例如,大欧米茄对于下限来说是很好的。

设想一个假设的算法,在最佳情况下只需要执行1步,在最坏情况下需要执行n2步,但在平均(预期)情况下,只需要执行n步。n是输入大小。 对于这三种情况中的每一种,您都可以计算一个描述此算法时间复杂性的函数。 最好的情况是O(1),因为函数f(x)=1实际上是我们能达到的最高值,但也是我们能达到的最低值,ω(1)。由于ω等于O(上界和下界),我们声明,在最佳情况下,此函数的行为类似于θ(1)。 2我们可以对最坏的情况做同样的分析,得出O(n2)=ω(n2)=θ(n2)。 3平均情况下相同的计数,但θ(n)。 因此,在理论上,可以确定一个算法的3种情况,并为这3种情况计算下限/上限/thight界限。我希望这能把事情弄清楚一点。

https://www.google.co.in/amp/s/amp.reddit.com/r/learnprogramming/comments/3qtgsh/how_is_big_o_not_the_same_as_worst_case_or_big/

大O表示法显示了算法是如何随着输入大小而增长的。它没有说明哪种算法更快,因为它没有考虑到恒定的设置时间(如果输入量较小,设置时间可能占主导地位)。所以当你说

需要O(n)个执行步骤

这几乎没有任何意义。大O没有说有多少执行步骤。有C+O(n)步(其中C是常数),该算法根据输入大小以n的速率增长。

大O可以用于最佳、最差或一般情况。让我们以排序为例。冒泡排序是一种简单的O(n^2)排序算法,但当列表排序时需要O(n)。快速排序通常用于排序(GNU标准C库对其进行了一些修改)。它在O(n log n)处执行,但只有当所选枢轴将阵列拆分为两个大小相等的块(平均)时,才是这样。在最坏的情况下,我们在数据透视的一侧得到一个空数组,快速排序在O(n^2)处执行。

由于大O显示了算法是如何随着大小而增长的,因此您可以查看算法的任何方面。它在时间和/或内存使用方面的最佳情况、平均情况和最坏情况。它告诉你当输入大小增加时这些是如何增长的,但它没有说哪个更快。

如果你处理的是小规模的问题,那么大O就无关紧要了——但分析可以告诉你,当你的输入规模增加时,情况会怎样。

最坏情况可能不是渐近极限的一个例子是:假设您有一个算法可以处理某个集合和输入之间的集合差。它可能会跑进来 O ( N )时间,但随着输入变大并从工作集中敲出更多值,速度会变快。

或者,更抽象地说, F ( 十、 )=1/ 十、 对于 十、 &燃气轮机;0是递减的 O (1) 功能。

我将把时间作为一个非常常见的关注点,但Big-O也可以用于评估内存等资源需求。您必须认识到,Big-O告诉您问题的运行时或资源需求 规模 (渐近)随着问题规模的增加。确实如此 不 为您提供所需实际时间的预测。预测实际运行时需要我们知道预测公式中的常量和低阶项,它们取决于硬件、操作系统、语言、编译器等。使用Big-O可以让我们在避开所有这些依赖关系的同时讨论算法行为。

让我们用几个例子来讨论如何解释Big-O的可伸缩性。如果问题为O(1),则无论问题大小,所需的时间都是相同的。这可能是一纳秒或1000秒,但在极限范围内,问题的大小增加一倍或三倍不会改变时间。如果问题是O(n),那么将问题大小加倍或三倍将(渐进地)分别使所需时间加倍或三倍。如果一个问题是O(n^2),那么将问题大小加倍或加倍(渐进地)分别需要4倍或9倍的时间。等等

许多算法在最佳、平均或最差情况下都有不同的性能。排序提供了一些非常简单的示例,说明了最佳、平均和最坏情况分析的区别。

我想你知道怎么做 insertion sort 作品在最坏的情况下,列表可能是逆序的,在这种情况下,对于所有项目,每次传递都必须将当前正在考虑的值尽可能向左移动。这就产生了O(n^2)行为。将列表大小加倍将需要四倍的时间。更有可能的是,输入列表是按随机顺序排列的。在这种情况下,每个项目平均必须向列表前面移动一半的距离。这比最坏的情况要小,但只有一个常数。它仍然是O(n^2),所以对一个随机列表进行排序,这个随机列表的大小是第一个随机列表的两倍,平均所需时间将是第一个随机列表的四倍。它将比最坏的情况更快(由于涉及的常数),但它以同样的方式扩展。然而,最好的情况是当列表已经排序时。在这种情况下,您检查每个项目是否需要向前滑动,并立即发现答案是“否”,因此在检查完n个值后,您将在O(n)时间内完成。因此,对一个大小为两倍的已排序列表使用插入排序只需要两倍的时间,而不是四倍的时间。

你是对的,因为你可以肯定地说,算法运行在 O(f(n)) 最佳或一般情况下的时间。我们一直这样做,比如说,快速排序 O(N日志N) 平均而言,但仅 O(N^2) 最坏情况。

除非另有规定,但是,当您说算法在 O(f(n)) 时间,你是说算法运行 O(f(n)) 时间 在最坏的情况下 .至少应该是这样的。有时人们会变得马虎,你会经常听到哈希表 O(1) 在最坏的情况下,情况实际上更糟。

大O定义无法描述最坏情况的另一种方式是 仅上限 .中的任何函数 O(N) 是 而且 在里面 O(N^2) 和 O(2^N) ,所以我们可以完全正确地说,快速排序需要 O(2^N) 时间我们只是不这么说,因为这样做没有用。

大θ和大ω分别用于指定下界和紧界。