トライを作るのにどれくらいの時間がかかりますか

Question

トライを検索する時間はO（N）（Nはパターンの長さ）と言う文献には多くの情報があります。

ただし、ツリーの構築にも時間がかかります。私には、合計でY文字のX単語があるとしましょう。

だから、O（Y）は時間です（各文字を挿入する必要があるため）。この評価は正しいですか（私は通常正しくありません）

Answer 1

間違っています。トライを作成し、トライを検索することは、2つの異なるアルゴリズムである。トライを作成せずに検索し、データ構造全体を破棄します。

Answer 2

それではO（Y）は

確かに（私たちは、それぞれの文字を挿入する必要があるため）、あなたはそれぞれの入力文字を処理する必要があり、既存のブランチに従うか、新しいの挿入のいずれかの時間でありますchar。

各入力文字を見る必要があるので、O（Y）より速くすることはできません。ソートや他の操作を行うと、処理が遅くなることはありません。