Алгоритм минимума скользящего окна

Question

Это домашнее задание. Пусть A [] - массив целых чисел, а K - размер окна. Создайте массив M минимумов, видимых в окне, когда он скользит по A. Я нашел статью с решением этой проблемы, но не понял , почему имеет сложность O (n). Кто-нибудь может мне это объяснить?

Answer 1

Это имеет тенденцию ловить людей. Вы могли бы подумать, что это займет O(N^2) время, так как вы считаете, что добавление занимает O(N) время, и у вас есть O(N) элементы. Однако следует понимать, что каждый элемент может быть добавлен только один раз и удален один раз. Таким образом, в общей сложности требуется O(N), чтобы скользить по всему массиву A.

Это дает амортизированную эффективность O(1) каждый раз, когда вы перемещаете скользящее окно на один элемент. Другими словами, среднее время, необходимое для перемещения скользящего окна на один элемент, составляет O(1).