問題タブ [master-theorem]

この疑似コードを調べて、マスター定理で使用されている c/d 定数をどのように見つけますか?

ランダム化されたクイック ソートの場合、少なくとも 25% から 75% の割合で分割されるようにピボットを選択すると、実行時間はO(n log n). また、これをマスター定理で証明できることも知りました。

しかし、私の問題は、各ステップで配列を 25% から 75% に分割した場合、どのように定義し、T(n)どのようにランタイム分析を証明できるかということO(n log n)です。

以下の再帰関係をどのように解決しますか?

できればマスター定理によって、それ以外の場合は任意の方法で。マスター定理が失敗することは知っていますが、この種の問題の拡張機能はありますか? 上記のような複雑な関係を解決するための何かを教えてもらえますか?

私はデータ構造とアルゴリズムのコースを受講していますが、次の再帰方程式に行き詰まっています。

明らかに、これはマスター定理を使用して処理することはできないので、誰かがこの再帰方程式を解くためのアイデアを持っているかどうか疑問に思っていました. n を 2^m と見なすなど、パラメーターを変更して解決する必要があると確信していますが、適切な修正を見つけることができませんでした。

マスター定理を使用して、この種の再発を解決するにはどうすればよいでしょうか?

T(n) = 4T(n/2) + n ² + logn

これを行う方法はわかりませんが、マスター定理を使用して解決できると確信しています。用語の 1 つを無視する必要がありますか? どんな助けでも大歓迎です、ありがとう。