<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />

    <title>アルゴリズム計算量入門　〜　② - イノベーション　エンジニアブログ</title>

    <meta name="HandheldFriendly" content="True">
    <meta name="MobileOptimized" content="320">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

    <meta name="description" content="">

    <meta name="twitter:card" content="summary">
    <meta name="twitter:title" content="アルゴリズム計算量入門　〜　②">
    <meta name="twitter:description" content="">

    <meta property="og:type" content="article">
    <meta property="og:title" content="アルゴリズム計算量入門　〜　②">
    <meta property="og:description" content="">

    <link href="/favicon.ico" rel="shortcut icon" type="image/x-icon">
    <link href="/apple-touch-icon-precomposed.png" rel="apple-touch-icon">
    
<script type="text/javascript">
var _trackingid = 'LFT-10003-1';

(function() {
  var lft = document.createElement('script'); lft.type = 'text/javascript'; lft.async = true;
  lft.src = document.location.protocol + '//test.list-finder.jp/js/ja/track_test.js';
  var snode = document.getElementsByTagName('script')[0]; snode.parentNode.insertBefore(lft, snode);
})();
</script>

<script type="text/javascript">
var _trackingid = 'LFT-10003-1';

(function() {
  var lft = document.createElement('script'); lft.type = 'text/javascript'; lft.async = true;
  lft.src = document.location.protocol + '//track.list-finder.jp/js/ja/track_prod_wao.js';
  var snode = document.getElementsByTagName('script')[0]; snode.parentNode.insertBefore(lft, snode);
})();
</script>

    <link rel="stylesheet" type="text/css" href="//tech.innovation.co.jp/themes/uno/assets/css/uno.css?v=1.0.0" />

    <link rel="canonical" href="http://tech.innovation.co.jp/2018/06/25/Introduction-of-Computational-Complexity-2.html" />
    
    <meta property="og:site_name" content="イノベーション　エンジニアブログ" />
    <meta property="og:type" content="article" />
    <meta property="og:title" content="アルゴリズム計算量入門　〜　②" />
    <meta property="og:description" content="どうも、bigenです。 なぜ２本連続で書いているかというと、先週のブログ当番をブッチしてしまった罰ゲームです！ そんなわけで、 前回の記事に引き続き、ソートアルゴリズムの計算量について見ていこうと思います。  【前回の記事のまとめ】  バブルソート： 時間計算量 O(n2), 空間計算量O(n)  バケツソート： 時間計算量 O(m + n), 空間計算量O(m + n)  マージソート： 時間計算量 O(n log n), 空間計算量O(n)  【まとめおわり】  今回は、実際にphpでそれぞれのアルゴリズムを動かして、「計算量本当にそれであってん..." />
    <meta property="og:url" content="http://tech.innovation.co.jp/2018/06/25/Introduction-of-Computational-Complexity-2.html" />
    <meta property="article:published_time" content="2018-06-24T15:00:00.000Z" />
    <meta property="article:modified_time" content="2018-07-25T20:24:35.348Z" />
    <meta property="article:tag" content="Complexity" />
    <meta property="article:tag" content="Sort Algorithm" />
    <meta property="article:tag" content="bigen" />
    
    <meta name="twitter:card" content="summary" />
    <meta name="twitter:title" content="アルゴリズム計算量入門　〜　②" />
    <meta name="twitter:description" content="どうも、bigenです。 なぜ２本連続で書いているかというと、先週のブログ当番をブッチしてしまった罰ゲームです！ そんなわけで、 前回の記事に引き続き、ソートアルゴリズムの計算量について見ていこうと思います。  【前回の記事のまとめ】  バブルソート： 時間計算量 O(n2), 空間計算量O(n)  バケツソート： 時間計算量 O(m + n), 空間計算量O(m + n)  マージソート： 時間計算量 O(n log n), 空間計算量O(n)  【まとめおわり】  今回は、実際にphpでそれぞれのアルゴリズムを動かして、「計算量本当にそれであってん..." />
    <meta name="twitter:url" content="http://tech.innovation.co.jp/2018/06/25/Introduction-of-Computational-Complexity-2.html" />
    
    <script type="application/ld+json">
{
    "@context": "http://schema.org",
    "@type": "Article",
    "publisher": "イノベーション　エンジニアブログ",
    "author": {
        "@type": "Person",
        "name": null,
        "image": "https://avatars2.githubusercontent.com/u/39402426?v=4",
        "url": "undefined/author/undefined",
        "sameAs": ""
    },
    "headline": "アルゴリズム計算量入門　〜　②",
    "url": "http://tech.innovation.co.jp/2018/06/25/Introduction-of-Computational-Complexity-2.html",
    "datePublished": "2018-06-24T15:00:00.000Z",
    "dateModified": "2018-07-25T20:24:35.348Z",
    "keywords": "Complexity,  Sort Algorithm,  bigen",
    "description": "どうも、bigenです。 なぜ２本連続で書いているかというと、先週のブログ当番をブッチしてしまった罰ゲームです！ そんなわけで、 前回の記事に引き続き、ソートアルゴリズムの計算量について見ていこうと思います。  【前回の記事のまとめ】  バブルソート： 時間計算量 O(n2), 空間計算量O(n)  バケツソート： 時間計算量 O(m + n), 空間計算量O(m + n)  マージソート： 時間計算量 O(n log n), 空間計算量O(n)  【まとめおわり】  今回は、実際にphpでそれぞれのアルゴリズムを動かして、「計算量本当にそれであってん..."
}
    </script>

    <meta name="generator" content="Ghost ?" />
    <link rel="alternate" type="application/rss+xml" title="イノベーション　エンジニアブログ" href="http://tech.innovation.co.jp/rss" />
    <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/8.4/styles/default.min.css">


