0

以下の関数の時間の複雑さを分析しようとしています。この関数は、文字列が他の文字列で構成されているかどうかを確認するために使用されます。

set<string> s; // s has been initialized and stores all the strings
bool fun(string word) {
    int len = word.size();

    // something else that can also return true or false with O(1) complexity

    for (int i=1; i<=len; ++i) {
       string prefix = word.substr(0,i);
       string suffix = word.substr(i);
       if (prefix in s && fun(suffix))
           return true;
       else
           return false;
    }
}

O(n)時間の複雑さは、nが単語の長さであると思います（そうですか？）。しかし、再帰はループ内にあるため、それを証明する方法がわかりません。

編集：

このコードは正しいコードではありませんC++(例: prefix in s)。この関数のアイデアを示すだけで、その時間計算量を分析する方法を知りたい

4

2 に答える 2

0

他の人が指摘したバグを修正したと仮定すると、i値は文字列が分割されている場所です (それぞれiが左端の分割点であり、次に の右側のすべてを再帰しますi)。これは、再帰を巻き戻そうとすると、n-1さまざまな分割点まで調べて、各部分文字列が有効な単語かどうかを尋ねていることを意味します。の先頭にwordセットの要素が多くない場合は問題ありません。その場合、再帰をスキップできます。しかし、最悪の場合、prefix in sは常に真であり、n-1分割点のすべての可能なサブセットを試します。これにより、2^{n-1}さまざまな分割セットが得られ、そのような各セットの長さを掛けます。

于 2013-08-25T17:41:51.267 に答える