Последнее, что нам осталось обсудить, в этой теме — это, что же такое амортизированная константа. То понятие, которое мы видели, когда подсмотрели в документации сложность метода push_back у вектора. Про вектор и то, как у него реализован метод push_back и почему он работает именно за амортизированную константу, мы поговорим позже в нашем курсе. Но сейчас мы рассмотрим это понятие амортизированной константы на другом примере. Рассмотрим такую задачу. Пусть к вам приходят события с какими-то временными метками. Допустим, вы их получаете прямо во возрастанию этих временных меток. Вам нужно уметь добавлять очередное событие с конкретной временной меткой и находить в какой-то конкретный момент, сколько событий случилось за последние пять минут. Как нам решать такую задачу? Мы напишем класс EventManager, который будет обрабатывать события. У него будет метод Add, который будет добавлять событие. Давайте хранить временные метки в типе unit64_t. Для этого подключим модуль sctdint. Итак, будем добавлять события и узнавать, сколько событий случилось за последние пять минут. Скажем, в типе int вернём количество событий. Понимаем тоже временную метку. И предполагая, что каждая очередная метка больше, чем предыдущая, мы должны сказать, сколько за последние пять минут случилось событий. Как такую задачу вообще можно решать? Её можно решать с помощью очереди. Давайте я сразу подключу заголовочный файл queue. И что я буду хранить? Я буду хранить очередь временных меток событий. В этой очереди будут все события за последние пять минут. То есть я буду не только добавлять в эту очередь с одного конца, но и удалять из неё, когда нужно, старые события, которые старше, чем пять минут. Соответственно, в методе Add то, что я должен сделать в любом случае, это добавить в очередь эту самую временную метку. А в методе Count, если я гарантирую, что у меня в очереди нет старых событий, я могу просто вернуть размер этой очереди. Но как же я это гарантирую? Мне, конечно, понадобится удалять старые события. Давайте я напишу отдельный приватный метод. Назову его Adjut, который будет принимать временную метку и удалять события, которые старше, чем пять минут, относительно этой метки. Как мне это сделать? Я должен удалять последнее событие из очереди, пока оно достаточно старое, если говорить точнее, то пока в очереди вообще что-то есть. while !events.empty — и пока у меня самое старое событие в очереди, которое я получаю с помощью метода front, пока оно слишком старое, то есть пока это время меньше либо равно, чем time минус 300. 300 секунда — пять минут. Пока оно достаточно старое, я должен его удалять с помощью метода pop. И теперь мне нужно поудалять эти старые события, пожалуй, и перед добавлением в очередь, и перед определением того, сколько же там событий. Итак, вот я написал какой-то код. Давайте я проверю, что он компилируется. Да, всё в порядке. И давайте теперь попробуем оценить сложность каждого запроса. Добавление одного числа в очередь стоит o от единицы, прямо честное константное время. Вычисление размера очереди — тоже o от единицы. Удаление из очереди и обращение к её последнему элементу — тоже o от единицы. Но есть интересный момент. В запросе Add, в запросе Count мы вызываем метод Adjust. Сколько работает этот метод? А здесь какой-то цикл. И в худшем случае сколько может работать этот цикл while. Он в худшем случае будет удалять вам вообще все события из очереди. В худшем случае все события в очереди, которые там накопились за долгое-долгое время, они все старше, чем пять минут. Скажем, вы долго-долго копили-копили события, они приходили в маленьком-маленьком промежутке. А потом — бац! И пришло новое событие спустя час. Вам нужно очистить всю очередь. И поэтому количество итераций в этом цикле while в худшем случае будет пропорционально количеству запросов, то есть o от Q. И поэтому метод Adjust в худшем случае работает o от Q. И в частности, как следствие, и метод Add, и метод Count в худшем случае работают o от Q. Что же получается? Неужели суммарно все эти методы будут обрабатывать запросы за квадратичное время, за Q умножить на Q? Это же странно. Я вроде бы делаю такие простые операции: добавил, удалил, проверил. Почему квадратичное время получается? Потому что мы слишком увлеклись верхними оценками. Верхняя оценка в данном случае достигаться не будет. Почему? Давайте посмотрим на ту же ситуации с другой точки зрения. Посмотрим на одно конкретное событие. Что с ним будет происходить? Мы его добавим сначала. Потом оно будет просто лежать в очереди, никак не влияя на сложность. И потом мы его, возможно, удалим. То есть всё, что может произойти с одним событием за всё время жизни программы — это одно добавление, одна проверка на время и одно удаление. То есть с каждым событием у нас произойдёт константное количество операций, o от единицы, то есть суммарно мы на обработку всех Q событий потратим o от Q времени, а не o от Q квадрат, в то время как верхняя оценка у нас получилась o от Q квадрат. Где же мы, на самом деле, ошиблись? Ну не ошиблись, а из-за чему мы получили такую слишком грубую, завышенную оценку? Дело в том, что вот эти циклы while, конечно, каждый конкретный вызов Adjust может работать долго за o от Q, но суммарно все эти циклы while, суммарно все вызовы Adjust по сути нам в худшем случае очистят всю очередь, все те события, которые мы добавляли. Их всего Q, поэтому и суммарное удаление всех этих событий суммарно будет работать за Q. То есть с каким явлением мы сейчас столкнулись? Каждый конкретный вызов Adjust может работать долго. Каждый конкретный вызов Add или Count может работать долго, если мы скопили много-много событий, а потом новое событие пришло спустя час. Но суммарно все эти события будут работать за o от Q, а не за o от Q квадрат. В этом случае говорят, что сложность одного запроса Add, сложность одного запроса Count и сложность одного вызова метода Adjust не o от Q, а амортизированное o от Q. Amortized — то самое, что мы видели в документации — o от Q. Здесь, здесь, здесь нет, а вот здесь да. Что означает амортизированная сложность? Точнее, простите, конечно. Верхняя оценка была o от Q, но амортизированно получается o от единицы, и поэтому суммарно мы получаем o от Q. Чуть более формально. Да, если мы выполним одну операцию, один вызов одного из наших методов, у нас будет сложность o от Q. Но если мы много-много раз на одних и тех же данных будем вызывать этот метод, тогда суммарно получиться o от Q, а каждый один вызов будет работать как будто бы за o от единицы. То есть, грубо говоря, в среднем каждый метод работает за o от единицы, вот такое понятие амортизированной сложности. Мы его позже в нашем курсе обсудим на примере push_back у вектора. Там ровно та же ситуация. Один push_back может работать долго, но если вы много-много push_back'ов делаете, тогда каждый из них будет работать быстро в среднем. А пока просто знайте о таком понятие как амортизированная сложность, в частности, амортизированная константа, и не увлекайтесь верхними оценками. Будьте внимательны, когда вы вычисляете суммарную сложность работы какого-то цикла.
