![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
アルゴリズムの時間計算量、空間計算量に関する質問です。
次のプログラムはレーベンシュタイン距離のアルゴリズムによって、文字列の編集距離を求めるものです。
また、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のフラグを格納するだけなのでビット単位でフラグを格納すればよいと思ったのですが、これは空間計算量の削減だと言えるでしょうか?
よろしくお願いします。
No.1ベストアンサー
- 回答日時:
オーダーの計算は、数が増えたときに一番影響のある項に注目します。
時間は 、次の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)とできるのですね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語を使用したプログラミング...
-
Scilabでのプログラミング
-
[急募]Pythonについてです。
-
C言語で電卓を作成する。修正お...
-
排他的論理和 BCC(水平パリテ...
-
C言語で N行*M列 の逆行列を求...
-
VB6.0でのバイナリデータの扱い...
-
スライムがつぶれていく様子を...
-
引き放し法による除算アルゴリ...
-
階乗のマクロ
-
逆行列求めたい
-
VBAの再計算が反映されない件に...
-
関数を使わないで日付の計算を...
-
小数点の変換
-
verilog ~ や() について特...
-
MT4 固まる
-
プログラムの質問
-
Javaでのある数の小数点乗に...
-
EXCELなどで「返す」という表現
-
計算量の少ないn乗根の求め方
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
パソコン
-
VBAで関数をつくる
-
階乗のマクロ
-
EXCELなどで「返す」という表現
-
排他的論理和 BCC(水平パリテ...
-
バッチファイルでウインドウを...
-
変化させるセルが変化しない
-
VBAの再計算が反映されない件に...
-
引き放し法による除算アルゴリ...
-
モジュラス103の計算とは何でし...
-
Visual C++でdebugとreleaseで...
-
エクセルで特定のセルのみを任...
-
数値計算の高速化 (cos, sin, exp)
-
傾いた四角形内の範囲の条件式
-
VBでReplace
-
骨折リスク評価のFRAXについて...
-
アドオン利率を実質年率に変換
-
入射角反射角
-
C言語についてです。 再帰を使...
おすすめ情報
回答ありがとうございます。
D[i][j]に関しては勘違いしていました。フラグではなく編集した回数ですね。
では、編集距離を削減する方法として、動的計画法を用いればO(n)になると思ったのですがどうでしょうか?