Tries、ハッシュ、Map（stl）、BSTに関するブログとチュートリアルを読みました。どちらをどこで使うのが良いのか、私は非常に混乱しています。それらはすべて実装に依存しているため、それらの間にそのような違いをもたらすことは意味がないことを私は知っています。より具体的に教えてください。複雑さ（最悪、平均、および最良の場合）についても忘れないでください。
前もって感謝します...
2373 次
1 に答える
6
BSTは二分探索木です。辞書に使用しています。BST は構造に制限がないため、検索/挿入/削除は O(n) 最悪のケースです。
Map [on stl] も辞書であり、実際には [on stl] の赤黒木です。これは特別な種類の BST であり、構造に制限があります。そのため、最悪の場合の検索/挿入/削除は O(logn) です。
ハッシュハッシュ テーブルは別の種類の辞書です。[優れたハッシュ関数を使用した] ハッシュ テーブルの利点は、検索/削除/挿入の平均時間が O(1) であることです。ただし、最悪のケースは O(n) です。これは、あまりにも多くの要素が衝突したり、再ハッシュが必要な場合に発生します [負荷バランスが高すぎる場合、より大きな配列を割り当て、すべての要素を再ハッシュします]。
試行は文字列にとって特別です。すべての演算は O(S) で、S は文字列の長さです。他の[文字列を扱う場合]の利点は、とにかく文字列を読み取る必要があるため、Mapたとえば文字列を扱う場合の複雑さは実際にはO(S*n*logn)です。
いつ使う？
[または他のMapバランスの取れたツリー] は、ほとんどの場合、通常の よりも優れた選択である必要がありますBST。
hash table平均的な短時間が必要な場合は良い選択ですが、再ハッシュによるパフォーマンスの低下や、場合によっては衝突が発生することを気にしないでください。
Trie通常、文字列の良い辞書です。
于 2011-08-17T07:54:35.173 に答える