Сравнение сложности алгоритма

Question

Пожалуйста, помогите мне сравнить сложность двух алгоритмов.

1. O(N+1000) + O(M*log(M))
2. O(N*5) + O(2000)

N = 100000 М = 100

Не могу понять, что мне делать с O(...)? Могу ли я оставить это? И просто делай ...

(N+1000) + (M*log(M)) = 101200
(N*5) + 2000 = 502000

Это правильно?

Спасибо

ОБНОВЛЕНО

У меня есть задача, и у меня есть два возможных решения. Сложность алгоритма первого решения O(N) + O(M log(M)), см. http://code.google.com/p/redis/wiki/ZunionstoreCommand; второе решение состоит из двух алгоритмов со сложностями O(N) http://code.google.com/p/redis/wiki/SunionCommand и O(N*M) http://code.google.com/p/redis/wiki/SinterCommand. Я думал, что могу заменить N и M на значения реального мира для сравнения скорости обоих решений. *

Answer 1

Обозначение Big-O не говорит вам, насколько быстрым является конкретный алгоритм для определенного набора данных, - оно говорит об асимптотической производительности.В записи Big-O вы можете игнорировать константы и постоянные коэффициенты:

1. O (N + M * log (M))
2. O (N)

Теперь вы можете видеть, что второй алгоритм имеет лучшую асимптотическую производительность.

Answer 2

При сравнении сложности в общем случае вы игнорируете постоянные значения.

O(N+1000 + M*log(M))

становится

O(N + M*log(M))

, а

O(N*5 + 2000)

становится

O(N)

---

Теперь, если вы точно знаете, что это значения, которые вы будете иметь для M и N, вы можете выполнить математику и быть более точным, но вам также нужно будет знать, сколько времени занимает каждая операция. Нотация используется для масштабирования, а не для того, чтобы алгоритм работал в конкретном случае. Если ваши данные такие статические, вы можете просто запустить оба алгоритма и посмотреть, какой из них возвращается быстрее.

Редактировать: как кто-то еще указывал, правильная запись - это не сумма двух больших осей, а скорее большая сумма суммы.

Answer 3

Собственно говоря, O(N+1000) + O(M*log(M)) на самом деле не имеет никакого смысла, так как O (f (n)) - это набор всех функций g (n), таких, что бла-бла, ищите это в большой белой книге, бла .. Энди, вы не можете добавлять наборы функций.

Да, это обычное злоупотребление нотацией, но, будучи педантичным, (и преподавая этот класс несколько раз), я вынужден указать, что правильный ответ - "Му".

Answer 4

Мне не очень нравится вопрос, на который вас просят ответить.

То, что сказал Марк Брайерс, правильно: вы можете игнорировать константы с обозначением Big-O.

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

Теперьпо этой причине я нахожу крайне странным, что в Big-O будет добавление или постоянное умножение - вы должны избавиться от тех, кто имеет обозначение Big-O ... в этом весь смысл.Это именно то, как вопрос был задан?Кроме того, алгоритмы не должны описываться с помощью двух Big-O каждый (это должен быть только один, как указано и объяснено Питером Леппертом).

Я бы ответил на это так:избавьтесь от констант, поскольку их там вообще не должно быть, а затем оцените их по n и m и сравните.