文字列の並べ替えはO（n^2logn）ですか？

Question

私は、次をお読みください。

ソートはO（NlogN）をとるので、O（N^2logN）であるか??。 2つの文字列の比較が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

Answer 1

はそれをこのように考えてみてください。

数字をソートするときに、大きい数字を検出するには、の1つの数字がである必要があります。

しかし、あなたは（helloとhellaを比較すなわち5charの比較を必要とする）は、文字列のすべての文字を比較する必要がある時期に、より大きなある文字列を検出するために、文字列をソートします。

したがって、すべての文字列の比較には、文字列の長さに正比例する時間がかかります。長さが（lを想定）、一致している場合、その複雑さはO(l*nlogn)

---

なるnとlの間で混乱しないでください。どのような時間複雑度でも、nは入力数を表します。あなたの場合、文字列の長さがnの場合にのみ、複雑さはO(n^2logn)になります。あなたは、コンテキストのうちその引用符を抽出O(l*nlogn)

Answer 2

そうでない場合は、lのように文字列の長さを取って、複雑さは次のようになります。何が起きているのかを理解するために、それを文脈に戻す価値があります。

文脈は、長さNの文字列Sから始まり、その文字列のすべての可能な接尾辞のセットをソートすることです。

文字位置ごとに1つずつ、N個の空でない空白の接尾辞があり、セット内の文字列の平均サイズは（N + 1）/ 2です（1からNまでのすべての長さが等しい可能性が高いためです）。

平均長さLの2つの文字列を比較するための予想コストがO（L）であり、N個のオブジェクトをソートするための予想比較数がO（N log N）であり、最後にLがN （N + 1）/ 2 × N × logN）これは、O（N logN）に簡略化するO（（N + 1）/ 2 × logN）であることがわかります。 。

しかし、長さLの2つの文字列を比較するための予想コストは、実際にはO（L）ではありません。一般に、2つの文字列の各文字の位置を比較する必要はありません。最初の不一致が見つかるまで、文字を見るだけで十分です。文字列が可能な文字列の中にランダムに分布している場合、検査される必要がある文字の予想数は、最悪の場合のコストはO（L）ですが、実際にはO（1）（単純な確率論的引数）です。

クイックソートの場合（少なくとも）、クイックソートの後のフェーズでの比較が互いに近い文字列間の傾向であるカウンタバランスがあります。この場合、検査される必要がある文字の数は、N個の文字列のソートされた一様分布のサンプル内の2つの連続する文字列の間の最も長い共通プレフィックスの予想される長さであるlog Nに近づく傾向がある。

ソートの実際の予想コストはO（Nlog N）である必要があります。 N.

を記録よりも小さいものに比較数の期待値を復元するに役立つかもしれない、さらに合併症として、各パーティションのLCPのを追跡するために、クイックソートアルゴリズムを変更することが可能である

、（同様の議論ができ引用文は、接尾辞木の問題に対してはるかに良いアルゴリズムを提供するように進んでいるが、並べ替え）