Я читал про метод ветвей и границ, когда писал статью, стараясь найти аналогичные определения в русском языке, но, как вы отметили, это не тот же метод.
Вы правы, что в данной реализации отсутствует явное отсечение постоянного коэффициента, но это объясняется особенностями задачи поиска слова в матрице: здесь мы не применяем метод "Отсечение и поиск" в полном объеме, мы используем основную идею - рекурсивный подход, основанный на пошаговом "отсечении" неподходящих вариантов.
Что касается большого объема данных, благодарю за уточнение.
Утверждение о линейности алгоритма дается в математическом определении, которое является переводом оригинальной статьи. Касаемо решаемой задачи оценка сложности не производилась.
"Натягиваю" не я, а англоязычное сообщество, я лишь хочу, чтобы у русскоязычного сообщества было хотя бы базовое понимание того, почему в контексте данной задачи на LeetCode используется этот термин.
Если в статье есть еще какие-то ошибки, то, пожалуйста, дайте знать, я поправлю. Спасибо!
Данная статья является переводом статьи из Википедии, целью написания статьи послужило отсутствие известного термина в английском языке на русском языке, чтобы любой, кто столкнется с таким термином, мог загуглить его и посмотреть, что он означает: в переводе математического определения и более простом пояснении (статья уже выдается в поисковиках).
В математическом определении отбрасывание части данных (n(1-p)) происходит на каждом шаге, что приводит к рекурсивной природе алгоритма. Рекурсивный поиск охватывает только те варианты, которые приводят к нужному результату.
И, понимая эту концепцию, мы можем применить ее на данной задаче - на каждом шаге мы отсекаем варианты, которые не приводят нас к желаемому результату.
Я читал про метод ветвей и границ, когда писал статью, стараясь найти аналогичные определения в русском языке, но, как вы отметили, это не тот же метод.
Вы правы, что в данной реализации отсутствует явное отсечение постоянного коэффициента, но это объясняется особенностями задачи поиска слова в матрице: здесь мы не применяем метод "Отсечение и поиск" в полном объеме, мы используем основную идею - рекурсивный подход, основанный на пошаговом "отсечении" неподходящих вариантов.
Что касается большого объема данных, благодарю за уточнение.
Утверждение о линейности алгоритма дается в математическом определении, которое является переводом оригинальной статьи. Касаемо решаемой задачи оценка сложности не производилась.
"Натягиваю" не я, а англоязычное сообщество, я лишь хочу, чтобы у русскоязычного сообщества было хотя бы базовое понимание того, почему в контексте данной задачи на LeetCode используется этот термин.
Если в статье есть еще какие-то ошибки, то, пожалуйста, дайте знать, я поправлю. Спасибо!
Данная статья является переводом статьи из Википедии, целью написания статьи послужило отсутствие известного термина в английском языке на русском языке, чтобы любой, кто столкнется с таким термином, мог загуглить его и посмотреть, что он означает: в переводе математического определения и более простом пояснении (статья уже выдается в поисковиках).
В математическом определении отбрасывание части данных (
n(1-p)) происходит на каждом шаге, что приводит к рекурсивной природе алгоритма. Рекурсивный поиск охватывает только те варианты, которые приводят к нужному результату.И, понимая эту концепцию, мы можем применить ее на данной задаче - на каждом шаге мы отсекаем варианты, которые не приводят нас к желаемому результату.
Убрал в теги (в статье есть упоминание расширения)