HOME»応用情報技術者試験掲示板»平成20年秋午後1問5 設問5
投稿する

平成20年秋午後1問5 設問5 [0617]

 野獣さん(No.1) 
設問5の②について質問です。

降順にソートされている場合のheap_make(A)の計算量がO(N)となっています。
しかし、どの部分木をとってもヒープ条件を満たしており、heap_correct()が再帰的に呼び出されることはありません。ゆえに、計算量はheap_correctが呼び出される回数のO(2/N)だと思うのですがどうですか?

計算量がO(N)だとしたら、すべてのノードに対してheap(correct)を適用していることになると思います。
2016.10.03 20:30

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop