不同的-2的答案相同的算法，这是正确的？ [英] Different-2 answers for same algorithm , which is correct one?

问题描述

  

N个字符串列表，每个长度为n，则整理成词典   订购使用合并排序算法。运行时间的最坏情况   这种计算是__________。

     

选项有：

     

  
1. 为O（n log n）的
  
2. 为O（n ^ 2 log n）的
  
3. 为O（n ^ 2 + log n）的
  
4. 为O（n ^ 2）
  

---

此问题是由竞争性考试门（看到-Q.no.-39 ），并且由门给出了接听键说：商标于所有（意味着要么超过一个或者没有选择是正确的）（的看-设置AQ.no.-39 ）。

---

我问这个问题之前，在<一个href="http://cs.stackexchange.com/questions/47771/worst-case-time-complexity-please-check-whether-my-solution-is-correct">stackexchange ，现在我也发现<一这个问题href="http://stackoverflow.com/questions/9276163/merge-sort-worst-case-running-time-for-lexicographic-sorting">stackoverflow ，我很满意与@汤姆范德Zanden先生给出的解释。

---

我要问，这解释是正确的？因为两者是相同的这个问题，不同的

解决方案

有关L，一组字符串，和M，字符串中的字符集。

在最坏的情况下比较两个字符串的复杂性是 O（| M |），这意味着你要比较的字符串的每一个字符，以确定哪一个是不同，如果有的话。

现在，如果我们考虑的第一个复杂度为 O（1）中，与归并排序为排序的所有字符串的复杂度为O （| L |登录| L |）。对于这一点，你可以参考的合并排序这是有据可查的最糟糕的情况的复杂性。

通过替代，你最终用的复杂性：

O（| M |） * O（| L |登录| L |） = O（| M | * | L | *登录| L |） => O（N * N * log n）的。

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is __________.

Options are :

1. O(n log n)
2. O(n^2 log n)
3. O(n^2 +log n)
4. O(n^2)

---

This question is from competitive exam GATE (see-Q.no.-39) , and the answer key given by GATE says "Marks to all(means either more than one or none option is correct)" (see-set-A-Q.no.-39) .

---

I asked this question before on stackexchange ,Now I also found this question on stackoverflow , I was satisfied with the explanation given by @Tom van der Zanden sir.

---

I'm asking ,which explanation is correct one? since both are different for same this question

解决方案

For L, a set of strings, and M, a set of characters in a string.

The complexity of comparing 2 strings in the worst case is O(|M|), which means you have to compare every characters of the string to determine which one is different, if any.

Now, if we consider the first complexity to be O(1), the complexity of sorting all the strings with the Merge Sort is O(|L| log |L|). For that, you can refer to the worst case complexity of the Merge Sort which is well documented.

By substitution, you end with a complexity of:

O(|M|) * O(|L| log |L|) = O(|M|*|L| * log |L|) => O(n*n * log n).

这篇关于不同的-2的答案相同的算法，这是正确的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！