Javaでスプレイツリー操作の複雑さをチェック

Question

私はJavaでスプレイツリー（挿入、検索、削除操作）を実装しました。アルゴリズムの複雑さがO（logn）かどうかを確認したいと思います。入力値（ノード数）を変更し、実行時間を秒単位でチェックすることでこれを確認する方法はありますか？ 1000,100000のような入力値を入れ、実行時間をチェックするか、他の方法がありますか？

Answer 1

厳密に言えば、nのいくつかの値に対してアルゴリズムを実行すると、アルゴリズムの複雑さがわかりません。値n_1, n_2, ..., n_kを実行したとします。アルゴリズムはnのいずれか大きい値のための任意のn <= max(n_1, ..., n_k)と正確10^100操作のためのn^2操作を行った場合、それはあなたが持っているポイントから次のようになりますにもかかわらず、一定の時間複雑性を有します。

しかし、サイズnの入力で完了するのに必要な操作の数を評価することができます（後者は厳密な正式な定義があるので、ここでは時間の複雑さと呼んでいません） nであり、比率は、T(n1)/T(n2)とn1/n2です。しかし、実際のアルゴリズム（たとえそれが最初の段落で説明された病理学的なケースではないという意味で）であっても、入力の "構造"に注意する必要があります（例えば、ピボットとして最初の要素は、ランダムな入力のための平均O(n log n)で実行されるので、あなたは、異なるサイズのランダムな配列を生成する場合には、O(n log n)ようになります。しかし、それは逆にソートされた配列のためのO(n^2)時間）で実行されます。

実際の視点からは十分に速いのか、アルゴリズムの一般的な入力がどのように見えるかを知る必要がある場合は、さまざまなサイズの入力を試してみると実行時間がどのように伸びるか。あなたは数学的な意味での実行時にバインドする必要がある場合

はしかし、あなたが数学的に自分のアルゴリズムのいくつかのプロパティと境界を証明する必要があります。

あなたの場合、私はランダムな入力をテストすることは合理的なアイデアであると言います（1つの操作の時間複雑さがスプレイツリーの場合はO(log n)であるという数学的証明があるので）。あなたが実装したツリーは確かに正しいスプレイツリーです。 1つの注意：入力が「ランダム」である限り、バランスのとれていないツリーでもかなり高速に動作できるため、さまざまなパターンのクエリ（並べ替え/逆順で要素を挿入するなど）を試すことをおすすめします。