0

文字列が配列内の任意の数の文字列の連結であるかどうかをチェックするアルゴリズムを作成しました (文字列を複数回使用できます)。アルゴリズムの実行時間を正確に把握するのに苦労しています。

問題の文字列を配列内のすべての単語に対してチェックし、インデックス 0 から始まる元の文字列の部分文字列である単語を見つけたら、配列内のすべての単語に対して残りの部分文字列もチェックします。何かが欠けていない限り、これは O(n^n) だと思います。

def check_concat(str,substr,words)
  if substr == ""
    return false
  end

  words.each do |word|
    if word == substr && str != substr
      return true
    end
    if substr.index(word) == 0
      if check_concat(str,substr[word.length..-1],words)
        return true
      end
    end
  end
  return false
end
4

1 に答える 1

1

m wordsメインの文字列が含まれておりn words、検索対象の配列にあると仮定しましょう。最悪の場合、メイン文字列の各単語を配列の各単語でチェックする必要があります。これがmn時間です。したがって、関数の時間計算量は ですO(mn)。

たとえば、メインの文字列は"Hello Hello Hello Hello Hello". チェックする配列には、次の単語が含まれています'Hai', 'Fine', 'Hello'。その場合、関数は合計 15 回の比較を必要とします。

于 2013-05-13T07:12:49.540 に答える