Avl Treesでの時間を検索するには？

Question

AVLツリーを使用するアプリケーションの操作は、O（ログN）時間です。 10,000要素のコレクションを実行するには約50 ミリ秒かかる。 は、どのくらいの期間、100,000要素のコレクションを実行すると思いますか？

Answer 1

アプリケーションの一定の計算コスト（ローディング、前処理など）をすべて考慮する必要があるため、大きなコレクションで実行するのにかかる時間を簡単に推測することはできません。

ただし、log（10000）= 4、log（100000）= 5の上限があるため、すでに到達している場合は5/4 * 50 = 62.5 ms未満で実行することができます漸近的な振る舞い。

とにかく、O（log N）は非常に効率的な複雑さです。アルゴリズムは大きなインスタンスに非常に良く適合するはずです。 N個の要素を処理するために

Answer 2

、あなたは10000のための

T ~ C * N * log (N) 

おおよその時間を必要とする：

100000用

50 ms = C * 10^4 * log(10^4) = C * 4 * 10^4 * log(10) 
C = 50ms/(4 * 10^4 * log(10)) 

：

T ~ 50ms/(4 * 10^4 * log(10)) * 5 * 10^5 * log(10) 
T ~ 50ms * 5 * 10/4 = 625 ms 

だから、約625ミリ秒

時間を期待します