Алгоритмы и структуры данных. Семестр 1. Лекция 10. На десятой лекции мы начали разбирать метод динамического программирования Университет ИТМО, 2021 г.
На 42:00 - 45:30 задача решается за O(n*k). Можно ускорить до O(n), если для каждой внешней итерации не пересчитывать заново минимум на отрезке из k элементов, а оптимизировать, как оптимизировали в случае суммы на этом отрезке. Для суммы всё просто: при сдвиге отрезка на 1 вправо, делается S = S - arr[i-k-1] + arr[i]. С минимумом чуть хитрее: идея аналогична очереди на двух стеках. Надо поддерживать "головной" минимум (который обновляется элементами, добавляемыми справа в наш отрезок) и "хвостовой" стек минимумов, из которого извлекаются элементы, уезжающие влево. Через каждые k итераций стек опустошается, и его надо заполнить заново. Амортизационно выходит O(1) на шаг.
Можно же использовать multiset. Добавлять новый «головной» элемент и извлекать «хвостовой», и за logk получать минимум. В таком случае мне кажется ,что nlogk будет лучше ,чем k амортизированная в константу. Возможно я не понял идею нахождении минимума в стеке.
The millionth Fibonacci Kata (codewars) - задача, в которой последний алгоритм нужно применять
На 42:00 - 45:30 задача решается за O(n*k). Можно ускорить до O(n), если для каждой внешней итерации не пересчитывать заново минимум на отрезке из k элементов, а оптимизировать, как оптимизировали в случае суммы на этом отрезке. Для суммы всё просто: при сдвиге отрезка на 1 вправо, делается S = S - arr[i-k-1] + arr[i]. С минимумом чуть хитрее: идея аналогична очереди на двух стеках. Надо поддерживать "головной" минимум (который обновляется элементами, добавляемыми справа в наш отрезок) и "хвостовой" стек минимумов, из которого извлекаются элементы, уезжающие влево. Через каждые k итераций стек опустошается, и его надо заполнить заново. Амортизационно выходит O(1) на шаг.
Все так
Можно же использовать multiset. Добавлять новый «головной» элемент и извлекать «хвостовой», и за logk получать минимум. В таком случае мне кажется ,что nlogk будет лучше ,чем k амортизированная в константу. Возможно я не понял идею нахождении минимума в стеке.
Паша топчик!
а зачем нам while на 37:50 ??
R E S P E C T
вопрос не по теме: а муз. оформление чье?
Все свое