tree - Big Oの質問：一般的なツリー操作と相対的な複雑さ

Question

これは実際には宿題ではありませんが、クラスでこれらの概念を理解する必要があります。

一般的なツリーでの挿入、検索、および削除操作の最悪の場合のBig-Oパフォーマンスはどれくらいですか？なんでそうなの？

一般的な樹木にはくびれがないので、どうやってアプローチすればいいのかわかりません。

O（n ^ 2 * log（n））またはO（n ^ 1.01）のどちらが速く成長するか

Answer 1

O（n ^{2 log n ）は、O（n 1.01} ）よりもはるかに速く成長します。多くのツリーアルゴリズムの場合と同様に、対数の底は2であると想定しています。

たとえば、n=1024の場合を考えてみます。

n ^{2 log n} = 1024 ^{2 * log 1024} = 1024 ²⁰ =1606938044258990275541962092341162602522202993782792835301376。

一方、n ^1.01 = 1024 ^1.01 = 1097.5