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

Question

要在 n 个字符的字符串上构建后缀数组，

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))。