</head>
<body class="post-template tag-Complexity tag-Sort-Algorithm tag-bigen no-js">

    <span class="mobile btn-mobile-menu">
        <i class="icon icon-list btn-mobile-menu__icon"></i>
        <i class="icon icon-x-circle btn-mobile-close__icon hidden"></i>
    </span>

    <header class="panel-cover panel-cover--collapsed " >
      <div class="panel-main">
    
        <div class="panel-main__inner panel-inverted">
        <div class="panel-main__content">
    
            <h1 class="panel-cover__title panel-title"><a href="http://tech.innovation.co.jp" title="link to homepage for イノベーション　エンジニアブログ">イノベーション　エンジニアブログ</a></h1>
            <hr class="panel-cover__divider" />
            <p class="panel-cover__description">株式会社イノベーションのエンジニアたちの技術系ブログです。ITトレンド・List Finderの開発をベースに、業務外での技術研究などもブログとして発信していってます！</p>
            <hr class="panel-cover__divider panel-cover__divider--secondary" />
    
            <div class="navigation-wrapper">
    
              <nav class="cover-navigation cover-navigation--primary">
                <ul class="navigation">
                  <li class="navigation__item"><a href="http://tech.innovation.co.jp/#blog" title="link to イノベーション　エンジニアブログ blog" class="blog-button">Blog</a></li>
                </ul>
              </nav>
    
              
              
              <nav class="cover-navigation navigation--social">
                <ul class="navigation">
              
              
              
              
              
              
              
              
              
              
                </ul>
              </nav>
              
    
            </div>
    
          </div>
    
        </div>
    
        <div class="panel-cover--overlay"></div>
      </div>
    </header>

    <div class="content-wrapper">
        
    	<!-- ソーシャルボタンここから -->
    	<div id="boxArea" style="display: table; padding: 0 0 0 2px;">
    		<div style="width: 74px; height: 22px; float: left;">
    			<a href="https://twitter.com/share" class="twitter-share-button"
    				{count} data-lang="ja" data-dnt="true">ツイート</a>
    			<script>
    				!function(d, s, id) {
    					var js, fjs = d.getElementsByTagName(s)[0], p = /^http:/
    							.test(d.location) ? 'http' : 'https';
    					if (!d.getElementById(id)) {
    						js = d.createElement(s);
    						js.id = id;
    						js.src = p + '://platform.twitter.com/widgets.js';
    						fjs.parentNode.insertBefore(js, fjs);
    					}
    				}(document, 'script', 'twitter-wjs');
    			</script>
    		</div>
    		<div style="width: 76px; height: 22px; float: left;">
    			<div class="g-plusone" data-size="medium"></div>
    			<script type="text/javascript">
    				window.___gcfg = {
    					lang : 'ja'
    				};
    				(function() {
    					var po = document.createElement('script');
    					po.type = 'text/javascript';
    					po.async = true;
    					po.src = 'https://apis.google.com/js/platform.js';
    					var s = document.getElementsByTagName('script')[0];
    					s.parentNode.insertBefore(po, s);
    				})();
    			</script>
    		</div>
    		<div style="width: 126px; height: 22px; float: left;">
    			<a href="http://b.hatena.ne.jp/entry/" class="hatena-bookmark-button"
    				data-hatena-bookmark-layout="standard-balloon"
    				data-hatena-bookmark-lang="ja" title="このエントリーをはてなブックマークに追加"><img
    				src="http://b.st-hatena.com/images/entry-button/button-only@2x.png"
    				alt="このエントリーをはてなブックマークに追加" width="20" height="20"
    				style="border: none;" /></a>
    			<script type="text/javascript"
    				src="http://b.st-hatena.com/js/bookmark_button.js" charset="utf-8"
    				async="async"></script>
    		</div>
    		<div style="width: 117px; height: 22px; float: left;">
    			<a data-pocket-label="pocket" data-pocket-count="horizontal"
    				class="pocket-btn" data-lang="en"></a>
    		</div>
    		<div style="width: 86px; height: 22px; float: left;">
    			<span><script type="text/javascript"
    					src="//media.line.me/js/line-button.js?v=20140411"></script>
    				<script type="text/javascript">
    					new media_line_me.LineButton({
    						"pc" : true,
    						"lang" : "ja",
    						"type" : "a"
    					});
    				</script></span>
    		</div>
    		<div style="width: 114px; height: 22px; float: left;">
    			<script src="//platform.linkedin.com/in.js" type="text/javascript">
    				lang: ja_JP
    			</script>
    			<script type="IN/Share" data-counter="right"></script>
    		</div>
    		<div style="width: 112px; height: 22px; float: left;">
    			<iframe
    				scrolling="no" frameborder="0" id="fbframe"
				width="164" height="46" style="border:none;overflow:hidden" 
				allowTransparency="true"></iframe>
    		</div>
    		<script type="text/javascript">
    			(function() {
    				var url = encodeURIComponent(location.href);
    				document.getElementById('fbframe').src="//www.facebook.com/plugins/like.php?href=" + url + 
    				"&width=164&layout=button_count&action=like&show_faces=true&share=true&height=46&appId=1613776965579453"
    			})();
    		</script>
    	</div>
    	<script type="text/javascript">
    		!function(d, i) {
    			if (!d.getElementById(i)) {
    				var j = d.createElement("script");
    				j.id = i;
    				j.src = "https://widgets.getpocket.com/v1/j/btn.js?v=1";
    				var w = d.getElementById(i);
    				d.body.appendChild(j);
    			}
    		}(document, "pocket-btn-js");
    	</script>
    	<!-- ソーシャルボタンここまで -->
	
        <div class="content-wrapper__inner">
            

  <article class="post-container post-container--single">

    <header class="post-header">
      <div class="post-meta">
        <time datetime="25 Jun 2018" class="post-meta__date date">25 Jun 2018</time> &#8226; <span class="post-meta__tags tags">on <a href="http://tech.innovation.co.jp/tag/Complexity">Complexity</a>, <a href="http://tech.innovation.co.jp/tag/Sort-Algorithm"> Sort Algorithm</a>, <a href="http://tech.innovation.co.jp/tag/bigen"> bigen</a></span>
        <span class="post-meta__author author"><img src="https://avatars2.githubusercontent.com/u/39402426?v=4" alt="profile image for " class="avatar post-meta__avatar" /> by </span>
      </div>
      <h1 class="post-title">アルゴリズム計算量入門　〜　②</h1>
    </header>

    <section class="post tag-Complexity tag-Sort-Algorithm tag-bigen">
      <div id="preamble">
