Две петли, разделенные на одну L oop, это нормально?

Question

Ниже приведено значение al oop для двух функций:

const foos = [1, 2, 3, 4, 5];

for ( let foo of foos ) {
  func1(foo);
  func2(foo);
}

Я хочу разделить его на две части. Из-за разделения семанти c кода.

const foos = [1, 2, 3, 4, 5];

for ( let foo of foos ) {
  func1(foo);
}

for ( let foo of foos ) {
  func2(foo);
}

Оставляя в стороне, почему я должен это делать, я задаюсь вопросом, не снижается ли производительность. В обоих случаях это нормально, потому что это O (n), верно?

Answer 1

Это изменение не влияет на сложность времени. Итак, если предположить, что func1 и func2 равны O(1), тогда ваша временная сложность все еще равна O(n) (где n = len(foos)).

Хотя вас может беспокоить то, что код 2 фрагменты не совпадают. В зависимости от вашей реализации func1 и func2 вы можете получить разные результаты.
В то время как первый делает:

func1(1);
func2(1);
func1(2);
func2(2);
...

Второй делает:

func1(1);
func1(2);
...
func2(1);
func2(2);
...

Интуитивно понятное объяснение:
Вы изменили с: O(n * (1 + 1)) = O(n * 2) = O(2n) = O(n)
операций на: O((n * 1) + (n * 1)) = O(n + n) = O(2n) = O(n).

Answer 2

Хотя это может показаться не так, итерация по списку имеет свою стоимость. Это потому, что мы должны повторно вызывать .next() в списке, чтобы получить следующий элемент. Для массива это будет постоянное время, но для других перечислимых структур это может стоить дороже в зависимости от того, как хранятся данные (например, хэш-карта).

Скажем, стоимость перечисления f(N), где N - размер коллекции. Предположим для этого примера, что func1 и func2 работают в постоянное время k.

Сложность обоих одинакова: O(N*f(N)+N*k)=O(N*f(N))

Однако истинная стоимость отличается , Вам нужно сделать дополнительные N*f(N) операции. Переход на один l oop вместо двух может сэкономить вам заметное время в зависимости от f(N), но общая сложность останется прежней.