2

CLRSでは、配列内の i 番目に小さい要素を見つけるため(2/e, page 191, section 9.3)のアルゴリズムの分析は、次の帰納法証明で提示されます。SELECT

1.  T(n) <= c celing(n/5) + c(7n/10 + 6) + an
2.       <= cn/5 + c + 7cn/10 + 6c + an
3.       = 9cn/10 + 7c + an
4.       = cn + (-cn/10 + 7c + an)
5.       = cn,  when -cn/10 + 7c + an <= 0

アルゴリズムは理解できましたが、証明の 2 つの操作に少し戸惑いました。

質問 1 : 2 行目で、余分な c 項 (第 2 項) はどこから来ましたか? c 項を掛けると(7n/10 + 6)が得られ7cn/10 + 6cます。

質問 2 : 4 行目で、どうやって から9cn/10にたどり着きましたcn + (-cn/10 ...)か? 9 係数はどこに行ったのですか?

これは宿題ではありません

ありがとうございました！

4

2 に答える 2

0
  1. エクストラcは from c*celing(n/5) -conside n/5 = 10.2-thenc * ceiling(n/5) = 11c > cn/5なので、エクストラを追加する必要がありcます。
  2. 9cn/10 = (10-1)cn/10 = 10cn/10 - cn/10 = cn - cn/10 ... = cn + (-cn/10 ...)
于 2012-10-11T23:35:27.790 に答える