再帰を用いたプログラムの計算複雑度について

投稿者: Anonymous

ある面で、最も広い面積の正方形の辺の長さを求めるプログラムを書いています。
入力された配列の要素が0なら黒、1なら白とし、白の面積が最大となる場合の1辺の長さを出力します。

困っていること
動的計画法で書いた再帰表現を含むプログラムを実行しているのですが、計算複雑度のオーダを考える時に、最悪の場合「square(M, i+1, j+1) + 1 」が何回繰り返されるかに依存すると考えられます。

行列Mの縦横i,jの内、長い方ということになるでしょうか。
3×4行列であれば、O(4)で、一般化するとCが定数でO(C)という理解で合っていますか。
もし間違っていたらご指摘いただきたいです。

プログラム

def square(S, i, j):
    max = 0
    if S[i][j]== 0:
        return 0
    elif S[i][j]==1 and S[i+1][j]==1 and S[i][j+1]==1 and S[i+1][j+1]==1:
        return square(S, i+1, j+1) + 1 
    return 1

i = 2
j = 1

S= [[0, 1, 1, 0, 1], 
    [1, 1, 0, 1, 0], 
    [0, 1, 1, 1, 0], 
    [1, 1, 1, 1, 0], 
    [0, 0, 0, 0, 0]] 


print(square(S, i, j)) #2

解決

計算量に関する考え方が根本的に間違っています。

問題に対して変化する数量、この問題の場合はiやjに対して計算量がどれぐらいのオーダーで変化するかどうかです。たとえば、もし、1×1行列でも3×4行列でも10000×10000行列でも計算回数(時間計算量)もメモリ使用量(空間計算量)も変わらないようなアルゴリズムであればO(1)です。しかし、もし、1×1行列の計算量にたいして、3×4行列では最大で4倍、10000×10000行列では最大で10000倍、ほとんどの場合で最大でmax(i, j)倍になるようであれば、O(max(i,j))であろうとなります。つまり、3×4行列だけを考えてもダメで、色々変化していくときにどうなるかを考える必要があります。

このように、変化して行くであろう数量に対して、計算回数やメモリ使用量がどれくらいのオーダー(n倍なのか、n^2倍なのか、n!倍なのか、それとも変わらないのか)で必要になっていくのかを見ていきます。NPPさんが、10000×10000行列も3×4行列も1×1行列も最悪の場合の計算回数が変わらないと思うのであれば、それはきっと時間計算量は定数時間O(1)なのでしょう。はたして、本当にそう思いますか?もし、そうではないと思うのなら、どの値にどのように依存しているのかを考え直してください。

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *