Исходные данные: файл, с одной единственной колонкой, в которой находятся числа от 0 до Integer.MAX_INT. Нужно написать алгоритм, который будет подсчитывать количество повторений цифр в этом файле.
Будем считать, что у нас бесконечное количество памяти. Напишем такой метод, а по завершению просто распечатаем entries у этой коллекции: final Map map = new HashMap<>() //---- public void add(Integer digit) { Integer quantity = map.get(digit) if (quantity == null) { map.put(digit, 1) } else { map.put(digit, ++quantity) } } Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1). Вопрос №2: Общая сложность системы будет равна O(n) ?
А теперь заменим HashMap на TreeMap: Вопрос №3: Сложность метода будет равна O(log(n)) ? Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) + O(log(n)) -> O(n) т.к. она растет быстрее чем логарифм.
Ответ Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1). Да, с оговоркой про то, что вставка/поиск в хеше на неудачных данных может деградировать до O(n), Здесь стоит оговориться, что для хеша с адекватной хеш-функции, подходящем размере таблицы и при квазислучайных входных данных вероятность худшего случая пренебрежимо мала, но всегда существует такой набор данных, который этот случай даст. Зачастую его можно специально подобрать и даже использовать для DOS-атаки. Кроме того при обычной реализации динамически расширяемой хеш-таблицы map.put может потребовать перестроения индекса хеша, сложность которого также O(n), но этого можно избежать заранее выделив под таблицу достаточный объём данных. Вопрос №2: Общая сложность системы будет равна O(n) ? Да, с аналогичной оговоркой, в худшем случае время составит O(n²). В случае динамически расширяемой хеш таблицы в типовой реализации также необходимо увеличивать её размер и пересчитывать хеши порядка log(N) раз и время соответственно может ухудшиться до O(N*log(N)) в среднем случае, но этот эффект будет проявляться только для относительно больших N и зачастую его так или иначе можно нивелировать (выделяя заведомо больше памяти).
А теперь заменим HashMap на TreeMap: Вопрос №3: Сложность метода будет равна O(log(n)) ? Да Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) + O(log(n)) -> O(n) т.к. она растет быстрее чем логарифм. Нет, здесь не верно: нужно N раз сделать операцию сложностью O(log(n)), где n в среднем равно N/2. т.е. сложность будет O(N*log(N)).