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"并且出现两次。字符串也是偶数。话虽如此，语法和功能与这个问题无关。所有基本操作都被认为需要 O(1)（恒定）时间，这几乎是这段代码的全部内容。

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

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

4

2 回答 2

2

这很容易，只需检查长度是否除以总长度（它必须，如果 L 不除总长度，则字符串不能是长度 L 的重复模式）并且如果不运行内部循环它没有...除数的上限是 2sqrt(n)，所以这保证了 O(Nsqrt(N))。

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

当然，数字在现实中的除数要少得多，除了 12 实际上具有所有除数：1、2、3（每个数字都达到 sqrt）、12/1、12/2、12/3（倒数）。

有 2 个内部循环，但一个运行 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，但从数学上可以保证它小于 2sqrt(N)。您还可以通过在几百万个字符的字符串上运行它来看到 - 它会很快工作。

于 2012-05-17T12:31:25.250 回答
0

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

于 2012-05-17T02:28:35.703 回答