Version 13.30
計算量と時間

「さて、今回はアルゴリズムを考えるうえで重要な【計算量】、そして処理
に掛かる時間の計算方法について考えます」
『それってやっぱり重要なんだね……』
「まず、アルゴリズムの【計算量】について」
『それって、検索するとどこででも出てくるね』
「アルゴリズムの処理にどれくらい時間が掛かるかの目安だからね。計算量
の書き方は」

O(？)

「みたいになります」
『……なんか数学っぽくて難しい……』
「アルゴリズムは数学の世界だからね。僕の方針としては、プログラムに必
要なことだけ勉強すればいいって考えているから、数学的なことは置いてお
きます」
『その方が助かるかも』
「 O は【オーダー】と読みます。問題は？のところ。基本的に、？の所に
は〈要素数の何乗〉が入ります」
『要素数、って配列の中身の数だよね。それの何乗……』
「具体例で説明していこうか。まず要素数を N とします。つまり 
int iAry[N] みたいな場合」
『うん』
「では例として Version 13.07 ( No.243 ) のバブルソートについて考えま
す。バブルソートは、右からふたつずつ比較して、右の方が小さかったら入
れ替える、というのを繰り返すというものでした」
『そうすると自然と左の方に小さいのが行ってるんだよね』
「まず１周目の比較について。１周目は N - 1 回比較します」
『あれ？　 N じゃないの？』
「ふたつずつ比較するんだから、 1 少なくなるでしょ。実際に試してみた
ときの例を追ってみて」
『あ、要素数５で４回しか比較してない……あー、〈間の数〉だけ比較す
るんだね』
「う、うん、そういうこと……かな。さて、２周目は、一番左に一番小さな
数が来てるからこれは比較しないので、 N - 1 - 1 = N - 2 回比較します」
『１回少なくなるんだね』
「それを繰り返すと、比較回数は」

( N - 1 ) + ( N - 2 ) + ... + ( 2 ) + ( 1 ) 

「となります。これを数学の公式で書くと」

N * ( N - 1 ) / 2

「になります」
『数学の公式……』
「まぁこれは当てはめちゃえばいいだけだから難しいこと考えないで。重要
なのはここからだから」
『重要？』
「すごく重要。と、その前に」
『その前に？』
「〈 A の x 乗〉を〈 Z ^ x 〉と書くとします」
『 2 の 4 乗なら 2 ^ 4 ってことね』
「そういうこと。で、さっきの式を計算すると」

( ( 1/2 ) * N ^ 2 ) - ( ( 1/2 ) * N )

「となります」
『ただカッコ開いただけだね』
「さて。ここで N を 1 から順に増やしてみます」

( ( 1/2 ) * 1   ) - ( ( 1/2 ) * 1 )
( ( 1/2 ) * 2   ) - ( ( 1/2 ) * 2 )
( ( 1/2 ) * 4   ) - ( ( 1/2 ) * 3 )
( ( 1/2 ) * 8   ) - ( ( 1/2 ) * 4 )
( ( 1/2 ) * 16  ) - ( ( 1/2 ) * 5 )
( ( 1/2 ) * 32  ) - ( ( 1/2 ) * 6 )
( ( 1/2 ) * 64  ) - ( ( 1/2 ) * 7 )
( ( 1/2 ) * 128 ) - ( ( 1/2 ) * 8 )

『 N ^ 2 のところがすごく増えてくね。二乗だから当然だけど』
「そう、そこが重要！！」
『え、なに？』
「 N がある程度大きな数の場合、 N ^ 2 の影響力が大きすぎて、これにか
けている 1/2 や、右側の - ( ( 1/2 ) * N ) がほとんど意味がなくなって
しまうんです」
『確かに二乗の前には微々たるものよね』
「そこで、この？の所には、意味がない部分を取り除いて」

O( N ^ 2 )

「と記述します」
『おー、他のをばっさり削っちゃうんだ』
「この考え方がとても重要なんです。アルゴリズムに限らず、プログラムは
for などのループで〈何乗〉の計算が簡単に発生します」
『２重ループで２乗、３重ループで３乗ね』
「この〈何乗〉というのは要素数が増えるとすごく計算量が増えます。だか
ら、個別の計算とかよりも、この〈何乗〉っていう点は常に気を付けておい
て」
『〈何乗〉の計算になったらすごく重くなる、ってこと？』
「そういうこと。プログラムの中で for や while を入れる時には、こう
いったことを常に頭の片隅に入れておいて」
『はーい、って言ってもそれって結構難しいよね……』
「優れたプログラマーの資質のひとつに〈危険察知能力〉があるかも」
『危険察知能力、ねぇ……』
「さて、このオーダーの話は机上の話です」
『机上の空論？』
「とまでは言わないけど、実際問題として、 N が１なのと１００万とじゃ
全然違うでしょ」
『それは違いすぎ……』
「でも現実ではそういったことも考えなきゃいけないから。実際にプログラ
ムを組む上で注意しなきゃいけないのは、オーダーの他には次の３つ」