<div class="sectionbody">
<div class="paragraph">
<p>どうも、bigenです。<br>
なぜ２本連続で書いているかというと、先週のブログ当番をブッチしてしまった罰ゲームです！<br>
<br>
そんなわけで、 <a href="http://tech.innovation.co.jp/2018/06/26/Introduction-of-Computational-Complexity.html">前回の記事</a>に引き続き、ソートアルゴリズムの計算量について見ていこうと思います。<br>
<br>
 【前回の記事のまとめ】<br>
 バブルソート： 時間計算量 <strong><em>O(n<sup>2</sup>)</em></strong>, 空間計算量<strong><em>O(n)</em></strong><br>
 バケツソート： 時間計算量 <strong><em>O(m + n)</em></strong>, 空間計算量<strong><em>O(m + n)</em></strong><br>
 マージソート： 時間計算量 <strong><em>O(n</em> log <em>n)</em></strong>, 空間計算量<strong><em>O(n)</em></strong><br>
 【まとめおわり】<br>
<br>
 今回は、実際にphpでそれぞれのアルゴリズムを動かして、「計算量本当にそれであってんの？」っていうのを見ていきたいと思います。<br>
<br></p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="__">前提条件</h2>
<div class="sectionbody">
<div class="paragraph">
<p>OS: macOS High Sierra ver.10.13.5<br>
CPU: 第7世代の2.3GHzデュアルコアIntel Core i5プロセッサ<br>
メモリ: 8GB 2,133MHz LPDDR3メモリ<br>
PHP version: 7.1.16<br>
<br>
対象とする問題は、<br></p>
</div>
<div class="literalblock">
<div class="content">
<pre>1~mの範囲のランダムな自然数n個からなる配列を昇順にソートする</pre>
</div>
</div>
<div class="paragraph">
<p>としています。<br>
ソースは初心にかえって自力で用意しました。<br>
記事の末尾に付録としておいておきますので、暇な方はご参照ください。<br>
<br>
また、全体の流れとして、この後</p>
</div>
<div class="literalblock">
<div class="content">
<pre>データの数nや、データの取りうる種類mを増やした時に、計算時間とメモリの消費がどのように変化するか</pre>
</div>
</div>
<div class="paragraph">
<p>を実測で見ていきます。</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="___2">計算時間について</h2>
<div class="sectionbody">
<div class="paragraph">
<p>時間計算量は、それぞれ<br>
<br>
 バブルソート： 時間計算量 <strong><em>O(n<sup>2</sup>)</em></strong><br>
 バケツソート： 時間計算量 <strong><em>O(m + n)</em></strong><br>
 マージソート： 時間計算量 <strong><em>O(n</em> log <em>n)</em></strong> <br>
