mzp https://blog.hatena.ne.jp/mzp/ みずぴー日記 https://mzp.hatenadiary.org/ 院試 ソフトウェア http://www.is.nagoya-u.ac.jp/exam-old/d20608.pdf [1]クイックソート (1)実行時間のオーダー/最悪な場合 最悪な場合は、すでに対象となる配列が整列されている場合、だというのは有名。この場合、一回につき対象となる配列が1回短くなるだけ。なので、必要な比較回数は よって、 また、これが起こるのはp(ピボッド)が、最小または最大の要素だった場合。 (1)実行時間のオーダー/最善の場合(best case) 最善の場合は、配列の長さが1/2づつになっていく。 なので、必要な比較回数は、 という漸化式で表せる。nは分割するときに各要素を調べるので必要。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmzp.hatenadiary.org%2Fentry%2F20070626%2Fsoft" title="平成19年度 - みずぴー日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2007-06-26 00:00:00 rich https://mzp.hatenadiary.org/entry/20070626/soft 1.0 100%