Как посчитать сложность алгоритма?

#java #алгоритм #сложность

Исходные данные: файл, с одной единственной колонкой, в которой находятся числа от
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

Вопрос №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)).


Ответ 2

Да, все правильно. Перебор коллекции это всегда O(N), потому выполнение метода add
и печать всех элементов это O(N). В первом случае сложность функции add - O(1) в среднем(а
в худшем O(N), потому что в хеш-таблице могут быть коллизии), а во втором - O(log N)
в худшем случае потому что TreeMap это сбалансированное бинарное дерево поиска.

UPD К сожалению слегка ошибся, забыл что во втором случае мы N раз добавляем за логарифм
потому сложность O(N log N)


Ответ 3

"Нужно написать алгоритм, который будет подсчитывать количество повторений цифр в
этом файле."

Скажите на милость, зачем вам вообще какие-то HashMap, если вас интересуют цифры?
Массив из 10 целых, и вперед, чтение по одному символу, если цифра - увеличивать соответствующий
элемент массива. Все. Чистое O(размер файла).

Вы верно переписали задание? Просто в условии у вас одно задача, а решаете вы совсем
другую.