Производительность Java Big-O

Question

У меня есть вопрос о производительности моего проекта класса.

У меня около 5000 игровых объектов, сформированных из чтения текстового файла.У меня есть Treemap (называемое супердерево), которое содержит в качестве своих узлов Treemaps (мини-древовидные карты, я думаю).Это nodes/mini treemaps действие, стратегия, приключение, спорт, игровой титр и т. Д. В основном игровые жанры и эти мини-деревья будут содержать игровые объекты.Таким образом, supertree сам будет содержать, вероятно, 8 nodes/treemaps.

Когда я вставляю игровой объект, он определяет, к какому mini tree он придет и поместит его туда.Например, если я вставлю игру Super Mario World , она проверит, какой это жанр, и увидит, что это adventure, поэтому Super Mario World будет вставлен в adventuretree.

Таким образом, мой вопрос заключается в том, какова будет производительность, если в вопросе перечислены все action games, поскольку получение Treemap имеет значение O (log n)

Сначала в супердереве оно будетищите Action Node/Treemap, который будет принимать O (log n).

Затем, попав внутрь Action treemap, он получит все элементы, которые будут o (n log n) правильными?

То есть общая производительность log n * (n * log n) верна?Что хуже, чем o(n).

[править] Надеюсь, это немного прояснило мой пост.

Answer 1

В то время как получение на суперкарте равно O (n_categories), а для прохождения другой карты (с использованием итератора) должно быть O (n_games).Если ваша n_categories имеет верхнюю границу, скажем, 10 (потому что количество категорий не меняется при добавлении новых игр), вы можете считать поиск суперкарты O (1).

Поскольку подкарты могут иметьв большинстве записей n_games (когда все принадлежат к одной категории), перечисление всех игр типа action, таким образом, дает вам O (n_games).Не забывайте, что для перебора всех записей вам не нужно каждый раз вызывать get ().Это все равно что читать книгу и вместо того, чтобы переворачивать страницу, чтобы перейти со страницы 100 на 101, начать отсчет с начала и сосчитать до 101 ...

РЕДАКТИРОВАТЬ: поскольку в приведенном выше абзаце указано, что есликоличество категорий фиксировано, можно предположить, что поиск по категориям является O (1), кажется, трудно принять, позвольте мне сказать, что даже если вы настаиваете, что поиск по категориям равен O (log n_categories), это все равно дает O (n_games), так какпоиск категории должен быть выполнен только один раз.Затем вы перебираете результат, который равен O (n_games).Это приводит к O (n_games + log n_categories) = O (n_games).

Answer 2

Хорошо, во-первых, ваш big-O не изменится в зависимости от языка; вот почему люди используют биг-О (асимптотическую) нотацию.

Теперь подумайте о вашем алгоритме. Вы берете свое внешнее дерево и получаете каждый элемент, который действительно O (n ₀ lg n ₀ ) . Для каждого из этих узлов у вас есть O (n ₁ lg n ₁ ) . lg n отличаются только константой, поэтому их можно объединить, и вы получите O (n _o & times; n ₁ lg n) или O (n ² lg n) .

Answer 3

Пара комментариев относительно анализа ОП:

Я предполагаю, что вы уже создали свои древовидные карты / наборы и просто извлекаете элементы из законченного (предварительно обработанного) представления в памяти.

Допустим, n - количество жанров.Скажем, m - максимальное количество игр в жанре.

Сложность получения правильной «карты жанра» составляет O(lg n) (один get для супердерева).Сложность итерации по играм в этом жанре зависит от того, как вы это делаете:

 for (GameRef g : submap.keySet()) {
   // do something with supermap.get(g)
 }

Этот код дает O(m) операций 'get' со сложностью O(lg m) каждая, так что это O(m lg(m)).

Если вы сделаете это:

for (Map.Entry e : submap.entrySet()) {
   // do something with e.getValue()
}

, тогда сложность будет O(m) итераций цикла с постоянным (O(1)) доступом к значению по времени.

Использование второй итерации картыметод, ваша общая сложность составляет O(lg(n) + m)

Answer 4

Э-э, вы были правы до последнего абзаца.

Ваша общая сложность составляет O(n logn), logn для поиска типа и n для отображения всех значений этого типа.

Если вы говорите о перечислении всего, это определенно не O(n^2 logn), поскольку получение всех значений в вашем дереве линейно. Это было бы O(n^2).

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