我正在尝试将算法降低到至少 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:
我这样做是为了家庭作业。但是作业问题只是让算法正常工作,我已经做到了。降低复杂性只是额外的练习。
任何帮助或指导将不胜感激!