合并排序如何具有多个big-oh值? [英] How can merge sort have multiple big-oh values?

问题描述

在大Ө表示法的确切含义是什么?，最受支持的答案包含以下语句:

In What exactly does big Ө notation represent?, the most upvoted answer contains the following statement:

例如，合并排序最坏的情况是O(n*log(n))和Omega(n*log(n))，因此也是Ө(n*log(n))，但它也是O(n^2)，因为n^2渐近地比大".但是，它不是不是 Ө(n^2)，因为算法不是Omega(n^2).

For example, merge sort worst case is both O(n*log(n)) and Omega(n*log(n)) - and thus is also Ө(n*log(n)), but it is also O(n^2), since n^2 is asymptotically "bigger" than it. However, it is not Ө(n^2), Since the algorithm is not Omega(n^2).

我有两个问题:

1. 如何确定最坏的情况是O(n*log(n))和Omega(n*log(n)).在算法简介"中，您可以通过计算每个语句的执行次数和执行成本来确定Theta插入时间. O和Omega是否有类似的方法?
2. 如何合并排序的最坏情况是O(n*log(n))还是O(n^2)?

1. How do you determine that the worst case is O(n*log(n)) and Omega(n*log(n)). In "Introduction to Algorithms" you determine the Theta time of insertion sort by counting number of times and cost of the execution of each statement. Is there a similar method for O and Omega?
2. How can merge sort's worst-case be O(n*log(n)) but also O(n^2)?

推荐答案

首先，您问题中的链接未指向接受的答案.它指向最受好评的答案.

First thing, the link in your question does not point to the accepted answer. It points to the most upvoted answer.

现在，一个接一个地回答您的问题...

Now, answering your questions one by one...

如何确定最坏的情况是O(nLog(n))和Ω(nLog(n)).在算法简介"中，您可以通过计算每个语句的执行次数和执行成本来确定插入的Theta时间. O和Omega有类似的方法吗?

How do you determine that the worst case is O(nLog(n)) and Ω(nLog(n)). In "Introduction to Algorithms" you determine the Theta time of insertion sort by counting number of times and cost of the execution of each statement. Is there a similar method for O and Omega?

为了使这个答案对每个人都有用，我将再次提及与合并排序"有关的要点.

For the sake of making this answer useful to everyone, I'll mention again the important points related to Merge Sort.

• 合并排序是一种分而治之的算法.
• 您采用一个数字序列，将其递归地分成两半，分别对两半进行排序，最后再递归合并两半，从而得到一个排序的数字序列.

采取最简单的情况.如果您在这种情况下运行合并排序"，您会触摸多少个元素?借助下面的图像，可以轻松实现可视化.每个级别涉及的元素是 cn ，总共有 lg n 个级别.因此，即使在最简单的情况下，触摸的总元素为 cnLog(n).

Take the most simplistic case. How many elements do you touch^† if you run the Merge Sort on that case? It is easy to visualize with the help of the image below. The elements touched at each level are cn and there are a total of lg n levels. So total elements touched, even in the easiest case, is cnLog(n).

^图像源

因此，合并排序将始终具有最小的复杂度≈cnLog(n)，并且也写为 合并排序为Ω(nLog( n)).

Thus, Merge Sort will always have a minimum complexity ≈ cnLog(n) and that's also written as Merge Sort is Ω(nLog(n)).

好的.因此，我们了解到，即使在该算法最简单的运行中，我们也必须触摸序列元素总共 cnLog(n)次.现在...

Ok. So we understand that even in the most simplistic run of this algorithm we have to touch the elements of the sequence a total of cnLog(n) times. Now...

否则我们要触摸序列元素多少次?那么，无论如何，合并排序"的递归树将与上面的完全相同.因此，事实证明，我们将始终具有与 nLog(n)成比例的合并排序的运行时复杂性！这意味着合并排序的上限和下限均为 cnLog(n).

How many times do we touch the elements of the sequence otherwise? Well, in any case whatsoever, the recursion tree of Merge Sort will be exactly the same as above. So, it turns out that we will always have a run-time complexity of Merge Sort proportional to nLog(n)! This means that both, the upper as well as the lower bound of Merge Sort is cnLog(n).

因此， 合并排序的运行时复杂度不仅是Ω(nLog(n))，而且是O(nLog(n)) ，这意味着它是 Ө(nLog(n)).

Hence, Merge Sort's run time complexity is not only Ω(nLog(n)) but also O(nLog(n)) which means that it is Ө(nLog(n)).

_{您想查看(也可以可视化)为合并排序"完成的计算.我希望图形解释能够令人满意，该解释显示了在树的每个级别上完成的计算.}

如何合并排序的最坏情况是O(n * log(n))还是O(n ^ 2)?

How can merge sort's worst-case be O(n*log(n)) but also O(n^2)?

这很简单，但是就像前面的答案一样，我将从基本定义开始，以便该答案对每个人都有用.

That's straightforward, but just like the previous answer I'll begin with the basic definition so that the answer is useful to everyone.

我喜欢下面的图片，以了解术语.

I like the image below for understanding the terminologies.

^图片来源

请注意，Big-O仅强调上方边界.它不关心上面有多远.因此，算法的Big-O复杂性具有无限的功能.其中最有用的是紧接其上的那个，否则每个算法都是O( infinity ).

Pay attention that Big-O only stresses on bounding above. It does not bother about how far above. So an algorithm has infinite functions as its Big-O complexity. The most informative of them is the one that is immediately above, otherwise every algo is O(infinity).

现在，定义很清楚了，我们可以很容易地说合并排序是O(nLog(n))和O(n ² ).

Now with the definition being clear, we can easily say that Merge Sort is O(nLog(n)) as well as O(n²).

^† _{此解释中的触摸"一词等同于您在问题中写的计算次数".在算法运行期间，每次遇到数字-我们都说该数字已被触摸.因此，我们有效地对数字的接触进行计数，以确定算法的复杂性.}

这篇关于合并排序如何具有多个big-oh值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！