プログラム作成時のアルゴリズムと計算量について考えてみた

2020年2月22日2021年6月19日

1. アルゴリズムとは
2. アルゴリズムの評価
3. 計算量とは
4. 時間計算量の調べ方
5. 計算量の比較
6. リスト内包表記について
7. まとめ
8. 参考にした書籍
- 8.1. おすすめ記事
- 8.2. 関連

アルゴリズムとは

問題を解く手順のことです。

簡単に言うと、はじめにAして、そのつぎBして・・・という手順のこと。

一般的には解き方の数だけアルゴリズムが存在します。

また、問題がはやく解けるアルゴリズム＝良いアルゴリズムとされています。

なぜなら、処理速度（作業の効率化）はコストに直結するからです。

時間はお金です「Time is money（タイムイズマネー）」

データ量が多ければそれだけ計算に時間がかかります。

良いアルゴリズムなら大幅に計算時間が短縮できます。

アルゴリズムの評価

アルゴリズムの良し悪しを判断する一番簡単な方法は、プログラムを作って実行することです。

でもこの方法には問題があります。

問題点１：使う言語によって結果が異なる

C/C++だとメッチャはやい！

Pythonだとメッチャおそい！

なんてことがあります。

問題点2：開発環境によって結果が異なる

最新のCPUと大量のメモリを積んだパソコンではバリバリ動いた。

旧型のCPUで少量のメモリしか積んでないパソコンでは死ぬほど遅い。

どんな環境でもその環境において最速であることが望ましいです。

言語や環境に依らない評価方法は何か？

それは「計算量」という考え方です。

計算量とは

計算の複雑さを表現する言葉です。

英語で「Computational Complexity」といいます。

計算量にはいくつかの種類があります。

時間計算量
空間計算量
通信計算量
回路計算量

一般に「計算量」と言えば、時間計算量を意味します。

以下、特に大事な時間計算量と通信計算量について述べます。

時間計算量とは

アルゴリズムの処理にどれくらいの時間がかかるかを示す量で、CPUの処理速度によって決まります。

空間計算量とは

記憶容量（メモリ）をどれくらい必要とするかを示す量で、メモリの量によって決まります。

時間計算量の調べ方

CPUが命令を実行した回数を調べることで求められますが、正確な回数は数えられません。

そこで、処理を終了するまでに命令の基本単位を何回実行したかを調べて計算時間とします。

例えば、Python で以下のプログラムを実行した場合を考えます。

# test_1.py
for i in range(10):
    i += 1
    print("答え：", i)
>
答え： 1
答え： 2
答え： 3
答え： 4
答え： 5
答え： 6
答え： 7
答え： 8
答え： 9
答え： 10

for ループを1回まわすたびにprint 文で計算結果を1回出力します。

これを10回繰り返します。

print 文を1回実行するのにΑ時間かかるとします。

10回繰り返した時の時間は、（A×10）時間です。

次に、for ループ内に if 文による条件判定がある場合を考えます。

# test_2.py
for i in range(10):
    i += 1
    if i % 2 == 0:
        print("偶数：", i)
    else:
        print("奇数：", i)
>
奇数： 1
偶数： 2
奇数： 3
偶数： 4
奇数： 5
偶数： 6
奇数： 7
偶数： 8
奇数： 9
偶数： 10

先ほどと同じように、print 文を1回実行するのにA時間かかります。

if 文で条件判定するのにB時間かかるとします。

全体の処理時間は、（(A+B)×10）時間です。

さらに、for の2重ループの場合を考えます。

# test_3.py
for i in range(10):
    for j in range(10):
        k = i + j
        print("答え：" + str(i) + "+" + str(j) + "=", k)
>
答え：0+0= 0
答え：0+1= 1
答え：0+2= 2
答え：0+3= 3
答え：0+4= 4
答え：0+5= 5
・・・
答え：9+5= 14
答え：9+6= 15
答え：9+7= 16
答え：9+8= 17
答え：9+9= 18

print 文を1回実行するのにA時間かかります。

内側のforループが10回、外側のforループが10回まわります。

全体の処理時間は、(A×10×10)時間です。

forループが重なるほど、また、実行回数（今の例では10）が大きくほど、処理時間が長くなることが分かります。

計算量の比較

プログラムを実行した際、各命令に以下の処理時間がかかるとします。

print 文の実行　：A時間
if 文の実行　　：B時間
for ループの実行：ｎ時間

AやBは1つの命令の実行に掛かる時間はデータ量とは関係ありません。

データ量が大きくなった際に一番影響を受けるのはｎです。

for ループを重ねるとｎは乗数（ｎを何回掛け合わせるか）で効いてきます。

処理時間を短くするためには、如何にｎを小さくするかが重要です。

なお、計算量を記述する記号として「O」（オー）という記号（ランダウの記号）があります。

これは、全体の計算量に大きな影響がない部分（A、B）を無視してO(ｎ)のように記述するものです。

以下にオーダー比較表を示します。

処理時間	オーダー	例	例
短い	O(1)	print 文実行	－
↑	O(ｎ)	for ループ1重	test_1.py test_2.py
↓	O(ｎ＾2)	for ループ2重	test_3.py
長い	O(ｎ＾3)	for ループ3重	－

この表から for ループはなるべく重ねない方が良いことが分かります。

処理時間を短くするテクニックがあります。

それは、リスト内包表記を使う方法です。

リスト内包表記について

繰り返し処理には forループを使うのが一般的ですが、Python にはリスト内包表記という便利なものがあります。

例１：リスト内容表記を使った場合

print([i+j for i in range(10) for j in range(10)])

例２：for ループを使った場合

for i in range(10):
    for j in range(10):
        print(i+j)

例１と例２は等価です。

リスト内包表記の最大のメリットは処理時間の短縮です。

処理速度を比較してみます。

import time
t0 = time.time()
print([i+j for i in range(10) for j in range(10)])
t1 = time.time() - t0
print("時間：", float(t1))
>
時間： 0.000997066497802734

import time
t0 = time.time()
for i in range(10):
    for j in range(10):
        k = i + j
        print("答え：" + str(i) + "+" + str(j) + "=", k)
t1 = time.time() - t0
print("時間：", float(t1))
>
時間： 0.016955137252807617