排序字符串真的是 O(n^2logn) 吗？
Is it true that sorting strings is 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)。
如果有人能解释为什么是 O(N^2logN) 那就太好了。
编辑：引自此处：https://www.hackerrank.com/challenges/string-similarity/topics/suffix-array
这样想。
排序数字时，判断哪个数字大，只需要1次比较。
但是在对字符串进行排序时，为了检测哪个字符串更大，有时您需要比较字符串的所有字符（即比较 hello 和 hella 需要 5 char 比较）。
所以在那种情况下，每次字符串比较所花费的时间都与字符串的长度成正比。如果长度一致，（假设l），那么复杂度就会变成O(l*nlogn)
不要混淆 n 和 l。在任何时间复杂度中，n 都代表输入的数量。在您的情况下，只有当字符串的长度也为 n.
时，复杂性才会为 O(n^2logn)
否则，将字符串的长度设为l，复杂度为O(l*nlogn)
你断章取意地引用了这句话；值得将其放回上下文中以了解发生了什么。
上下文是我们从一些长度为 N 的字符串 S 开始，并希望对该字符串的所有可能后缀的集合进行排序。
有 N 个可能的非空后缀，每个字符位置一个，并且该集合中字符串的平均大小为 (N+1)/2（因为从 1 到 N 的每个长度都是等可能的。 )
如果我们假设比较两个平均长度为 L 的字符串的预期成本是 O(L)，并且对 N 个对象进行排序的预期比较次数是 O(N log N)，最后由于 L 是 ( N+1)/2，我们可以看到比较排序 这组特定的字符串 的预期时间是 O((N+1)/2×N×logN) 这简化了到 O(N2logN).
但是比较两个长度为 L 的字符串的预期成本实际上并不是 O(L)，因为通常情况下不需要查看两个字符串中的每个字符位置来比较它们。在找到第一个不匹配之前查看字符就足够了。如果字符串随机分布在可能字符串的范围内，那么需要检查的预期字符数实际上是 O(1)（通过简单的概率论证），尽管最坏情况的成本是 O(L)。
在快速排序的情况下（至少），存在一种平衡，即在快速排序的后期阶段比较更接近的字符串之间的趋势。在这种情况下，需要检查的字符数趋于接近log N，这是N个字符串的排序均匀分布样本中两个连续字符串之间最长公共前缀的预期长度。
所以排序的实际期望成本应该是O(Nlog2N).
更复杂的是，可以修改快速排序算法以跟踪每个分区的 LCP，这可能有助于将预期的比较次数恢复到小于 log N 的值。
（类似的论点可以应用于基数排序，它也从预期的——但不是最坏的情况——时间中消除了明显的 O(L) 项。引用的文章继续提供更好的算法对于后缀树问题，它避免了比较排序。）
我阅读了以下内容：
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)。
如果有人能解释为什么是 O(N^2logN) 那就太好了。
编辑：引自此处：https://www.hackerrank.com/challenges/string-similarity/topics/suffix-array
这样想。
排序数字时，判断哪个数字大，只需要1次比较。
但是在对字符串进行排序时，为了检测哪个字符串更大，有时您需要比较字符串的所有字符（即比较 hello 和 hella 需要 5 char 比较）。
所以在那种情况下，每次字符串比较所花费的时间都与字符串的长度成正比。如果长度一致，（假设l），那么复杂度就会变成O(l*nlogn)
不要混淆 n 和 l。在任何时间复杂度中，n 都代表输入的数量。在您的情况下，只有当字符串的长度也为 n.
O(n^2logn)
否则，将字符串的长度设为l，复杂度为O(l*nlogn)
你断章取意地引用了这句话；值得将其放回上下文中以了解发生了什么。
上下文是我们从一些长度为 N 的字符串 S 开始，并希望对该字符串的所有可能后缀的集合进行排序。
有 N 个可能的非空后缀，每个字符位置一个，并且该集合中字符串的平均大小为 (N+1)/2（因为从 1 到 N 的每个长度都是等可能的。 )
如果我们假设比较两个平均长度为 L 的字符串的预期成本是 O(L)，并且对 N 个对象进行排序的预期比较次数是 O(N log N)，最后由于 L 是 ( N+1)/2，我们可以看到比较排序 这组特定的字符串 的预期时间是 O((N+1)/2×N×logN) 这简化了到 O(N2logN).
但是比较两个长度为 L 的字符串的预期成本实际上并不是 O(L)，因为通常情况下不需要查看两个字符串中的每个字符位置来比较它们。在找到第一个不匹配之前查看字符就足够了。如果字符串随机分布在可能字符串的范围内，那么需要检查的预期字符数实际上是 O(1)（通过简单的概率论证），尽管最坏情况的成本是 O(L)。
在快速排序的情况下（至少），存在一种平衡，即在快速排序的后期阶段比较更接近的字符串之间的趋势。在这种情况下，需要检查的字符数趋于接近log N，这是N个字符串的排序均匀分布样本中两个连续字符串之间最长公共前缀的预期长度。
所以排序的实际期望成本应该是O(Nlog2N).
更复杂的是，可以修改快速排序算法以跟踪每个分区的 LCP，这可能有助于将预期的比较次数恢复到小于 log N 的值。
（类似的论点可以应用于基数排序，它也从预期的——但不是最坏的情况——时间中消除了明显的 O(L) 项。引用的文章继续提供更好的算法对于后缀树问题，它避免了比较排序。）