15

挿入と検索のためのトライ データ構造の最良/最悪/平均ケースの複雑さ (Big-O 表記法) はどれくらいですか?

挿入または検索される任意の文字列の長さは、O(K)すべての場合に当てはまると思います。K誰かがこれを確認しますか？

4

3 に答える 3

19

ウィキペディアとこのソースによると、トライの挿入と検索の最悪のケースの複雑さはO(M)、Mキーの長さです。挿入と検索の最良または平均的なケースの複雑さを説明している情報源を見つけることができません。ただし、 Big-O は複雑さの上限しか記述していないため、最良かつ平均的なケースの複雑さはキーの長さであるO(M)と言えます。M

于 2013-07-26T21:56:58.493 に答える
0

これに関する素晴らしい情報がウィクペディアにあります。http://en.wikipedia.org/wiki/Trie

于 2013-07-26T21:43:08.803 に答える