・要素数
・処理に掛かる時間的コスト
・データ容量

「ひとつひとつ見ていこうか」

・要素数

『これが今言ってた１か１００万か、ね』
「そういうこと。アルゴリズムの多くは要素数がそのままループ数になるか
ら、要素数がいくつか、っていうのを考える必要があるかな」
『でもそれって決まってるものかな』
「その辺の切り分けが重要。まず、要素数の中にはプログラム上固定のもの
があります」
『固定？』
「たとえば〈月の数〉とか」
『あー、それなら１２固定だね』
「固定でないにしても、プログラム上、上限値が決まっている場合は多いか
ら、それなら時間がわかるよね」
『決まってない場合っていうのは？』
「一番多いのが、ユーザーが入力できたり、環境に依存したりする場合。
一番ありがちなのが、ファイル数。あるフォルダに入っているファイルをす
べて処理する、とか」
『ユーザーがいっぱいファイル入れたらすごいことに……ってこと？』
「そういうこと。ユーザーによってデータ数が可変になる場合、ユーザーは
上限とか全然気にしないから、そういう可能性があるかどうか常に気を付け
ておく必要があります」
『気を付けてどうするの？』
「方法はいくつかあるかな。ある一定以上の数なら処理前に警告する、上限
を設けて超えていたらエラーにする、途中でキャンセルできるようにする、
とか」
『キャンセルが一番楽そう』
「これは次の章で紹介する【マルチスレッド】を使うことになるから、その
ときに説明します」
『はーい』
「では次」

・処理に掛かる時間的コスト

「ズバリ言えば、メモリアクセスよりファイルアクセスの方が重い、ってこ
と」
『当然じゃない』
「そうなんだけど……たとえば O( N ^ 2 ) と O( N ^ 3 ) でも、もし
O( N ^ 2 ) がファイルアクセス、 O( N ^ 3 ) がメモリアクセスなら」
『計算量が少ない方が時間かかっちゃう、ってわけね』
「そういうこと。特にファイルをメモリ代わりに使ったりするとかなり重く
なるから」
『ファイルをメモリ代わり？』
「具体的に言うと【データベース】へのアクセス」
『データベース……きいたことあるしなんとなくわかるけどよくわかんな
い』
「データベースの説明はもう少し先になるかな。 C++ からのアクセスは面
倒だし……まぁ、思わぬことでファイルアクセスがあったりすると重くなる
から、どこでそういう処理をしているか気を付けてってこと」
『はーい』
「では最後」

・データ容量

「これは今の話と関係していて、たとえばファイルアクセスを減らすため
に、最初にファイルから全部メモリの構造体に入れてそれを処理する、と
いう方法があります」
『そうすればファイルアクセスなくなるもんね』
「ところが、その際のデータ容量がすごく大きいと、結局はファイルアクセ
スが発生して重くなっていまいます」
『え”、そうなの？』
「メモリに入りきらないデータはハードディスクに書き込まれるから」
『それがファイルアクセスになる……って、でもメモリって他のアプリとか
も関係してくるんでしょ？』
「そのとき動かしているアプリの数や占有されているメモリのサイズ、マシ
ンに積まれているメモリの容量、そういったものが関係してくるからプログ
ラムの側ではカバーしきれない部分もあります」
『そういう時にはどうするの？』
「そういうときのために〈最低メモリ容量〉とか書いてあるでしょ」
『あ、そういえばそうだね』
「まぁそれも目安にしかならないけどね。さて、こういった現実的な問題が
あるわけですが、できればすべてのループ、すべての処理でこういった点に
ついては考慮しておいてください」
『考慮するだけでいいの？　したら、なんか対処しなきゃいけないんじゃな
いの？』
「もちろんそうなんだけど、実は〈考慮しない〉っていうことが多いんだよ
ね……プログラムを作っているときって」
『……そういうもの？』
「まず動くものできなきゃしょうがないでしょ」
『あー』
「それに、関数から関数を呼び出すような場合、厳密には〈呼び出している
関数がどれだけ時間掛かるか〉っていうのを把握してなきゃいけないけど」
『それって大変だよね。関数が増えたら特に』
「だから現実的には難しいけど、それでも常に気にはしておいてください」
『はーい』

/*
    Preview Next Story!
*/
「次回でアルゴリズム編は最後です」
『３部構成みたいな感じだったから、思ったより早いかも』
「まぁもっと本格的にやったら１年掛かるだろうけど」
『うわ』
「ま、その辺ははしょるってことで」
『というわけで次回』
＜ Version 13.31 アルゴリズムのまとめ ＞
『につづく！』
「……まとめ、っていう割にはちょっとまとまってないかも」
『ダメじゃん』