http://metabolomics.jp/mediawiki/index.php?action=history&feed=atom&title=Aritalab%3ALecture%2FAlgorithm%2FQuicksort
Aritalab:Lecture/Algorithm/Quicksort - Revision history
2026-04-09T02:18:22Z
Revision history for this page on the wiki
MediaWiki 1.19.1
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/Quicksort&diff=254236&oldid=prev
Adm at 08:04, 2 June 2011
2011-06-02T08:04:40Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 08:04, 2 June 2011</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>クイックソートのアルゴリズムは、[[Aritalab:Lecture/<del class="diffchange diffchange-inline">Basic</del>/Sorting|ソートのページ]]を参照してください。</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>クイックソートのアルゴリズムは、[[Aritalab:Lecture/<ins class="diffchange diffchange-inline">Algorithm</ins>/Sorting|ソートのページ]]を参照してください。</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==平均計算量==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==平均計算量==</div></td></tr>
</table>
Adm
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/Quicksort&diff=254235&oldid=prev
Adm: moved Aritalab:Lecture/Basic/Quicksort to Aritalab:Lecture/Algorithm/Quicksort
2011-06-01T15:29:04Z
<p>moved <a href="/mediawiki/index.php?title=Aritalab:Lecture/Basic/Quicksort&action=edit&redlink=1" class="new" title="Aritalab:Lecture/Basic/Quicksort (page does not exist)">Aritalab:Lecture/Basic/Quicksort</a> to <a href="/wiki/Aritalab:Lecture/Algorithm/Quicksort" title="Aritalab:Lecture/Algorithm/Quicksort">Aritalab:Lecture/Algorithm/Quicksort</a></p>
<table class='diff diff-contentalign-left'>
<tr valign='top'>
<td colspan='1' style="background-color: white; color:black;">← Older revision</td>
<td colspan='1' style="background-color: white; color:black;">Revision as of 15:29, 1 June 2011</td>
</tr></table>
Adm
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Algorithm/Quicksort&diff=254234&oldid=prev
Adm: New page: クイックソートのアルゴリズムは、ソートのページを参照してください。 ==平均計算量== ピボットをランダムに...
2010-10-20T01:41:21Z
<p>New page: クイックソートのアルゴリズムは、<a href="/mediawiki/index.php?title=Aritalab:Lecture/Basic/Sorting&action=edit&redlink=1" class="new" title="Aritalab:Lecture/Basic/Sorting (page does not exist)">ソートのページ</a>を参照してください。 ==平均計算量== ピボットをランダムに...</p>
<p><b>New page</b></p><div>クイックソートのアルゴリズムは、[[Aritalab:Lecture/Basic/Sorting|ソートのページ]]を参照してください。<br />
<br />
==平均計算量==<br />
ピボットをランダムに選ぶクイックソートの平均計算量は、2 n log<sub>e</sub> n = 1.4 n log<sub>2</sub> n といわれます。<br />
その値を導出しましょう。<br />
<br />
長さ n の配列をソートする手間数を C<sub>n</sub> と書くと、以下の漸化式を満たします。<br />
<br />
: C<sub>0</sub> = 0<br />
: C<sub>n</sub> = (n-1) + (2/n) <big>∑</big><sup>n-1</sup><sub>k=0</sub> C<sub>k</sub><br />
<br />
両辺を n 倍して、その式で n を (n-1) と置き換えたものを引き算すると<br />
: n C<sub>n</sub> - (n-1) C<sub>n-1</sub> = 2 (n-1) + 2 C<sub>n-2</sub> (n > 1)<br />
この式は n = 1 のとき C<sub>1</sub> = 0 となるので、n > 0 で成立します。<br />
つまり、漸化式は<br />
: C<sub>0</sub> = 0<br />
: n C<sub>n</sub> = (n + 1) C<sub>n-1</sub> + 2 (n-1)<br />
と書き直せます。<br />
和の因子として s<sub>n</sub> = 2 / n(n+1) を導入すると、[[Aritalab:Lecture/Basic/Reccurrence|漸化式の一般解]]を用いて解くことができ、<br />
: C<sub>n</sub> = 2(n+1) <big>∑</big><sup>n</sup><sub>k=1</sub> 1 /(k+1)<br />
となります。<br />
<br />
最後に、調和数 (Harmonic number) ''&Eta;''<sub>n</sub> = <big>∑</big><sup>n</sup><sub>k=1</sub> 1 / k を導入します。<br />
: <big>∑</big><sup>n</sup><sub>k=1</sub>1 /(k+1) = <big>∑</big><sup>n+1</sup><sub>k=2</sub> 1 / k<br />
:::: = -1 + 1/(n+1) + <big>∑</big><sup>n</sup><sub>k=1</sub>1 / k<br />
:::: = - n / (n+1) + ''&Eta;''<sub>n</sub><br />
<br />
調和数は ''&Eta;''<sub>n</sub> = log<sub>e</sub> n ですから、<br />
C<sub>n</sub> ≒ 2n log<sub>e</sub> n となります。</div>
Adm