Для л oop - биг-о - PullRequest
Новая
       3

Для л oop - биг-о

0 голосов
/ 06 апреля 2020

Я пытаюсь решить эту проблему из книги и изо всех сил пытаюсь понять ответ. 

for (i = 0; i < N; ++i) {
   if ((i % 2) == 0) {
      outVal[i] = inVals[i] * i
   }
}

вот как я разбил его: I = 0 -> выполняется 1 раз

I

оператор if содержит 2 операнда, поэтому теперь мы находимся в 4n + 1.

содержимое оператора if выполняется только n / 2 раза, поэтому мы находятся в 4n + 1 + n / 2

однако, большой O отбрасывает эти термины, оставляя нас с N в качестве ответа

Вот что я не понимаю: объяснение ответа моей проблемы говорит это: outVal [i] = inVals [i] * i; выполняет каждую другую итерацию l oop, поэтому общее количество операций включает в себя: 1 операцию в начале итерации l oop, 3 операции в каждой итерации l oop, 1 операцию в каждой итерации l oop и 1 операция для окончательной проверки состояния l oop.

как в l oop есть только 3 операции? Я насчитал 4, как указано выше. Пожалуйста, дайте мне знать обоснование этого.

1 Ответ

0 голосов
/ 07 апреля 2020

Сложность измеряется временем / пространством, которое вы берете для выполнения sh задачи. i<N и ++i не требуют времени, зависящего от вашей пространственной переменной N (длина l oop).

Вы не должны добавлять количество выполненных операций и суммировать их все - вместо этого вы должны выбрать тот, который занимает больше времени или пространства, поскольку это является узким местом алгоритма. В al oop msot операций выполняется одинаковое время, поэтому мы используем длину l oop в качестве пространства или времени сложности.

l oop будет выполняться N раз, так что его сложность -> O (n)

Внутри l oop область действия if будет выполняться N / 2 раза, как вы правильно сказали -> O (n / 2)

Но эти прогоны уже добавлены к первым l oop итерациям. Вы не добавите его, так как внешних итераций нет.

Итак, сложность алгоритма составляет O (n).

Что касается операций, 3:

  • Проверка I
  • Добавление 1 к I
  • Условие if

Все они выполняются на каждой итерации.

...