平均ケースBig Oとソートの影響

Question

Stringにすべての一意の文字が含まれているかどうかを判断する方法の実装には、時間の複雑さがあります。

基本、強引、アプローチが見文字のHashSetを維持する時にString 1文字を反復処理することです。反復の各文字について、Setに既にそれが含まれているかどうか確認し、そうであればfalseを返します。 String全体が検索された場合は、trueを返します。これは最悪の場合の複雑さとしてO(n)になります。平均的なケースは何でしょうか？ O(n/2)？

Stringをcharの配列にソートすることで最適化しようとすると、それは多かれ少なかれ効率的でしょうか？並べ替えは通常O(n log n)で、O(n)より悪くなりますが、ソートされたStringは、重複した文字をはるかに早く検出することができます（特に長い文字列の場合）。

最悪のケースはO(n^2 log n)ですが、平均的なケースが良いですか？もしそうなら、それは何ですか？

Answer 1

ソートされていないケースでは、平均ケースは文字列に完全に依存します。分配を知らない/仮定することなく、いかなる仮定もするのは難しい。

文字の一つが一度繰り返すランダムに配置された文字を含む文字列のための単純な場合、：

• 配置される反復文字の可能性の数はn*(n-1)/2
• であることがある確率検出される確率は、最大でkのステップである(k*(k-1))/(n*(n-1))であり、平均でそれを検出することを意味する（大の場合n）異なる周波数で発生する複数の文字については約0.7071*nで... [不完全]

、またはあなたは文字が文字列内でどのように分布しているか、あなたが異なる確率を得るでしょう上の異なる仮定を行います。

うまくいけば、誰かが私の答えを広げることができますように！ :)

文字列がソートされている場合、HashSetは必要ありません。

しかし、平均的なケースは文字列内の文字の分布に依然として依存します。つまり、2つのaaが表示されている場合はかなり効率的です。もしあなたが2つのzzを得たら、あなたは何も勝っていない。

最悪の場合は、と検出重複をソートするので、O(n log n + n)またはちょうどO(n log n)です。

したがって、複雑さが増したために、平均的な場合と最悪の場合の両方で、文字列をあらかじめ並べ替えることはあまり効果的ではないようです。