1つのインスタンス(整数べき乗指数)からアルゴリズム時間複雑度の解析を行う

アルゴリズムの時間的複雑さは基本ステップ(basic steps)の考慮にある.
複雑さ
notation
説明
コンスタント
O(1)
基本操作数は定数で入力データの規模に関係なくn=10^6⇒1-2 operations
対数(Logarithmic)
O(logn)
操作数はlog 2 n=10^6⇒30 operations
リニア(Linear)
O(n)
操作数は入力データの規模に比例n=10^6⇒5000 operations
平方(Quadratic)
O(n2)
キューブ(Cubic)
O(n3)
指数(exponential)
O(2n) O(kn) O(n!)
成長は非常に恐ろしい

整数べき乗指数を計算する3つの考え方

f(n)=an

遍歴乗算

def exp1(a, n):
    r = 1
    while n:
        r *= a
        n -= 1
    return r

その基本手順は(一次反復):判断(while)+乗算+減算==3であるため、サイクル全体の時間複雑度は:3 n+2⇒O(n)

である.

再帰版

def exp2(a, n):
    if n == 1:
        return a
    else:
        return a*exp2(a, n-1)

再帰版の時間的複雑さは、依然として再帰形式で分析されている.t(n):現在を識別すると、t(n)=3+t(n−1)となり、そのうち3は、1回の判断、1回の乗算、1回の減算を表す.
t(n)=3+t(n−1)t(n)=3k+t(n−k)t(n)=3(n−1)+t(1)=3(n−1)+2

再帰改良版
f(a,n)=an=⎧⎩⎨⎪⎪(a2)n/2=f(a2,n/2),a×(a2)(n−1)/2=a×f(a2,n−12),n is evenn is odd

def exp3(a, n):
    if n == 1:
        return a
    return exp3(a**2, n//2) if n%2 == 0 a*exp3(a**2, n//2)

nが偶数の場合、t(n)=6+t(n/2);nが奇数の場合、t(n)=6+t(n−1)=6+6+t(n−12)であるため、t(n)=12+t(n/2)=12×log 2 n+t(1)時間複雑度:logn

References

[1]アルゴリズム複雑度解析