我读了以下内容：
排序需要 O(NlogN) 那么它怎么是 O(N^2logN)??。我们在这里想念的是
两个字符串的比较不是 O(1)；在最坏的情况下，需要
在）。所以最终的复杂度是O(N^2logN)。
它是否正确？我一直认为排序总是 O(NlogN) 但现在我感觉有点不对劲，因为它变成了 O(N^2logN)。
如果有人能解释为什么它是 O(N^2logN) 那就太好了。
编辑：引用自这里：https://www.hackerrank.com/challenges/string-similarity/topics/suffix-array https://www.hackerrank.com/challenges/string-similarity/topics/suffix-array
这样想吧。
当你对数字进行排序时，要检测哪个数字更大，你只需要1 比较.
但是在对字符串进行排序时，要检测哪个字符串更大，有时需要比较字符串的所有字符（即比较hello and hella需要5 char比较）。
因此在这种情况下，每次字符串比较所花费的时间与字符串的长度成正比。如果长度一致，（假设l），那么复杂度就会变成O(l*nlogn)
不要混淆n and l。在任意时间复杂度下，n代表输入的数量。在你的情况下，复杂性将是O(n^2logn)仅当字符串的长度也为n.
否则，将字符串的长度视为l，复杂度为O(l*nlogn)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
