我了解最坏/平均/最佳情况用于确定算法在函数中的复杂性时间，但在渐近分析中如何使用？我了解上限/紧/下限（大 O，大欧米茄，大 theta）用于比较两个函数，并且随着 n 的增加，查看它的极限（增长）与另一个函数的关系，但我无法看到最坏/平均/最佳情况大 O 和渐近分析之间的区别。将我们的最坏/平均/最佳情况大 O 代入渐近分析和测量界限究竟能得到什么？我们是否会使用渐近分析来专门比较最坏/平均/最佳情况大 O 的两种算法？如果是这样，我们是对算法 1 使用函数 f(n)，对算法 2 使用 g(n)，还是对算法 1 为 f(n) 的每个算法进行单独的渐近分析，然后尝试找到一些 c*g(n ) 使得 => f(n) 和 c*g(n) <= f(n) 然后对算法 2 做同样的事情。我在这里没有看到大局。
问问题
1836 次
3 回答
4
既然你想要大局，让我试着给你同样的。
渐近分析用于研究运行时间如何随着输入大小的增加而增长。这种增长是根据输入大小来研究的。输入大小，通常表示为N或M，它可能意味着数字数量（如在排序中），节点数（如图形）或偶数位数（如两个数字相乘）。
在处理渐近分析时，我们的目标是找出在特定情况下哪种算法表现更好。意识到即使对于相同大小的输入，算法也会在不同的时间运行。要理解这一点，请考虑您是一台分拣机。您将获得一组数字，你需要对它们进行排序。如果我给你一个排序的数字列表，你将没有工作，你已经完成了。如果我给你一个反向排序的数字列表，想象一下你需要的操作数做以使列表排序。现在你看到了，意识到我们需要一种方法来知道输入是什么情况？这是最好的情况吗？我会得到最坏的情况输入吗？要回答这个问题，我们需要一些输入分布的知识。这都是最坏的情况吗？还是一般情况？还是大多数情况下是最好的情况？
在大多数情况下，输入分布的知识是相当难以确定的。那么我们有两个选择。要么我们可以一直假设平均情况并分析我们的算法，或者我们可以得到运行情况的保证，而不管输入分布。前者被称为平均案例分析，要进行这样的分析需要正式定义什么是平均案例。有时这很难定义，需要很多数学洞察力。所有的麻烦都是值得的，当您知道某些算法在平均情况下的运行速度比其最坏情况下的运行时间快得多时。有几种随机算法可以证明这一点。在这种情况下，进行平均情况分析揭示了它的实际适用性。后者，
是的，你在想，对吧？不是那么直观。
最好的案例分析很少使用，因为并不总是得到最好的案例。仍然可以进行这样的分析并找到有趣的行为。
总之，当我们有想要解决的问题时，我们会提出算法。一旦我们有了算法，我们需要确定它是否对我们的情况有任何实际用途。如果是，我们继续并列出可以解决的算法应用，并根据它们的时间和空间复杂度进行比较。可能有更多的指标进行比较，但这两个是基本的。这样的指标可以易于实施。根据手头的情况，你会采用最坏的情况分析或平均案例分析或最佳案例分析。例如，如果您很少遇到最坏情况，那么进行平均案例分析更有意义。但是，如果我们的代码性能具有关键性质，我们需要提供在严格的时间限制内输出，那么看最坏情况分析要谨慎得多。因此，您所做的分析取决于手头的情况，并且随着时间的推移，应用哪种分析的直觉成为第二天性。
请询问您是否有更多问题。
于 2013-08-12T08:59:56.730 回答
1
关于快速排序的Wikipedia 文章提供了一个很好的例子，说明如何在最佳/平均/最坏情况下使用渐近分析：最坏情况为 O(n^2)，平均情况为 O(n log n)，最佳情况为O(n log n) 的情况，如果您将其与另一个算法（例如 heapsort）进行比较，您会将苹果与苹果进行比较，例如，您会将快速排序的最坏情况 big-theta 与堆排序的最坏情况 big- theta，或快速排序的空间大哦到堆排序的空间大哦。
如果您对上限感兴趣，您还可以将 big-theta 与 big-oh 进行比较，如果您对下限感兴趣，则可以将 big-theta 与 big-omega 进行比较。
大欧米茄通常只具有理论意义——你更有可能看到大哦或大θ的分析。
于 2013-08-12T02:27:04.517 回答
0
将我们的最坏/平均/最佳情况大 O 代入渐近分析和测量界限究竟能得到什么？
当您针对某些问题比较不同的方法时，它只是给出了一个想法。这将帮助您比较不同的方法。
我们是否会使用渐近分析来专门比较最坏/平均/最佳情况大 O 的两种算法？
与 Big Omega 和 theta 相比，通常只有更糟糕的情况才会得到更多关注。是的，我们对算法 1 使用函数 f(n)，对算法使用 g(n)。这些函数是它们各自算法的大 O。
于 2013-08-12T13:23:31.793 回答