algorithm - 后缀数组生成 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)).