これは宿題ではありません。私はデータ構造のクラスを受講しており、最近ツリーを完成させました。授業の終わりに、私の教授はこの画像を見せました。
ConcreteBTree は自己バランスをとらない二分木です。これらの手順を完了するのにかかった時間についていくつか質問があります。
ConcreteBTree に 100,000 個の連続要素を挿入するのに、ランダムな要素を挿入するよりもはるかに時間がかかるのはなぜですか? 私の直感では、要素は連続しているため、1,000,000 個のランダムな要素を挿入するよりも時間がかからないはずです。
ランダムな要素を持つ ConcreteBTree の insert() と find() の時間が非常に近いのはなぜですか? 両方の時間の複雑さが同じだからですか？insert は O(1) で find は O(n) だと思った
ここで何が起こっているのかを本当に理解したいのですが、どんな説明でも大歓迎です。ありがとう
Armin が Q1 に回答しました。
2.ランダムな要素を持つ ConcreteBTree の insert() と find() の時間はなぜそんなに近いのですか? 両方の時間の複雑さが同じだからですか？insert は O(1) で find は O(n) だと思った
insert同じ作業を行う必要がありfindます-値がリンクされているか、値がリンクされている最後のノードを探して、まとめた奇妙なツリーをたどります（の場合はinsertそうなります）。したがって、同じことを行います比較とノードトラバーサルの数、同様の時間がかかります。
平衡木へのランダム要素の挿入は O(log 2 N) です。自己再調整を行わないツリーへのランダムな値の挿入は少し悪くなりますが、一部のブランチが他のブランチよりもかなり長くなるため、劇的に悪化することはありません。おそらく、ブランチの長さのある種のベル カーブが得られるでしょう。 insert挿入が行われるツリー内のノードがすでにわかっている場合 (つまり、上記の検索ステップが通常必要な場合) は O(1) のみです。 findの唯一の O(n) は、ツリー内のすべてのノードを訪問する必要がある場合です。これは、病理学的にバランスの取れていないツリーの場合にのみ当てはまり、効果的にリンクされたリストを形成します。要素。