<br>
でした。<br>
<strong><em>O(n<sup>2</sup>)</em></strong>は「nが10倍になったら計算時間は100倍」<br>
<strong><em>O(m+n)</em></strong>は「nが10倍になったら計算時間も10倍、mが10倍になったら計算時間も10倍」<br>
<strong><em>O(n</em> log <em>n)</em></strong>は「nが10倍になったら計算時間は(10*ちょっと)倍、nが大きいほどちょっとは小さくなる」 <br>
という意味です。<br>
<br></p>
</div>
<div class="sect3">
<h4 id="__n">データの数が増える場合(nが増える場合)</h4>
<div class="paragraph">
<p>まずはデータの範囲は1~100の自然数に固定（<strong><em>m=100</em></strong>）し、データの数<strong><em>n</em></strong>を変化させた時に計算時間がどうなるか見ていきましょう。<br>
<br></p>
</div>
<table class="tableblock frame-all grid-all spread">
<caption class="title">Table 1. 計算時間(s) , m = 100</caption>
<colgroup>
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">n=100</th>
<th class="tableblock halign-left valign-top">n=1000</th>
<th class="tableblock halign-left valign-top">n=10000</th>
<th class="tableblock halign-left valign-top">n=100000</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バブルソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002770</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0278578</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">2.7695038</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">287.1152839</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バケツソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0000241</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0000670</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0005970</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0061991</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">マージソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002079</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0030000</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.1332741</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">11.2226848</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p><strong>バブルソート</strong>から見てみると、nが10倍になるにつれ、ほぼ<strong>100倍→10000倍→1000000倍</strong>ときれいに遅くなっていますね。<br>
典型的な<strong><em>O(n<sup>2</sup>)</em></strong>の増え方です。
アルゴリズムがシンプルなのもあり、他の依存要素が少ないため綺麗に比例してくれました。<br></p>
</div>
<div class="paragraph">
<p><strong>バケツソート</strong> は、n:100 &#8594; 1000は3倍程度しか増えていませんが、n: 1000 &#8594;10000 &#8594; 100000はほぼ10倍ずつ増えています。
これは、nが小さい領域ではデータの範囲mに依存する分が大きかったためでしょう。 <br>
n=100: 100(mに依存する時間) + 20(nに依存する時間) = 120<br>
n=1000: 100(mに依存する時間) + 200(nに依存する時間) = 300(3倍ぐらい)<br>
n=10000: 100(mに依存する時間) + 2000(nに依存する時間) = 2100(9倍ぐらい)<br>
n=10000: 100(mに依存する時間) + 20000(nに依存する時間) = 20100(10倍ぐらい)<br>
みたいな感じで増えていっただろうっていうことですね。<br>
理論通りの<strong><em>O(m+n)</em></strong>っぽい増え方をしてくれています。<br></p>
</div>
<div class="paragraph">
<p><strong>マージソート</strong>は、理論どおりにはいってくれませんでした。<br>
nが10倍ずつ増えていくとき、計算時間は<br>
<strong>15倍→45倍→80倍</strong><br>
と増えています。理屈上は増え方が減っていってほしいのですが・・・。<br>
原因としては、再起呼び出し条件が最適化されていなかったりするところでしょうか。<br>
（呼ばなくていい再帰呼び出しをしている箇所がある）<br>
それでも、計算量の増え方は、バブルソートよりかなり遅いのが見て取れます。<br>
<br></p>
</div>
</div>
<div class="sect3">
<h4 id="__m">データの取りうる範囲が大きくなる場合(mが増える場合)</h4>
<div class="paragraph">
<p>次に、データの数nを固定(n=100)して、データの取りうる範囲mを大きくしてみます。<br></p>
</div>
<table class="tableblock frame-all grid-all spread">
<caption class="title">Table 2. 計算時間(s) , n = 100</caption>
<colgroup>
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">m=100</th>
<th class="tableblock halign-left valign-top">m=1000</th>
<th class="tableblock halign-left valign-top">m=10000</th>
<th class="tableblock halign-left valign-top">m=100000</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バブルソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0003309</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002930</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0003278</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002920</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バケツソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0000350</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0000579</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0004789</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0067119</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">マージソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002470</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002210</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002301</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">0.0002169</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p><strong>バブルソート</strong>と<strong>マージソート</strong>は<strong>データの取りうる範囲mに依存していない</strong>ことが見て取れます。<br>
<br>
また、<strong>バケツソート</strong>だけm=1000~100000の間で大体10倍ずつ増えていっていることが分かります。<br>
<strong><em>O(m + n)</em></strong>っぽいですね！<br></p>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="___3">メモリ使用量について</h2>
<div class="sectionbody">
<div class="paragraph">
<p>空間計算量はそれぞれ、<br>
<br>
 バブルソート： 空間計算量 <strong><em>O(n)</em></strong><br>
 バケツソート： 空間計算量 <strong><em>O(m + n)</em></strong><br>
 マージソート： 空間計算量 <strong><em>O(n)</em></strong> <br></p>
