排序字符串是O(n ^ 2logn)是真的吗？

我读了以下内容:

排序需要O(NlogN),所以它是如何O(N ^ 2logN)??.我们在这里想念的是两个字符串的比较不是O(1); 在最坏的情况下,需要O(N).所以最终的复杂性是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都代表输入的数量.在您的情况下,复杂性O(n^2logn)仅在字符串的长度也是如此n.

否则,将字符串的长度视为l复杂性O(l*nlogn)