最近、祖先について聞いたことがありますが、その実装を試みることに決めましたが、検索操作の複雑さを悩ますものがあります。私はなぜそんなに早くなるはずなのか、私は立証できません。nedtrieでの検索操作の複雑さ(ビット単位のトライ)
私が理解したところでは、検索操作の複雑さは O(m/2)でなければなりません。 あなたが得る 、伝統的なバイナリツリー内の検索操作の複雑さと比較した場合: LOG2(N)> = M/2
レッツは、キーは32ビットの長さである:LOG2(N)> = 16 < => n> = 65536
したがって、nedtriesは、65536個のアイテムから始まるバイナリツリーよりも速くなければなりません。 しかし、著者はバイナリツリーよりも常に高速であると主張しているので、私の前提である の複雑さや、検索の各ステップで実行される計算がnedtrieで非常に高速です。
だから、どうですか?
シンプルで効率的です。完璧な答え。 – fokenrute