3
CLRSでは、155ページのmax-heapについて、max-heapifyの実行時間はT(n) = T(2n/3) + O(1)と記述されています。CLRSは、max-heapifyの実行時間が `T（n）= T（2n/3）+ O（1）`の繰り返しで記述されると完全に正確ですか？
私は、ノードの最も深いレベルが半分であるほぼ完全なバイナリツリー（常にヒープの場合）を持つ場合、最初の再帰呼び出しがサイズのサブ問題にある理由を理解しています最も深いレベルでこれらのノードを含むサブツリーのルートである子を再帰する）。詳細な説明はhereです。
私が理解していないのは、最初の再帰呼び出しの後、サブツリーが完全なバイナリツリーになり、次の再帰呼び出しはサイズn/2の問題になります。
したがって、max-heapifyの実行時間は、再帰T(n) = T(2n/3) + O(1)によって記述されていると正確に述べていますか？
CLRSのコピーは私にはありませんが、おそらくT（n）≤ T（2n/3）+ O（1）と言っていましたか？ T（n）が単調であると仮定すると、控えめな上限が得られる。 – templatetypedef
はい、私は@templatetypedefに意味があります。いずれかの方法で再帰を解くと、O（n）の実行時間が与えられます。 – evianpring
@ジム・ミッシェル（Jim Mischel）重複すると思われる質問は全く同じ質問ではありません。私が言ったことは、私の質問の一部分の説明です。問題は、その最初の計算（最初の再帰呼び出しの場合、その重複した質問で説明されている）の後、再帰呼び出しのサブツリーが完全なツリー（半分ではない）になって以来、その計算はもう適用できません。 – evianpring