ツリーに追加する2つのノードと、2つのニュースノードを追加するノードを提供するソースからツリーを作成しようとしています。このノードがツリー内のどこにあるかを知るために、私はO(n)を取るinorder traversalを使いました。したがって、ツリーにn個のノードを追加すると、ツリー全体の作成はO(n^2)になります。私の制約は、木を作るのにO(n)しかかからないということです。バイナリツリーを作成する時間の複雑さ
答えて
ツリーの典型的なO(log(n))
ではなく、各ノードへのアクセスがO(1)
になるように、HashMap [1]のツリーの各ノードへの参照を保持できます。 HashMapを使うと、ツリーのルートノードからそのノードを横断するのではなく、ノードに直接ジャンプすることができるので、O(n)
の時間にツリーを構築することが可能になります。
[1]鍵は、ノードを一意に識別するためにソースが使用するもので、私はそれを整数または文字列とみなしています。値は、ツリー内のノードへの参照になります。ツリーの実装では、すべてのノードをパブリックにする必要があるため、ツリーを自分で作成するか、適切なライブラリ(TreeMapなどのJDKのツリーは内部構造を非公開にして切断しない)を見つける必要があります。
これで問題は解決しますが、もう1つの質問があります。なぜなら、その時点でHashMapにデータを格納し、ツリー全体を捨てるだけではないからです。 – twain249
twain249:真。これが宿題であれば、私は樹木を使う本当の理由はないと思っています。 :)現実的な(しかしまれな)理由の1つは、システムが再起動後のファイル(つまりO(n)の起動時間)から状態を素早く復元する必要があり、通常の動作中にシステムが厳密な最悪ケースしたがって、ハッシュマップの償却されたO(1)は受け入れられませんが、ツリーの予測可能なO(log(n))が必要です)。 –
完全なハッシュ関数**または 'O(1)average'を与えられた** O(1)の償却時間は、この答えでもっと主に現れるはずです:-) –
バイナリツリー内のノードを検索すると、log(n)
(各レベルはそれより上のレベルの2倍の大きさ)のツリーがあるため、O(log(n))
です。したがって、n
要素をバイナリツリーに作成/挿入するには、O(nlog(n))
です。
バイナリ検索ツリー時間の複雑さは、要素がソートされずソートされていない場合はO(n^2)である場合はO(nlogn)になります。これは、BST O(n)時間内のソートされたリストに1つの要素を挿入するために、n個の要素O(n^2)に対して、平衡型またはほぼ平衡型のバイナリ検索ツリーの最大挿入時間をlognとすると、 n要素それはnlognです
- 1. バイナリツリーO(n)のInOrder Treeトラバーサルの時間複雑度?
- 2. fun()の時間の複雑さ?
- 3. 入力のエンコーディング(時間の複雑さ)
- 4. 時間の複雑さは、Python
- 5. 計算時間の複雑さ
- 6. random.sampleの時間複雑度
- 7. プログラムの時間複雑度
- 8. フィボナッチアルゴリズムの時間複雑度
- 9. アルゴリズムの時間複雑
- 10. Pythonセット操作の時間の複雑さ?
- 11. 時間複雑度を計算する
- 12. 時間の複雑さのためのアルゴリズムを分析する
- 13. ソートを計算する時間の複雑さ
- 14. 複雑な非バイナリツリーの生成方法は?
- 15. このコードの実行時間と空間の複雑さ
- 16. Javaで時間の複雑さが設定されている
- 17. 時間と空間の複雑さの場合(!areAllArrayElementsZero())
- 18. 時間/空間の複雑さの低減。プログラミングコンテスト
- 19. 変換ベクトルの時間の複雑さを減らす方法
- 20. 一般ツリーからバイナリツリーへの変換の複雑さ
- 21. このwhileループの時間複雑度
- 22. 以下のコードの時間複雑度
- 23. アルゴリズムのBigO時間の複雑度
- 24. キャニーエッジ検出器の時間複雑度
- 25. モジュラー算術の時間複雑度
- 26. erlang dictの時間複雑度
- 27. 分割アルゴリズム - 時間の複雑度
- 28. 遺伝的アルゴリズムの時間複雑度
- 29. python str.index時間の複雑度
- 30. アルファベータ検索時間の複雑度
私は本当に 'n(n log n)'より少ない数で2つのノードを次々に追加する方法を見ることができません。あなたの説明には何かがないようです。また、それは宿題なので、適切なタグを追加する必要があります。 – Voo
ツリー内の正しい場所を見つけるためにインオーダートラバーサルが必要なのはなぜですか?ノードは、O(log(n))の平均時間内に特定のノードを見つけることができるように配置する必要があります。あなたがそのような取り決めをすることができない場合、バイナリツリーはあなたのデータの正しい構造ではないかもしれません。 – Gigatron