T（n）= 2T（n / 4）+1のようなケースがあるとします。f（n）= 1 a=2およびb=4。したがって、n ^（1/2）>1です。これはケース1である必要があります。ただし、ケース1にはラムダもあるため、ラムダ> 0の場合はf（n）= O（n ^（（1/2）-lambda））になります。この場合、ラムダは1/2になりますか？
1627 次
1 に答える
2
それは正解です。この場合、a=2およびb=4であることに注意してください。この場合の関数f（n）は1であり、いくつかのε>に対して1 =Θ（n1 / 2-ε ）であることに注意してください。 0、この場合はε=1/2です。したがって、マスター定理により、T（n）=Θ（n1 / 2）が得られます。
このεのポイントは、レベルごとに実行される作業量が十分に少ない場合（log b a未満）、作業はレベルごとの作業ではなく、主に分割によって支配されるということです。指数からε>0を引くことができるという事実は、レベルごとの作業が分割率よりも厳密に漸近的に遅くなる必要があり、ある程度の多項式量だけ増加する必要があることを示しています。
お役に立てれば！
于 2012-02-01T05:53:30.450 に答える