ヒープをヒープ化する時間の複雑さは何ですか

Question

ヒープ化の式は、ヒープ化の式が T（n）≦T（2n/3）+Θ（1）であることを示しています。 しかし、それは 「マスター定理のケース2によって、T（n）= O（lg n）であるので、Heapifyは対数時間をとる」と述べている。私は本当にそれを得ていない、a、b、c、dの値は何ですか？なぜこのケースは定理の2番目のケースに属し、その結果はO（lg n）ですか？マスター定理はここ

Answer 1

ある

THX

は検討し、T（n）がAT =（N/B）+ N^Cは、n> 1

ための3つのケース（音符がありますそのb）は

あなたが

0123を持っているあなたの場合

(1) if logb a < c, T(n)=Θ(n^c), 

(2) if logb a = c, T (n) = Θ(n^c log n), 

(3) if logb a > c, T(n) = Θ(n^(logb a)). 

ログベースであります

我々は我々が簡単に

log3/2 1 = 0 

は、このように、我々はケース2

logb a = c 

を使用する必要があることを確認することをベリティことができ、そう

、

a = 1, b = 3/2, and c = 0 

を

n^0 here because Θ(1) = Θ(n^0) 

を言うことができます

それで、あなたは

投稿画像を見てみると

T(n) = Θ(n^c log n) = Θ(n^0 log n) = Θ(log n) 

は、ケース2

を守っそれは

Θ(n log n) if d = b 

は一般的に、それは、

であることを述べています

Θ(n^i log n) if d = b^i 

d = b^i implies logb d = i 

しかし、（たぶん）だから

D = 1およびb = 3/2（及び上記のように）は、i = 0

を明確にするために、

D = B^iがありますtrue

ここで別の文字を使用しましたが、これは上記の方法と同じです。私は同じ事を二度、あなたのために物事をクリアするためにあなたのポストの手紙を使っていた。どのように見たいかにかかわらず、ケース2を使用します。