Исходные данные: файл, с одной единственной колонкой, в которой находятся числа от 0 до Integer.MAX_INT.
Нужно написать алгоритм, который будет подсчитывать количество повторений цифр в этом файле.
Будем считать, что у нас бесконечное количество памяти. Напишем такой метод, а по завершению просто распечатаем entries у этой коллекции:
final Map<Integer, Integer> 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) т.к. она растет быстрее чем логарифм.