使用最差/平均/最佳情况进行渐近分析
我知道最差/平均/最好的情况是用来确定一个算法的复杂性时间，但它是如何用于渐近分析？ 我知道上/下/下界（大O，大欧米茄，大θ）用于比较两个函数，并且看到它的局限性（增长）对另一个角度是透视的，因为n增加，但是我看到最差/平均/最好情况下大O和渐近分析之间的差异。 我们究竟将最坏/平均/最好情况下的大O输入到渐近分析和测量范围？ 我们是否会使用渐近分析来具体比较两种最差/平均/最佳情况下的大O算法？ 如果这样做，我们对算法1使用函数f（n），算法2使用函数f（n），或者我们对算法1是f（n）的每个算法进行单独的渐近分析，并且试图找到一些c * g（n ）使得=> f（n）并且使得c * g（n）<= f（n），然后对算法2做同样的事情。我在这里没有看到大图。
既然你想要大局，让我试着给你一样的。
渐近分析用于研究随着输入大小的增加，运行时间如何增长。这种增长是根据输入大小来研究的。输入大小，通常表示为N或M ，它可能意味着任何数目的数字（如在排序中），节点数量（如图中所示）或甚至比特数量（如两个数字的乘法）。
在处理渐近分析时，我们的目标是找出哪种算法在特定情况下的性能更好。实际上，即使对于相同大小的输入，也可以在相当不同的时间运行算法。要了解这一点，请考虑您是排序机器。您将获得一组你需要对它们进行排序。如果我给你一个有序的数字列表，你就没有工作，并且你已经完成了。如果我给了你一个反向排序的数字列表，想象你需要的操作数目如果你看到这一点，意识到我们需要知道输入是什么情况的方式？它会是最好的情况吗？我会得到一个最坏的情况输入吗？为了回答这个问题，我们需要一些关于投入分配的知识。是最坏的情况吗？还是一般情况？还是大多数情况下是最好的情况？
输入分布的知识在大多数情况下很难确定。然后我们剩下两个选择。我们可以一直假设平均情况并分析我们的算法，或者我们可以在运行情况下获得保证，而不管输入分配。前者被称为平均案例分析，做这样的分析需要对什么是平均情况进行正式定义。有时候这很难界定，并且需要很多数学洞察力。所有这些麻烦都是值得的，当你知道一些算法在平均情况下运行速度比其最坏情况下的运行时间快得多。有几种随机算法证明了这一点。在这种情况下，进行平均情况分析揭示了它的实际适用性。 后者，最糟糕的情况分析更常用，因为它为运行时间提供了一个很好的保证。在实践中遇到最糟糕的情况往往是相当直观的。你是排序机器，最坏的情况就像是反向排序数组什么是平均情况？
是的，你在想，对不对？
最好的案例分析很少被使用，因为人们并不总是能得到最好的案例。只有一个人可以做这样的分析并找到有趣的行为。
总之，当我们有一个我们想要解决的问题时，我们想出了算法。一旦我们有了一个算法，我们需要决定它是否对我们的情况有任何实际用处。如果是这样，我们继续并将可以算出来的算法根据时间和空间的复杂程度进行比较。可以有更多的指标进行比较，但这两个指标是基本的。一个这样的指标可以很容易实现。并且根据手头的情况，yu会采用最坏的情况分析或平均案例分析或最佳案例分析。例如，如果您很少遇到最糟糕的情况，那么进行平均案例分析就更有意义。但是，如果我们的代码的性能具有关键性质，并且我们需要提供在严格的时间限制内输出，那么对于最糟糕的情况分析来说，要谨慎得多。因此，你所做的分析取决于手头的情况，随着时间的推移，应用哪种分析的直觉成为第二性质。
请询问你是否有更多问题。
了解更多关于大哦，其他符号阅读我的答案在这里和这里。
关于quicksort的维基百科文章提供了一个很好的例子，说明如何在最佳/平均/最差情况下使用渐近分析：它的最坏情况是O（n ^ 2），平均情况是O（n log n），最好是如果你将这个与另一个算法（比如heapsort）相比较，你会比较苹果和苹果，例如你会比较quicksort的最坏情况的big-theta和heapsort的最坏情况的big- theta，或者quicksort的空间很大 - 哦，heapsort的空间很大哦。
如果你对上限感兴趣，你也可以比较big-theta和big-oh，如果你对下限感兴趣，你也可以将big-theta与big-omega比较。
大欧米茄通常只具有理论上的兴趣 - 你更有可能以大哦或大角度来看待分析。
我们究竟将最坏/平均/最好情况下的大O输入到渐近分析和测量范围？
当你比较不同的方法来解决某个问题时，它只是给出一个想法。 这将帮助您比较不同的方法。
我们是否会使用渐近分析来具体比较两种最差/平均/最佳情况下的大O算法？
通常情况下，只有糟糕的情况才会得到更多的关注，相比大欧米茄和theta。 是的，我们对算法1使用函数f（n），对算法使用g（n）。 这些函数是它们各自算法的大O.
链接地址: http://www.djcxy.com/p/40173.html