3

アルゴリズムを少なくともO（n ^（3/2））の複雑さまで下げようとしています。アルゴリズムは次のとおりです。

function( string s, int n )
{
    bool result = false;
    int position = 0;
    for( int i = 0; i < n/2; i++ )
    {
        position = 0;
        for( int j = i+1; j < n; j++ )
        {
            if( s[j] != s[position] ) break;        
            if( j == n ) result = true;
            if( position == i ) position = 0;
            else position++;        
        }
        if(result) break;       
    }
    return result;
}

最初のforループはn/2回繰り返されます。これは、O（n）の複雑さです。内部のforループを最大でO（sqrt（n））にする必要があるため、アルゴリズム全体にO（n ^（3/2））の複雑さが与えられます。ネストされたforループが必要な複雑さであるかどうかを判断するのに苦労しています。

注：
nは文字列のサイズです。この関数は基本的に、文字列sで繰り返しパターンが発生するかどうかを確認します。sの文字は"0"とだけ"1"です。たとえば、文字列が"001001"である場合、パターンはで"001"あり、2回発生します。文字列も偶数です。そうは言っても、構文と機能はこの質問には関係ありません。すべての基本的なアクションは、O（1）（定数）時間かかると見なされます。これは、このコードのほぼ全体です。

注2：
宿題のためにやっています。しかし、宿題の質問は、私が行ったアルゴリズムを機能させることだけでした。複雑さを軽減することは、実践するための余分な作業にすぎません。

どんな助けやガイダンスもいただければ幸いです！

4

2 に答える 2

2

非常に簡単です。長さが全長を除算するかどうかを確認するだけで（Lが全長を除算しない場合、文字列は長さLの繰り返しパターンになることはできません）、内部ループを実行しないでください。そうではありません...除数の数の上限は2sqrt（n）であるため、これによりO（Nsqrt（N））が保証されます。

理由がわからない場合は、ある数が持つことができる除数の最大数は、sqrt（n）までのすべての数であり、それらの数ごとにx、N/xです。したがって、2sqrt（N）の下で。

もちろん、実際には、1、2、3（sqrtまでのすべての数）、12 / 1、12 / 2、12 / 3（逆）の12を除いて、数値の除数ははるかに少なくなります。

2つの内部ループがありますが、1つはL回実行され、もう1つはN / L回実行されるため、内部ループはO（N）になります。

    static bool f(string s)
    {
        int n = s.Length;
        for (int l = n / 2; l >= 1; l--)
        {
            if (n % l != 0) continue;
            bool d = true;
            for (int o = 0; o < l; o++)
            {
                char f = s[o];
                for (int p = l; p < n; p += l)
                    if (s[p + o] != f) d = false;
            }
            if (d == true) return true;
        }
        return false;
    }

キーラインは次のとおりです。

if (n % l != 0) continue;

それ以外の場合はO（N ^ 2）になります。

外側のループは一見N/2のように見えるかもしれませんが、数学的には<2sqrt（N）であることが保証されています。これは、数百万文字の文字列で実行することでも確認できます。これはすぐに機能します。

于 2012-05-17T12:31:25.250 に答える
0

文字列の先頭からすべての文字を、値が外部ループによって制御される特定のインデックスiの文字と比較する必要があるため、内部ループをO（sqrt（n））に下げることはできないと思います。

于 2012-05-17T02:28:35.703 に答える