Простой алгоритм анализа

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; 
} 

Первый для цикла будет итерации N/2 раза, что О (п) сложность. Мне нужно, чтобы внутри for-loop было не более O (sqrt (n)), тем самым придавая целому алгоритму сложность O (n^(3/2)). Я с трудом пытаюсь понять, нужна ли мне вложенная петля для нужной сложности.

Примечание:
n - размер строки. Функция в основном проверяет, существует ли повторяющийся шаблон в строке s. Единственными символами в s являются "0" и "1". Например, если строка равна "001001", тогда шаблон равен "001" и встречается дважды. Строка также четная. При этом синтаксис и функциональность не имеют отношения к этому вопросу. Считается, что все базовые действия принимают O (1) (постоянное) время, которое в значительной степени соответствует всему этому коду.

Примечание2:
Я делаю это для выполнения домашних заданий. Но вопрос о домашнем задании состоял в том, чтобы заставить работать алгоритм, который я сделал. Устранение сложности - это просто дополнительная работа для практики.

Любая помощь или руководство будут оценены!

Answer 1

Это очень просто, просто проверьте, не делит ли длина общую длину (она должна быть, строка не может быть повторяющимся образцом длины 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). Который вы также можете увидеть, запустив его на строку в несколько миллионов символов - он будет работать быстро.

Answer 2

Я думаю, что ваша внутренняя петля не может быть сведена до O (sqrt (n)), поскольку вам нужно сравнить все символы от начала строки до значений из определенного индекса i, значение которого определяется внешним циклом.