后缀数组生成O(n ^ 2 log n)的成本如何？

Question

要在n个字符的字符串上构建一个suffis数组,

1. 我们首先生成n个后缀O(n)
2. 然后对它们进行排序O(n log n)

总时间复杂度显示为O(n)+ O(nlogn)= O(nlogn).

但我正在读它是O(n ^ 2 log n)并且无法理解如何.有人可以解释一下吗？

Answer 1

首先,声明O(n) + O(nlogn) = O(n)是错误的.O(n) + O(nlogn) = O(nlog(n)).

第二,你感到困惑的原因 - 比较两个后缀并不是一成不变的.由于每个后缀是长度最多为n的字符串,因此两个后缀的比较顺序为O(n).因此,排序n个后缀的顺序为O(n * log (n) * n) = O(n^2 * log(n)).