性能の定量化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:29 UTC 版)
「トライ (データ構造)」の記事における「性能の定量化」の解説
トライ木の探索時間は、キー文字列の長さが一定であれば O(1) とみなせるが、厳密には異なる。キーが N 個あるとき、文字の種類が k なら、最も長いキーは logkN 文字がその長さの下限となる。このことから、トライ木の探索時間は厳密には Ω(logN) であり、これは2分探索と同じである。 この結果は必ずしもトライ木の利点を否定するものではない。トライ木の高速性の利点は各ノードでの比較が高速である点にある。2分探索での一回の比較は比較対象の短いほうを m 文字としたとき O(m) が最悪時間となる。一方トライ木では各ノードでの比較は1文字の比較であるため、その時間は一定である。これは単に理論上の違いというわけではない。というのも2分探索木で末端に近いノードまで行くと常にプレフィックスが共通なノードで文字列比較を行うため、比較時間が長くなってしまうからである。
※この「性能の定量化」の解説は、「トライ (データ構造)」の解説の一部です。
「性能の定量化」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。
ウィキペディア小見出し辞書の「性能の定量化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 性能の定量化のページへのリンク
