如何知道要使用的时间复杂性分析的表示法？

cs.stackexchange https://cs.stackexchange.com/questions/57

题

在大多数介绍性算法类中，引入了$ o $（big o）和$ theta $之类的符号，并且学生通常会学会使用其中之一来找到时间复杂性。

但是，还有其他符号，例如$ o $，$ omega $和$ omega $。是否有任何特定方案，一个符号比另一种符号更可取？

有帮助吗？

解决方案

你指的是 兰道符号. 。对于同一事物，它们不是不同的符号，但具有完全不同的含义。哪一个是“可取的”，完全取决于所需的陈述。

$ f in cal {o}（g）$表示$ f $最多生长至$ g $，渐近且最大为恒定因素；将其视为$ leq $。 $ f in O（g）$是更严格的表格，即$ <$。

$ f in omega（g）$具有对称含义：$ f $至少生长至$ g $。 $ Omega $是其更严格的表弟。您可以看到 omega（g）$中的$ f 等于$ g in cal {o}（f）$。

$ f in theta（g）$表示$ f $生长的速度与$ g $一样快；正式地$ f in cal {o}（g） cap omega（g）$。 $ f sim g $（渐近平等）是其更强的形式。当我们使用$ cal {o} $时，我们通常是指$ theta $。

请注意$ cal {o}（g）$及其兄弟姐妹 功能类. 。重要的是要非常意识到这一点及其确切的定义 - 在与他们进行“算术”时，这取决于谁在说话。

在证明事情时，请注意处理您的精确定义。周围有许多定义（所有具有相同的基本直觉）的定义，其中一些在功能上的某些集合中等效，但在其他函数上却不相等。

建议阅读：

如果您有兴趣以严格和合理的方式使用Landau符号，那么您可能对Rutanen等人的最新工作感兴趣。 [1]。它们为我们在算法中使用它们的渐近符号制定了必要和足够的标准，表明常见的定义无法满足它们，并提供了（实际上）可行的定义。

  1. O算法分析的O通知的一般定义 K. Rutanen等人。 （2015）

其他提示

大O：上限

到目前为止，“ Big O”（$ O $）是最常见的。当您分析算法的复杂性时，大多数情况下，重要的是要在输入大小增长时运行时间的速度有一定的界限。基本上，我们想知道，运行该算法不会“太长”。我们不能在实际时间单元（秒）中表达这一点，因为这取决于精确的实现（编写程序的方式，编译器的良好方式，机器的处理器的速度，…）。因此，我们评估什么不取决于此类细节，这是在将算法输入更大的输入时运行算法所需的时间。我们主要在乎何时确定该程序已经完成，因此我们通常想知道这需要花费大量时间或更短的时间。

要说算法的运行时间为$ o（f（n））$的$ n $ $ n $表示存在一些常数$ k $，因此该算法最多可以完成$ k ，f（n ）$ step，即该算法的运行时间最多增长至$ f $（最多达到缩放系数）。注意到$ t（n）$输入尺寸$ n $，$ o（n）$的运行时间非正式地表示$ t（n） le f（n）$达到某种比例。

下限

有时，拥有比上限更多的信息是有用的。 $ omega $是$ o $的相反：它表明函数的增长至少与另一个功能一样快。 $ t（n）= omega（g（n））$表示某些常数$ k'$或非正式地将$ t（n）$ t（n）$ t（n） ge k'g（n）$ ge g（n）$达到一定的缩放因素。

当可以精确确定算法的运行时间时，$ theta $ combines $ o $和$ omega $：它表明函数的增长率已知，最多是缩放因素。 $ t（n）= theta（h（n））$表示某些常数$ k h（n） ge t（n） ge k'h（n）$对于某些常数$ k $和$ k'$。从非正式的说法中，$ t（n）大约h（n）$达到某种缩放系数。

进一步的考虑

在复杂性分析中，“小” $ o $和$ omega $使用的频率要少得多。小$ o $比大$ o $强； $ o $表示增长的速度不快，$ o $表明该增长严格较慢。相反，$ omega $表示严格的增长速度更快。

我在上面的讨论中有些非正式。 维基百科 具有正式定义和更数学的方法。

请记住，在$ t（n）= o（f（n））$中使用平等符号等是错误的名称。严格来说，$ o（f（n））$是变量$ n $的一组功能，我们应该在o（f）$中编写$ t 。

示例：某些排序算法

因为这很干，让我举个例子。大多数排序算法具有二次最差的情况运行时间，即用于尺寸$ n $的输入，该算法的运行时间为$ O（n^2）$。例如， 选择排序 具有$ O（n^2）$运行时间，因为选择$ k $ th元素需要$ nk $比较，总计$ n（n-1）/2 $比较。实际上，比较数量始终是$ n（n-1）/2 $，其增长为$ n^2 $。因此，我们可以更精确地选择选择的时间复杂性：它是$ theta（n^2）$。

现在服用 合并排序. 。合并排序也是二次（$ O（n^2）$）。这是真的，但不是很精确。实际上，合并的运行时间为$ O（N ： Mathrm {lg}（n））$在最坏的情况下。像选择排序一样，Merge Sort的工作流程本质上独立于输入的形状，并且其运行时间始终为$ n ： mathrm {lg}（n）$，直至一个恒定的乘法因素，即它是$ theta （n ： mathrm {lg}（n））$。

接下来，考虑 QuickSort. 。 QuickSort更为复杂。当然是$ O（n^2）$。此外，QuickSort最糟糕的情况是二次： 最坏的情况下 是$ theta（n^2）$。但是，QuickSort的最佳情况（当输入已经排序时）是线性的：我们可以说的最好的是$ omega（n）$的coocksort的下限。我不会在这里重复证明，但是 平均 复杂 QuickSort（输入输入的所有可能排列的平均值）为$ theta（n ： mathrm {lg}（n））$。

关于在公共设置中分类算法的复杂性的一般结果。假设排序算法一次只能比较两个元素，并与Yes-or-no结果（$ x le y $或$ x> y $）。那么，很明显，任何排序算法的运行时间始终是$ omega（n）$（其中$ n $是要排序的元素的数量），因为该算法必须至少比较一次，以了解其适合位置的每个元素。例如，如果已经对输入进行排序，并且该算法仅将每个元素与下一个元素进行比较并保持顺序（那是$ n-1 $比较）。不太明显的是 最大 运行时间必定是$ omega（n ： mathrm {lg}（n））$。该算法有时可能会进行更少的比较，但是必须有一些恒定的$ k $，以便对于任何输入尺寸$ n $，至少有一个输入，该算法在该输入中可产生超过$ k n mathrm { lg}（n）$比较。证明的想法是构建算法的决策树，即遵循算法从每个比较的结果中做出的决策。由于每个比较都返回一个是或不可以的结果，因此决策树是二进制树。有$ n！$可能的输入排列，算法需要区分所有输入，因此决策树的大小为$ n！$。由于树是二进制树，因此需要$ theta的深度（ mathrm {lg}（n！））= theta（n ： mathrm {lg}（n））$适合所有这些节点。深度是该算法采取的最大决策数，因此运行算法至少涉及这么多比较：最大运行时间为$ omega（n ： mathrm {lg}（n））$。

¹ 或其他资源消耗，例如内存空间。在此答案中，我只考虑运行时间。

通常，$ o $用于说明上限（从上方估算），而$ omega $用于陈述下限（从下方估算），并且在匹配时使用$ theta $案例您可以（通常）使用$ theta $来陈述结果。

许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top