アマチュア数学者の日記

とある大学で数学を学んでいます。専門は偏微分方程式です。高校野球、マラソン、カメラ、数学、etc...多趣味です。様々なことを書いていきます。

計算量

数学をするうえで計算をすることは重要なことです。数学に限らず日常生活の中でも計算をすること機会は多々あります。昔はそろばんを使って計算をしていたようですが今はほとんどが電卓を使います。近年ではスマホの電卓機能のレベルも高く、いつでもどこでも面倒くさい計算を瞬時にすることができます。また、関数電卓のアプリを入れると関数の計算も瞬時に行ってくれます。

私たちが普段行う計算程度では習字に計算できてしまいますが、大量の計算を行う場合、いくらコンピュータとはいえ、計算に時間がかかってしまいます。(現に古いコンピュータ等で計算エクセルなどを使うと処理に時間が掛かります。)

そこでコンピュータメーカーや計算機に携わる仕事をしている人は何とかして計算の量を減らすことはできないか?ということを考えるのです。

計算量とは

ある数同士を計算したいときに、同じ結果が得られるのならば計算の回数を少なくする方が時間的にも、消費電力的にもメリットがあるのです。私たちが計算する時も計算の量をいかに少なくするかということは程度の差はあれ誰しもが考えることだと思います。

では、計算方法を変えても本当に同じ結果が得られるのでしょうか?

ここで一つの例を見てみたいと思います。

 

Aさんは定期預金に100万円を10年間預けたとしましょう。この銀行の金利が5%だったとします。(こんな金利はこの時代にありえませんが例として)10年後Aさんの定期預金が満期を迎えたとき、Aさんは銀行からいくら受け取ることができるでしょうか?

という問いがあったとします。

実際に計算してみます

1年後には 100万円×1.05=105万円

2年後には 100万円×1.05×1.05=100万円×(1.05)^2

これを繰り返すと10年後には 100万円×(1.05)^10≒100万円×1.63≒=163万円

となります。これが複利効果というやつですね。10年後の金利を求める際に、掛け算を10回行いました。便宜的にこれの計算量を10としましょう。

次に、今行った計算をもう少し効率よく(=計算量を減らして)行ってみましょう。

指数法則に従えば

100万円×(1.05)^10=100万円×(((1.05)^2)^2×1.05)^2

()が3つあって少し見にくいですが、文で説明します

①1.05を2乗する。

②さらにそれを2乗します。(この時点で4乗です。)

③次に4乗した状態の数に1.05を1回かけます。(この時点で5乗)

④5乗した状態の数を2乗する。(この時点で10乗)

⑤最後に100万円に④で出た10乗の数をかける。

 すなわち100万円×(1.05)^10≒100万円×1.63≒=163万円

 

以上のステップにより掛け算を行うことで計算する回数を5回に減らすことができました。

このように計算を「うまく」行うことで劇的に計算量を減らせる場合もあります。今回の計算では10回計算する方法では最大の時間がかかり、5回で計算する方法では最短の時間内で計算を終了させることができます。強調したいことは計算結果はどちらも同じであるということです。

次に一般の指数法則について確認しておきます。

A.mが偶数のとき

m=2nとかけてx^2n=(x^n)^2

B.mが奇数の時
m=2n+1とかけて x^2n+1=(x^n)^2×x
 

以上から次のことがわかります。

自然数mを2進数で表した桁数をkとすると、x^nの計算に必要な掛け算の回数は、(k-1)回以上、2(k-1)回以下である」

 

計算量のオーダー

先ほどは便宜的に掛け算の回数を計算量として例を挙げました。先ほどの例程度の計算うならばだ簡単に求めることができますが、一般には難しいです。また、それを正確に求めることもそこまで重要ではありません。計算量を正確に求めたところで正確な計算結果が求まるわけではないからです。ただ計算量がどれくらいあるのか?ということをうことには意味があります。そこで、おおまか計算量を表す指標的なものがあります。

 計算量のサイズをNとするとf(N)を計算量のオーダーといいます。f(N)はNの関数です。具体的には、N^2とかN^3とかlogNとか2^Nとかになります。

時間計算量が「サイズNの多項式でおさえられる」ことを「多項式時間」といい、「サイズNの指数関数でおさえられる」ことを「指数関数時間」といいます。

※数学でおさえるというとき、不等式で評価することをいいます。例えばxは2^nでおさえられるというと、x<2^Nのことをいいます。

一般に多項式時間はNのサイズが大きくなったときf(N)のサイズも「まぁまぁ」大きくなります。すなわちNのサイズが大きくなると「まぁまぁ」長い時間で計算を完了させることができることが多いです。(必ずできる保証はありません)

一方、指数関数時間はNのサイズが大きくなるとf(N)のサイズが爆発的に多くなるという性質があります。すなわち、ある計算をコンピュータに命令した時に、その計算が指数関数時間かかる場合、「常識的な」時間内に終わらないという性質があります。「常識的な」時間より長くなるとは、たとえば人類の寿命よりも長かったり、地球の寿命よりも長かった利するような時間のことです。

 

以上のように、計算量をいかに効率化することができるか、というのは人類の課題でもあります。コンピュータの発展の歴史は、計算の効率化の歴史といっても過言ではないかもしれません。