</div>
<div class="paragraph">
<p>でした。<br>
<br>
メモリ使用量を計測するのは難しいのですが、phpではざっくり図るために<br>
<code>memory_get_peak_usage()</code>と<code>memory_get_usage()</code>の差を使って計測しました。<br>
計算の前後で増えたメモリ割り当て量が分かります。<br>
ノイズが多いので正確ではないですが、大体の増え方はつかめるんじゃないでしょうか。<br></p>
</div>
<div class="sect3">
<h4 id="__n_2">データの数が増える場合(nが増える場合)</h4>
<div class="paragraph">
<p>まずはじめに、データの取りうる範囲mを固定(m=100)して、データの数を増やしたときに割当てメモリがどう増えるか見てみましょう<br></p>
</div>
<table class="tableblock frame-all grid-all spread">
<caption class="title">Table 3. メモリ使用量(byte) , m = 100</caption>
<colgroup>
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">n=100</th>
<th class="tableblock halign-left valign-top">n=1000</th>
<th class="tableblock halign-left valign-top">n=10000</th>
<th class="tableblock halign-left valign-top">n=100000</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バブルソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36920</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">528440</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4198480</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バケツソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">45168</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">536688</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4206728</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">マージソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">95784</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">1112040</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">8477032</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p><strong>バブルソート</strong>と<strong>バケツソート</strong>はほぼ同じ増え方をしています。<br>
n=1000~100000の間で大体10倍ずつ増えています。<br>
<strong><em>O(n)</em></strong>とか<strong><em>O(m+n)</em></strong> っぽいですね。<br>
少し不安定なのでもう少し様子をみたかったのですが、バブルソートはデータ数がこれ以上増えると計算時間がなかなかのものだったので諦めました。<br>
<br>
<strong>マージソート</strong>も、他の2つに比べてメモリが多いように見えますが、増え方を見ると10倍ずつ大きくなっており、結局
<strong><em>O(n)</em></strong>っぽいですね。<br>
計算通りでした。<br></p>
</div>
</div>
<div class="sect3">
<h4 id="__m_2">データの取りうる範囲が大きくなる場合(mが増える場合)</h4>
<div class="paragraph">
<p>次に、データの数nを固定(n=100)して、データの取りうる範囲mを増やしてみました。<br></p>
</div>
<table class="tableblock frame-all grid-all spread">
<caption class="title">Table 4. メモリ使用量(byte) , n = 100</caption>
<colgroup>
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
<col style="width: 20%;">
</colgroup>
<thead>
<tr>
<th class="tableblock halign-left valign-top"></th>
<th class="tableblock halign-left valign-top">m=100</th>
<th class="tableblock halign-left valign-top">m=1000</th>
<th class="tableblock halign-left valign-top">m=10000</th>
<th class="tableblock halign-left valign-top">m=100000</th>
</tr>
</thead>
<tbody>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バブルソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">バケツソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">45168</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">536688</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">4206728</p></td>
</tr>
<tr>
<td class="tableblock halign-left valign-top"><p class="tableblock">マージソート</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
<td class="tableblock halign-left valign-top"><p class="tableblock">36544</p></td>
</tr>
</tbody>
</table>
<div class="paragraph">
<p>phpの基本使用料が36500byteぐらい使うのは良いとして、<strong>バケツソートだけ</strong> m=1000~100000の間で大体10倍ずつ増えていくのが分かりました。<br>
<strong><em>O(m+n)</em></strong>っぽいですね。<br>
また、<strong>バブルソート</strong>と<strong>マージソート</strong>は<strong>データの範囲mには依存していない</strong>ことも分かります。<br>
どちらも計算通り、といったところでしょうか。<br>
<br></p>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="___4">まとめ</h2>
<div class="sectionbody">
<div class="paragraph">
<p>全体として、理論上の増え方になかなか近い実測値が出たんじゃないでしょうか。<br>
<br>
みなさんも、エンジニアであれば<br>
<strong>「とりあえず動かしてみたけど結果が返ってこない。あと1分で終わるかもしれないし、1年かもしれない。いつまで待てばいいんだ？」</strong><br>
みたいな時ありますよね？<br></p>
</div>
<div class="paragraph">
<p>あらかじめプログラムの計算量がわかっていると、データ数だけ見れば「数時間」なのか「数日」なのか「数年」なのかぐらいは大体分かるのです。 <br>
すごい！<br>
<br>
また、<strong><em>O(n)</em></strong>のような書き方を<strong>オーダー記法</strong>や<strong>ビッグオー記法</strong>といったりするのですが、これをわかってると<br>
「そのアルゴリズムってどれぐらい早いの？」<br>
「エヌログエヌオーダーだぜ！今までのエヌニジョウオーダーとは比べ物にならないぜ！」<br>
みたいな会話ができるわけですね。<br>
すごい！！<br>
<br>
興味ある方は、ぜひ色々調べてみてください。<br>
こちらからは以上です。<br></p>
</div>
<div class="sect2">
<h3 id="___5">付録</h3>
<div class="paragraph">
<p>ソースコードはこちら。
GitHubはこちら。
<a href="https://github.com/bigen1925/complexity_of_sort_algorithm" class="bare">https://github.com/bigen1925/complexity_of_sort_algorithm</a></p>
</div>
<div class="listingblock">
<div class="content">
<pre class="highlight"><code class="language-php" data-lang="php">&lt;?php
//////////////
// Usage
// Call from command line
// $ php sort.php &lt;number_of_data&gt; &lt;max_range_of_data&gt; &lt;kind_of_sort_method&gt;
// Sample: $ php sort.php 1000 100 bubble
//////////////

