二分探索木を使用してn個の要素のリストをソートする次のアルゴリズムについて考えてみます。
initialise t to be an empty binary search tree
for each element x in the list,
add x to t
while t is not empty,
remove and print the smallest element of t
ツリーが以下を使用して実装されている場合、このアルゴリズムの最悪の場合の時間計算量はどれくらいですか。
a）通常の二分探索木？
b）AVLツリー？
私の解決策：解決策は、AVLツリーの場合はO（Log N）、BSTの場合はO（N）になると思います。
これらのツリーの挿入/削除の最悪のケースはO(n)、BSTとO(log(n))AVLの場合です。
リストの長さが長いn場合は、n挿入とn削除を行います。つまりO(n^2)、BSTO(nlog(n))とAVLを使用します。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加