c - 空のツリーから始めて、big-O 記法で Red Black Tree に挿入する複雑さは何ですか?

Question

10 個の要素があり、空のツリーから開始する場合、Big-O 記法で赤黒に 10 個の要素を挿入する複雑さは何ですか?

要素を挿入するたびに、要素の適切な場所を検索し、祖先ノードと子ノードの間で一連のローテーションを実行する必要があるため、O(log 10) を超えることはありません。N 個の要素があり、Red Black Tree に N 回挿入すると、O(n log n) になりませんか?

助けてくれてありがとう。

Answer 1

O(10) は O(1) または O(128291) とまったく同じ意味であるため、定数 (1 を除く) で big-O を使用することはありません。慣例により、常に O(1) を使用します!

それでは、最初は空の RB ツリーに K 個のアイテムを挿入することの大きな問題を見てみましょう。最初の挿入は一定時間なので、O(1) と呼びます。X 個の項目がある場合に挿入すると、X+1 番目は O(log(X)) になります (各ステップを下にローテーションする必要がある場合でも、最悪の場合は log(X) に比例するため、O(log(X)) )、「レイヤー」または「レベル」の数は、X に対して対数的にのみ増加するためです。K レベルの RB ツリーには、2 の K 乗として増加するノードの数があるためです)。

したがって、2 から N までの X の log(X) の総和 (およびコスタント) が必要です。これはたまたま N の階乗の対数に等しくなります。スターリングの approxによると、それは約 N log(N) - N です。ビッグオーの用語で言えば、これは再び N log(N) になります。

Answer 2

@Justice と @Alex が実際に得ているのは、O(f(N))N が無限大になる傾向があるため、複雑さの尺度が制限動作 (実行時間、比較の数など) について話しているということです。

ON を特定の値に置き換えると、用語の意味がなくなると彼らは言っています。

彼らがしなかった別の点があります。つまりO(...)、N が小さい場合に何が起こるかを示すために、表記法でステートメントを使用することはできません。定義上、"big O" 表記は、その場合に何が起こるかについて何も教えてくれません。

これは衒学だけではありません。たとえば、コスト関数F(N) = 1,000,000 * N + N**2は ですO(N**2)が、1,000 未満の N の値では最初の項が支配的です。この場合、測定値を推定量として使用しようとするO(N**2)と、完全に間違った答えが得られます。

Answer 3

O(log n)単一の要素を RB ツリーに挿入する時間の複雑さnは、ツリーの現在のサイズです。

nしたがって、要素を空の RB ツリーに挿入する時間の複雑さはですO(n log n)。

10要素を空の RB ツリーに挿入する時間の複雑さは定数、つまりO(1)です。ツリーは空で始まり、挿入される要素の数が固定されているため、ここには可変要素はありません。