// データの数
$length_array = (int)$argv[1] ?: 1000;
// データのとりうる値の上限
$max_range = (int)$argv[2] ?: 100;
// ソートアルゴリズム
$sort_method = $argv[3] ?: "all";

// 計測
main($length_array, $max_range, $sort_method);

function main($length_array, $max_range, $sort_method)
{
    // 1~max_rangeまでの数字から成る、ランダムな順序の数列を生成
    $array = array();
    for ($i=0; $i &lt; $length_array; $i++) {
        $array[] = rand(1, $max_range);
    }

    // 初期の割当メモリ
    $initial_memory_usage = memory_get_usage();

    if ($sort_method === "all" || $sort_method === "bubble") {
        $time_start = microtime(true);
        bubbleSort($array);
        $time = microtime(true) - $time_start;
        echo "bubbleSort:: {$time}s\n";
    }

    if ($sort_method === "all" || $sort_method === "buckets") {
        $time_start = microtime(true);
        bucketsSort($array, $max_range);
        $time = microtime(true) - $time_start;
        echo "bucketsSort:: {$time}s\n";
    }

    if ($sort_method === "all" || $sort_method === "merge") {
        $time_start = microtime(true);
        mergeSort($array);
        $time = microtime(true) - $time_start;
        echo "mergeSort:: {$time}s\n";
    }

    // プログラム実行中に追加で割り当てられたメモリ量
    $used_memory = memory_get_peak_usage() - $initial_memory_usage;
    echo "used_memory:: {$used_memory}\n";
}

