#<tex>a[k + 1] \notin candidates</tex> и <tex>candidates.size() = K - 1</tex><p>Размер <tex>candidates</tex> на данном шаге может только уменьшиться. Садим группу. Если какой-то элемент был удален на текущем шаге, то, значит, он встречался не более, чем <tex>(k + 1) / K</tex> раз, т.к. мы могли успеть посадить максимум <tex>(k + 1) / K</tex> групп. Тогда удаление данного элемента из candidates ни к чему плохому не приведет. Инвариант выполняется.</p>
Пусть операции со словарем выполняются Рассмотрим среднее количество обращений к словарю за <tex>O(X)</tex>. Тогда покажем, что в среднем итерация выполняется тоже за <tex>O(X)</tex>. Заметим, что увеличение счетчика эквивалентно добавлению элемента в <tex>candidates</tex>, а уменьшение счетчика - удалению элементаодну итерацию. Тогда на кажой На каждой итерации происходят добавления или удаления элементов. В рамках одной итерации мы добавляем происходит не более <tex>1</tex> элементаувеличения счетчика. Тогда, количество элементов за все время, происходит не превышает более <tex>N</tex>увеличений. МаксимумТак как количество уменьшений счетчика не может превышать количество увеличений, что мы можем сделать - это добавить то всего происходит не более <tex>N2N</tex> элементов и их же удалитьобращений к словарю. Получается <tex>O(N)</tex> операций. Всего итераций <tex>N</tex> штук. Тогда на каждую итерацию в среднем приходится <tex>O(1)</tex> операций и итоговая Следовательно, сложность одной итерации составляет <tex>O(X1)</tex>.
Получается, при реализации словаря на основе хэш-таблиц, каждая итерация в среднем выполняется за <tex>O(1)</tex>. Итоговая сложность <tex>O(N)</tex> с дополнительной памятью <tex>O(K)</tex>.
