Что такое большое количество сложенных петель? - PullRequest
Новая
       19

Что такое большое количество сложенных петель?

0 голосов
/ 06 декабря 2018

Если у вас есть функция, которая имеет несколько не вложенных циклов, меняет ли это сложность времени от O (N)?Я знаю, что если бы вы написали функцию, которая регистрирует каждый элемент массива, вы могли бы сделать это с помощью одного цикла, давая вам большое O (N), но если вы добавите больше циклов, это даст вам большое значениеO (N * количество петель)?

Рассмотрим эту функцию сжатия строк, какова ее значимость, учитывая, что она зацикливается на строке несколько раз: 

 function compression(string) {
  let compressed = "";
  let map = {

  }

  string.split("").forEach((e, i) => {
    map[e] = 0;
  })

  string.split("").forEach((e, i) => {
    map[e] += 1;
  })

  for (var element in map) {
    compressed += element + map[element];
  }
  if (compressed.length > string.length) {
    return string;
  } else {
    return compressed;
  }
}

Ответы [ 2 ]

0 голосов
/ 06 декабря 2018

По определению, алгоритм равен O(N), когда число f(N) элементарных операций, которое ему необходимо выполнить на входе размера N, удовлетворяет: 

f(N) <= C.N    ; N >= N0

для некоторой положительной константы C, независимо от N, где N0 - некоторый начальный индекс, также не зависящий от N.

Допустим, вы объединяете три цикла, каждый из которых O(N).Согласно определению у вас будет три пары констант (C1, N1), (C2, N2) и (C3, N3), такие что 

loop1(N) <= C1.N  ; N >= N1
loop2(N) <= C2.N  ; N >= N2
loop3(N) <= C3.N  ; N >= N3

Тогда, 

loop1(N) + loop2(N) + loop3(N) <= (C1 + C2 + C3)N       ; N >= max(N1,N2,N3)

и определение O(N) сохраняется для константы C = C1+C2+C3 и начального индекса N0 = max(N1,N2,N3).Следовательно, конкатенация постоянного числа алгоритмов O(N) снова равна O(N), потому что константы C и N0 не зависят от N.

0 голосов
/ 06 декабря 2018

Что касается не вложенных циклов, подобных тем, которые вы показали, сложность времени остается O (N).Это связано с тем, что число циклов является константой - например, если вы пробегаете N элементов 3 раза, в большой записи O вы можете отбросить константу.Следовательно, это все равно O (N).

Примечание. Предполагается, что число циклов является постоянным.Если количество циклов каким-либо образом зависит от количества элементов, вам нужно будет учесть это соотношение.

...