Big O при сложении разных подпрограмм

Question

Допустим, у меня есть подпрограмма, которая сканирует весь список из n элементов 3 раза, выполняет сортировку по размеру, а затем выполняет поиск, сортирующий список n раз. Сканирования выполняются за O (n) раз, сортировка, которую я назову O (n log (n)), а поиск n раз - O (n log (n)). Если мы сложим все 3 вместе, это только даст нам худший случай 3 - значение (я) n log (n), или семантика позволяет добавить время?

Я уверен, что теперь, когда я напечатал это, ответ n log (n), но я мог бы также подтвердить теперь, что я напечатал его:)

Answer 1

Сумма действительно самая большая из трех для Big-O.

Причина в том, что временная сложность вашей функции

(n) => 3n + nlogn + nlogn

, что

(n) => 3n + 2nlogn

Эта функция ограничена сверху 3nlogn, поэтому она находится в O (n log n).

Вы можете выбрать любую константу. Я просто выбрал 3, потому что это была хорошая асимптотическая верхняя граница.

Answer 2

Вы правы.Когда n становится действительно большим, n log (n) доминирует над 3n.

Answer 3

Как сказал Рэй, ответ действительно O (n log (n)).Интересная часть этого вопроса заключается в том, что не имеет значения, как вы на это смотрите: означает ли добавление «фактическое добавление» или «наихудший случай».Давайте докажем, что эти два взгляда на это дают одинаковый результат.

Пусть f (n) и g (n) - функции, и без ограничения общности предположим, что f - это O (g).(Неформально, что g «хуже», чем f.) Тогда по определению существуют такие константы M и k, что f (n) k.Если мы посмотрим на «худший случай», мы ожидаем, что f (n) + g (n) равно O (g (n)).Теперь, взглянув на него «фактическим сложением» и специализируясь на случае, когда n> k, мы имеем f (n) + g (n)

Answer 4

Да, это будет наихудший случай, поскольку O-нотация - это просто асимптотическая производительность.

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