// バブルソート
// @param array @array ソートしたい自然数配列
// @return array ソート済みの配列
function bubbleSort(array $array)
{
    $length = count($array);
    for ($i=0; $i &lt; $length; $i++) {
        for ($j=0; $j &lt; $length - $i - 1; $j++) {
            if ($array[$j] &gt; $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

// バケツソート
// @param array $array ソートしたい自然数配列
// @param integer $max_range データのとりうる最大値
// @return array ソート済みの配列
function bucketsSort(array $array, $max_range)
{
    $length = count($array);
    $buckets = array_fill(1, $max_range, 0);
    $sorted_array = array();

    foreach ($array as $value) {
        $buckets[$value]++;
    }

    foreach ($buckets as $value =&gt; $count) {
        for ($i = 0; $i &lt; $count; $i++) {
            $sorted_array[] = $value;
        }
    }

    return $sorted_array;
}

// マージソート
// @param array $array ソートしたい自然数配列
// @return array ソート済み配列
function mergeSort(array $array)
{
    $length = count($array);
    $sorted_array = array();

    if ($length &gt; 1) {
        $mid_index = floor(($length + 0.5) / 2);
        $left_array = array_slice($array, 0, $mid_index);
        $right_array = array_slice($array, $mid_index);

        $left_array = mergeSort($left_array);
        $right_array = mergeSort($right_array);
        while (count($left_array) || count($right_array)) {
            if (count($left_array) == 0) {
                $sorted_array[] = array_shift($right_array);
            } elseif (count($right_array) == 0) {
                $sorted_array[] = array_shift($left_array);
            } elseif ($left_array[0] &gt; $right_array[0]) {
                $sorted_array[] = array_shift($right_array);
            } else {
                $sorted_array[] = array_shift($left_array);
            }
        }
    } else {
        $sorted_array = $array;
    }

    return $sorted_array;
}</code></pre>
</div>
</div>
</div>
</div>
</div>
    </section>

  </article>




            <footer class="footer">
                <span class="footer__copyright">&copy; 2018. All rights reserved.</span>
                <span class="footer__copyright"><a href="http://uno.daleanthony.com" title="link to page for Uno Ghost theme">Uno theme</a> by <a href="http://daleanthony.com" title="link to website for Dale-Anthony">Dale-Anthony</a></span>
                <span class="footer__copyright">Proudly published with <a href="http://hubpress.io" title="link to Hubpress website">Hubpress</a></span>
            </footer>
        </div>
    </div>

    <script src="//cdnjs.cloudflare.com/ajax/libs/jquery/2.1.3/jquery.min.js?v="></script> <script src="//cdnjs.cloudflare.com/ajax/libs/moment.js/2.9.0/moment-with-locales.min.js?v="></script> <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/8.4/highlight.min.js?v="></script> 
      <script type="text/javascript">
        jQuery( document ).ready(function() {
          // change date with ago
          jQuery('ago.ago').each(function(){
            var element = jQuery(this).parent();
            element.html( moment(element.text()).fromNow());
          });
        });

        hljs.initHighlightingOnLoad();      
      </script>

    <script type="text/javascript" src="//tech.innovation.co.jp/themes/uno/assets/js/main.js?v=1.0.0"></script>
    
    <script>
    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
      (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
      m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
    })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

    ga('create', 'UA-105881090-1', 'auto');
    ga('send', 'pageview');

    </script>

</body>
</html>
