排序字符串是否为O(n ^ 2logn)是真的吗? [英] Is it true that sorting strings is O(n^2logn)?

问题描述

我阅读以下内容:

排序需要O(NlogN)，所以它是O(N ^ 2logN)??.我们在这里想念的是 两个字符串的比较不是O(1)；最坏的情况是 在).因此最终的复杂度为O(N ^ 2logN).

Sorting takes O(NlogN) so how it is O(N^2logN)??. What we miss here is that comparison of two strings is not O(1); in worst case, it takes O(N). So the final complexity is O(N^2logN).

这是正确的吗?我一直以为排序总是O(NlogN)，但是现在我觉得有点不对劲，因为它已经变成O(N ^ 2logN).

Is this correct? I had always assumed that sorting was always O(NlogN) but now I feel a little thrown off because it has become O(N^2logN).

如果有人可以解释为什么O(N ^ 2logN)会很棒.

If someone could explain why it's O(N^2logN) that would be great.

引用来自此处: https://www.hackerrank .com/challenges/string-likeity/topics/suffix-array

推荐答案

以这种方式思考.

对数字进行排序时，要检测哪个数字更大，只需要 1个比较.

When you are sorting numbers, to detect which number is bigger, you need only 1 comparison.

但是在对字符串进行排序时，要检测哪个字符串更大，有时您需要比较字符串的所有字符(即，比较hello和hella将需要进行5 char比较).

But when sorting strings, to detect which string is bigger, at times you need to compare all the characters of the string (i.e comparing hello and hella would need 5 char comparisons).

因此，在这种情况下，每个字符串比较将花费与字符串长度成正比的时间.如果长度是一致的(假设l)，那么复杂度将变为O(l*nlogn)

So in that case, every string comparison would take time that is directly proportional to the length of the strings. If the length is consistent, (suppose l), then the complexity would become O(l*nlogn)

不要混淆n和l.在任何时间复杂度中，n代表输入的数量.在您的情况下，仅当字符串的长度也为n时，复杂度才会为O(n^2logn).

Do not get confused between n and l. In any time complexity, n would stand for the number of inputs. In your case, complexity will be O(n^2logn) only when the length of the strings are also n.

否则，将字符串的长度设为l，则复杂度将为O(l*nlogn)

Otherwise, taking the length of the strings as l, complexity would be O(l*nlogn)

这篇关于排序字符串是否为O(n ^ 2logn)是真的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！