简单算法分析

Question

我试图将一个算法降低到至少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中唯一的字符是"0"和"1"。例如，如果字符串为"001001"，则模式为"001"，并发生两次。字符串也是均匀的。话虽如此，语法和功能都与这个问题无关。所有基本操作都被认为需要O(1) (常数)时间，这几乎就是这段代码的全部。

Note2:

我这么做是为了家庭作业。但家庭作业的问题只是让算法工作，我已经做了。降低复杂性只是额外的练习。

如有任何帮助或指导，将不胜感激！

Answer 1

这很容易，只需检查长度是否除以总长度(必须如此，如果L不除总长度，字符串不能是长度L的重复模式)，如果不除以总长度，则不要运行内循环。除数的上限为2sqrt(n)，因此这保证了O(Nsqrt(N))。

如果你想知道为什么，一个数字可以有的最大除数是每个数最多平方(N)，然后对于每一个数字x，N/x，所以在2sqrt(N)下。

当然，在现实中，数字的除数要少得多，除了12，实际上所有的除数: 1,2,3 (每一个数不超过平方)，12/1，12/2，12/3 (逆)。

有两个内环，其中一个是L次，另一个是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，但它在数学上保证是<2 2sqrt(N)。通过在几百万个字符的字符串上运行它，您也可以看到这一点--它将快速工作。

Answer 2

我认为您的内环不能降到O(sqrt(n))，因为您必须将字符串开头的所有字符与由外部循环控制其值的特定索引i中的所有字符进行比较。