アルゴリズムの時間計算量、空間計算量について

アルゴリズムの時間計算量、空間計算量に関する質問です。
次のプログラムはレーベンシュタイン距離のアルゴリズムによって、文字列の編集距離を求めるものです。
また、MIN3という関数は引数の中の最小値を返します。

int dist_table(char a[],int m,char b[],int n){
int i,j,D[m+1][n+1];

for(i=0;i<=m;++i) D[i][0]=i;
for(j=0;i<=n;++j) D[0][j]=j;
for(i=0;i<=m;++i){
for(j=1;j<=n;++j){
int d=0;
if(a[i-1] != b[j-1])d=1;
D[i][j]=MIN3(D[i-1][j-1]+d,D[i-1][j]+1,D[i][j-1]+1);
}
}
return D[m][n]
}

このプログラムの時間計算量と空間計算量の漸近的評価を求めたいのですが、
どちらもO(m*n)だと思ったのですが合っているでしょうか？
また、テストなどでこのような問題が出題された場合各オーダーを求めるまでのプロセスをどのように示せばいいのでしょうか？よろしければこの問題を例にプロセスを示していただきたいです。
また、空間計算量を削減するためにはどのような改良を加えればよいのでしょうか？自分は、D[m+1][n+1]は0,1のフラグを格納するだけなのでビット単位でフラグを格納すればよいと思ったのですが、これは空間計算量の削減だと言えるでしょうか？
よろしくお願いします。

質問者からの補足コメント

• 回答ありがとうございます。
  D[i][j]に関しては勘違いしていました。フラグではなく編集した回数ですね。
  では、編集距離を削減する方法として、動的計画法を用いればO(n)になると思ったのですがどうでしょうか？

  No.1の回答に寄せられた補足コメントです。 補足日時：2015/08/07 12:56

No.1 ベストアンサー 回答者： kmee 回答日時： 2015/08/07 07:39

オーダーの計算は、数が増えたときに一番影響のある項に注目します。

時間は 、次の3つの和になります。
for(i=0;i<=m;++i) D[i][0]=i; のループ回数
for(j=0;i<=n;++j) D[0][j]=j; のループ回数
for(i=0;i<=m;++i) for(j=1;j<=n;++j){〜 のループ回数
つまり
m + n + m*n
です。
※ より正確には、ループ内での実行時間を考慮したもの、例えば、命令数で
m + n + 3*m*n
とかになりますが、オーダーを求めるときは、定数倍は無視します。

このうち、値が大きくなったときに一番影響のあるのは、m*n ですから O(m*n) であっています。


空間も同じように使用するメモリサイズを見積ります。


> ビット単位でフラグを格納すれば

2つの点で間違いです。
1)仮にフラグだとしても、オーダーを考えるときは定数倍は無視します。
　1ビットのときは
O( 1 * (m+1) * (n+1) ) = O( m*n + m + n + 1 ) = O( m*n )
　32ビットのときは
O( 32 * (m+1) * (n+1) ) = O( 32 * m*n + 32 * m + 32 * n + 32 ) = O( m*n )
で、オーダーは同じです。

実際の動作では、この定数倍や切り捨てた項の影響が無視できない場面も多いですが、オーダーを考えるときには無視します。


2)プログラムをよく読んでください。Dはフラグではありません。

この回答へのお礼

すみません、今の補足間違えでした。
D[i][j]=MIN3(D[i-1][j-1]+d,D[i-1][j]+1,D[i][j-1]+1);
より、D[* , j-2] , D[* , j-3] ... は計算の必要がないからO(n)とできるのですね。

お礼日時：2015/08/07 13:27