単純なアルゴリズムによる支援

Question

私は現在、Amazonから購入した本のアルゴリズムを学習していますが、世界で最悪の本ですが、例を示していますが、解答の仕方を決定的に示していません。

ので、私が持っている最初の質問は、

Prefix-Match(T[1..n], P[1..m]) { 
i := 1 // point to current position in T[] 
while(i <= n) { 
// find a match for first character of P 
while(i <= n && T[i] != P[1]) i++ 
if (i > n) return; // quit 
len := 1 
// match as much as possible 
while(len < m && i+len <= n && T[i+len] == P[1+len]) len++ 
output i, len 
i++ 
} 

このプログラムの出力はであるものであればT = [A、B、A、B、C、B]およびP = [Aであります、b、a]

第2に、mとnに関してアルゴリズムの時間の複雑さをどのように調整するのですか？

Answer 1

まず最初にすべての質問：あなたは何について話していますか？これがまさにそのコードサンプルであれば、恐ろしいことです...

今答え：

• この関数は、Tのすべての要素を通る（これは最初whileループである）、
• それはPでの最初の要素の最初の発生を発見この場合、T[1] == P[1]（TにPの最初の要素が含まれておらず、単に関数が返る場合）、
• のようになるため、テーブルの最後から最後までの範囲を調べます。 Tはiから始まり、の次の要素と一致します（それは要素T[i+1]を取り、それがT[i+2]とP[3]でP[2]と同じに一致するかどうかをチェックすることを意味する）、
• それは、それが発見し、それが見つかったどのように多くの試合iを印刷します。

基本的に、この関数は、Pと一致Tのすべての部分集合を見つけ、正確な出力は次のようになります

1, 3 
3, 2 
6, 2 

Tldr：最初の番号は要素P[1]が内される指標でありますテーブルTと2番目の数字は、テーブルPのそれに対応する要素の後ろの要素の数です。

しかし、著者の意図は何か分かりません - 見つかったサブセットが完全にPセットに一致する、すなわち、取った場合：T = [a,c,a]とP = [a,b,a]の場合でも、出力は1,3になります。見つかった部分集合の次の要素がTの部分集合と異なる場合、ループを壊す要素はありません。

時間の複雑さについては、Web上に多数の記事があります。本が欲しいなら、CLRS Introduction to AlgorithmsまたはAlgorithm Design Manualを参考にしてください。

Answer 2

このプログラムの出力はどうであろうT = [A、B、A、B、C、B]及びP = [A、B、A]は？

これを行う初心者の方法は、ペンと紙をとり、各変数のスロットを作ることです。そして、コンピュータのように各ステートメントを実行し、ステートメント実行の結果として書かれた変数値を変更します。

あなたは上記のようにT及びPで始まる場合、最初のTの値を設定し、n、pおよびmはiためのスロットでi := 1書き込み1通過するであろうたとえば、あなたはwhile(i <= n) {を通過する（1なぜなら< nなど）

これを数回実行すると、はるかに高速に処理できるようになります。

私は現在、Amazonから購入した本のアルゴリズムを学習していますが、それは世界で最悪の本ですが、例を示していますが、答えを出す方法を決定的に示していません。

ので、私が持っている最初の質問は、このプログラムの出力がどうなるか

Prefix-Match(T[1..n], P[1..m]) { 
    i := 1 // point to current position in T[] 
    while(i <= n) { 
    // find a match for first character of P 
    while(i <= n && T[i] != P[1]) i++ 
    if (i > n) return; // quit 
    len := 1 
    // match as much as possible 
    while(len < m && i+len <= n && T[i+len] == P[1+len]) len++ 
    output i, len 
    i++ 
} 

は= [A、B、A、B、C、B]およびP = [A Tであります、b、a]

そして第二に、私は、mとnの 用語で、アルゴリズムの時間の複雑さをうまくありませんか？

：私はあなたがワークアウト時間の複雑さへの準備ができている確信し、しかしについてどのように考えるか、mとnのアルゴリズム（あるいはどのくらいの時間が手で行うに行くことができます）で撮影した最大時間に影響を与えていないです

• mに依存しますか？
• nに依存しますか？
• もし両方に依存するのであれば、m+n以上の関数はm*nのようになりますか？つまり、同じサイズのTと倍のサイズのPの場合、2倍の時間がかかりますか？