アルゴリズム学習 #3 (時間)計算量

今回は、「計算量」です。

AtCoderに参加していても、よく時間オーバーになってしまうことがあります。
そういったときに、模範解答を見てみると大抵for文をぶん回してしまっているのがダメみたいです。

ということで今回は計算量について、下記のサイトを見てみる。

n個のデータに対して、for 分を2回利用するものであれば、基本的に計算量は下記のようになるようです。

a:単位時間当たりの処理時間
n:データ量

a*n^2

再起関数を用いた計算量の求め方がわかりませんでしたが、
基本的に、判定文は無視して、データ量毎の繰り返し文と単純な処理で足し算と掛け算を計算することでお止まるようです。

では、素数を効率的に求めるアルゴリズム を# 1エラトステネスの篩(ふるい)と単純な実装を考えてい見ます。

[エラトステネスの篩(ふるい) 計算量]
1+1+1+n/2+√n×√n＋1
=1+1+1+n/2+n＋1
=n ※高い次数のみ取り出す

[単純な実装)(下記参照)計算量]
n*((1+√n+1)+1)
=3n+√n*n
=√n*n ※高い次数のみ取り出す

import math 

def is_ prime( n):
    if n <= 1:
        return False
    for i in range( 2, int( math. sqrt( n)) + 1):
        if n % i == 0:
            return False 
    return True 

for i in range(200):
     if is_ prime(i):
         print( i, end =' ')

ということで、単純な実装と比べると√n分の計算量が減らせているという計算になります。
次回以降からは計算量も日ごろから意識しつつ進めていきたいと思います。

[参考]

• サイト

dandan-611.hatenablog.com
[初心者向け] プログラムの計算量を求める方法 - Qiita
bmf-tech - O（オーダー）記法とアルゴリズムの計算量の求め方