0
私は、次の質問から2N/3を取得する方法を考え出した：Max-Heapifyのワーストケース - なぜ2n/3を得ることができますか？
Worst case in Max-Heapify - How do you get 2n/3?
「CLRS、第3版、155ページ、それはそのMAX-HEAPIFYに与えられている：
「子どものサブツリーのサイズは2n/3以下です。最悪の場合は、ツリーの最下位レベルが完全に半分になったときに発生します」。
しかし、ツリーの最下位レベルがちょうど半分フル、 を取得します。
我々は、事前に想定しているので、T（n）が< = T（2N/3）+シータ（1）
は、そのサブツリーの次の再帰呼び出しに、このサブツリーの下レベルは、（すべて満杯です上記の再発を得るために、もう一方の側は空であるが、この側はできるだけいっぱいである）。したがって、次の呼び出しに再発は次のようになります。
T（n）が< = T（N/2）+シータ（1）
毎再帰呼び出し以後同じです。
実際に再発が変わり、どのようにマスター定理を使用できますか？
しかし、a = 1、f（n）= n^0なので、bが何であれ、最悪の場合の実行時間は常にO（lgn）になるので、なぜわからないのですか？何bですか？
おかげ