问题描述
此问题是由竞争性考试门（看到-Q.no.-39 ），并且由门给出了接听键说：商标于所有（意味着要么超过一个或者没有选择是正确的）（的）。
我问这个问题之前，在stackexchange ，现在我也发现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）的。
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的答案相同的算法，这是正确的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！