Комментарии 14
есть книга Майкла Абраша, называется, по-видимому Zen of graphics programming
В русской редакции она выходила под названием "Таинства программирования графики". Там с вниманием к производительности рассматриваются задачи быстрого заполнения выпуклых (convex polygon) и невыпуклых многоугольников.
А я вот со времен ZX Spectrum помню, что "построчный" алгоритм куда более быстрый и экономный по памяти. Возможно, с тех давних пор какие-то еще алгоритмы появились. Рекурсивный же алгоритм может быть и хорош в образовательных целях, но статье все-равно явно не хватает ссылок на текущие "state-of-the-art" алгоритмы.
А у меня не было ZX Spectrum, но был его отечественный аналог "Дуэт" :) Это было прекрасное время.
Ну и конечно существуют разные алгоритмы заливки, кроме упомянутой рекурсивной заливки есть еще breadth-First Flood Fill, заливка по глубине, итеративная заливка, seed Fill и другие. Многие похожи друг на друга, отличаются некоторыми оптимизациями. На собеседованиях об этом достаточно часто спрашивают, поэтому даже как минимум учебную рекурсию стоит разобрать тем, кто планирует алгоритмическое собеседование.
Что касается пространственной сложности, то каждый рекурсивный вызов требует дополнительной памяти для хранения состояния функции, которое включает текущую позицию и цвет пикселя. В наихудшем случае, когда заполняемая область охватывает всё изображение, максимальная глубина рекурсии будет равна количеству строк в изображении. Поэтому пространственная сложность алгоритма заливки на основе рекурсии может быть выражена как O(m).
Это категорически неверно по двум пунктам сразу.
Во-первых, почему именно строк, а не столбцов? Столбцов может быть на порядок больше. Никаких принципиальных отличий между строками и столбцами в алгоритме обхода в глубину (depth-first search, так называется ваш первый алгоритм) нет. Так что как минимум O(max(n, m)), оно же O(n+m).
Во-вторых, а с какого перепуга это наихудший случай? Вы ещё скажите, что наихудший случай для алгоритма сортировки — это когда массив отсортирован в обратном порядке. Не бывает просто "наихудших" случаев. Это вредное заблуждение. Бывают только случаи, максимизирующие или минимизирующие какую-то метрику. Тогда мало предъявить случай, надо доказать.
Например, довольно легко придумать пример, где глубина стека (по сути максимальная длина пути, которую пройдёт алгоритм, пока не упрётся в тупик) будет уже порядка n*m/2.
Лучше придумайте сами
....................
###################.
....................
.###################
....................
###################.
....................
.###################
....................
###################.
....................
.###################
....................Здесь надо "залить" точки и не ходить по решёткам.
Если вам кажется, что ну уж это-то очевидно наихудший случай, то вы снова попались в ловушку. Не было ни слова доказательства про наихудшесть случая. Этот случай плохой, но не наихудший. Можно ещё хуже сделать. Я вот знаю пример с n*m*2/3, но тоже без доказательства, что это наихудший случай.
Хотя асимптотически уже неважно, оба случая будут O(n*m). И вот это уже доказывается без "наихудших случаев": в стеке вызовов (за исключением текущего фрейма) каждая ячейка может встретиться не больше одного раза. Доказательство закончено.
А ещё посылаю лучи ненависти новому редактору Хабра. Он уже один раз съел комментарий и не давал набирать текст в некоторых местах, уффф.
Приятно читать и отвечать на аргументированные комментарии внимательных читателей. Вдвойне приятно когда такое общение приносит продуктивный результат. Действительно сложность алгоритма заливки на основе рекурсии зависит от размера изображения или сетки, которую необходимо заполнить.
Когда необходимо заполнить всю сетку, сложность можно оценить как O(n * m). Это объясняется тем, что в этом случае каждая ячейка сетки должна быть обработана, и каждая ячейка занимает постоянное место в стеке вызовов.
Цель статьи не столько в том, чтобы научить читателя делать оценки сложности или показать чем отличаются понятия "наихудший и наилучший случаи" и "случаи, максимизирующие или минимизирующие какую-то метрику" - эти вопросы разбираются на соответствующем курсе по алгоритмам, а больше в том, чтобы показать пример реальной задачи из алгоритмической части интервью, показать возможные варианты её решения, а также предложить обсуждение темы. Тем не менее спасибо, что обратили внимание этот действительно важный момент!
graph = {(y, x): [] for y in range(height) for x in range(width) if f[y,x]!=COLOR}
далее очевидно
люблю хабр за это: ничего непонятно, но очень интересно, спасибо!
Приятно читать такие публикации :). Вопрос: как понять "Если все стены смежные?" Могут быть и не смежные? Авось пригодится где-нибудь, если попаду в лабиринт :).
В своё время тоже пилил "наводнение". Было интересно придумать самому. В итоге, как потом выяснилось, сделал "построчный" вариант, правда с рекурсией. То что реализовано в статье - это называется DFS. У меня такой вариант не зашёл, почему-то работало медленно, видно где то накосячил..
Я бы реализовал бы его через метод пузырька. То есть от середины идет к краю... как волны от камня на воде.
Решаем задачу заливки однородной области