0

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

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

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

4

2 に答える 2

1

したがって、O(Y) は時間です (各文字を挿入する必要があるため)

確かに、各入力文字を処理し、既存の分岐に従うか、新しい文字を挿入する必要があります。

各入力文字を確認する必要があるため、O(Y) よりも高速になることはありません。並べ替えや、速度を低下させる可能性のあるその他の操作はありません。

于 2011-01-29T10:23:21.740 に答える
-1

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

于 2011-01-13T04:43:41.377 に答える