Как я могу рассчитать сложность Big O моей программы?

Question

У меня вопрос с обозначением Big O.Скажем, у меня есть Java-программа, которая выполняет следующие действия:

1. Считывает массив целых чисел в HashMap, который отслеживает, сколько вхождений целых чисел существует в массиве.[1,2,3,1] будет [1-> 2, 2-> 1, 3-> 1].

2. Затем я беру ключи от HashMapи поместите их в Array:

   Set<Integer> keys = dictionary.keySet();
   Integer[] keysToSort = new Integer[keys.size()];
   keys.toArray(keysToSort);
   

3. Сортируйте keyArray, используя Arrays.sort.

4. Затем выполните итерацию поотсортировано keyArray получение соответствующего значения из HashMap, чтобы отобразить или отформатировать результаты.

Мне кажется, я знаю следующее:

• Шаг 1 - O (n)
• Шаг 3 - O (n log n), если верить Java API

• Шаг 4 - O (n)

• Шаг 2: При выполнении этого типа вычислений я должен знать, как Java реализует метод Set class toArray.Я бы предположил, что он выполняет итерацию HashMap, получая Keys.Если это так, я приму его O (n).

Если последовательные операции требуют, чтобы я добавил каждую часть, тогда окончательный расчет будет O (n + n · log n + n).+ n) = O (3n + n · log n).

Пропустить константы, и вы получите O (n + n log n) .Можно ли это еще уменьшить или я просто совершенно не прав?

Answer 1

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

Answer 2

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

Это может помочь вам найтиБольшой O сложных типов данных в Java: http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

Answer 3

Одна вещь, большая О, не говорит вам о том, насколько велик коэффициент масштабирования. Это также предполагает, что у вас есть идеальная машина. Это важно, потому что чтение из файла, вероятно, будет гораздо дороже, чем все, что вы делаете.

Если вы на самом деле рассчитываете это, вы получите что-то, что startup cost + read time. Стоимость запуска, вероятно, будет самой большой даже для одного миллиона записей. Время чтения будет зависеть от количества прочитанных байтов (т.е. длина чисел может иметь значение). Если у вас есть 100 миллионов, время чтения, вероятно, будет более важным. Если у вас есть один миллиард записей, много будет зависеть от количества уникальных записей, а не от общего количества записей. Количество уникальных записей ограничено ~ 2 млрд.

Кстати: чтобы сделать подсчет более эффективным, попробуйте TIntIntHashMap, который может свести к минимуму создание объекта, делая его в несколько раз быстрее.

Конечно, я говорю только о реальных машинах, которые большие O не учитывают;)

Я хочу сказать, что вы можете сделать большой O-расчет, но он не будет информативным в отношении того, как будет вести себя настоящее приложение.

Answer 4

Во-первых,

Шаг 1 равен O(n), если для вставки целых чисел в HashMap задано O(1).В Perl худший случай для вставки в хеш - O(N) для N элементов (он же амортизируется O(1)), и это если вы не учитываете длину ключа (что здесь допустимо).HashMap может быть менее эффективным в зависимости от того, как оно решает определенные проблемы.

Во-вторых,

O(N) равно O(N log N), поэтому O(N + N log N) равно O(N log N).

Answer 5

Вы правы, что немного беспокоитесь о шаге 2. Насколько я могу судить, Java API не определяет время выполнения этих операций.

Что касается O(n + n log n) Treebranch - это правильно.Вы можете уменьшить это значение до O(n log n) по той причине, что для некоторого базового значения n0 n log n > c*n forall c /= 0, n > n0 это, очевидно, имеет место, поскольку независимо от того, какое число вы выбрали для c, вы можете использовать n0, установленный на 2^c+1

Answer 6

• Шаг 2 занимает O ( емкость карты ).

• Шаг 1 и 4 может испортиться, если у вас много ключейс тем же хеш-кодом (т. е. O ( число этих ключей ) для одного поиска или изменения, умножьте на количество этих поисков / изменений).

• O(n + n · log n) = O (n · log n)