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

第二に、あなたが混乱する理由 - 2 つの接尾辞の比較は一定ではありません。各接尾辞は n までの長さの文字列であるため、2 つの接尾辞の比較は の順序で行われO(n)ます。したがって、n 個の接尾辞を並べ替えると、 の順序になりO(n * log (n) * n) = O(n^2 * log(n))ます。