Что такое «наивный» алгоритм и что такое «замкнутое» решение?

Question

У меня есть несколько вопросов относительно семантики терминологии, используемой при описании алгоритмов.

Во-первых, что подразумевается под «наивным» алгоритмом?Чем это отличается от других решений данной проблемы?Какие другие формы могут принимать решения?

Во-вторых, я слышал много упоминаний о наличии решения «закрытой формы».Я тоже понятия не имею, что это значит - но часто это появляется при попытке решить рецидивирующие отношения ...

Спасибо за ваше время

Answer 1

A Наивный алгоритм обычно является наиболее очевидным решением, когда задают проблему. Возможно, это не умный алгоритм, но, вероятно, он выполнит свою работу (... в конце концов.)

Например. Попытка поиска элемента в отсортированном массиве. Наивным алгоритмом было бы использовать линейный поиск . Не столь наивным решением было бы использовать бинарный поиск.

Лучшим примером будет поиск подстроки Наивный алгоритм гораздо менее эффективен, чем Boyer–Moore или Knuth–Morris–Pratt Алгоритм

A Решение для закрытых форм - это простое решение, которое работает мгновенно без каких-либо циклов, функций и т. Д.

Например: Итерационный алгоритм для суммы целых чисел от 1 до n

s= 0
for i in 1 to n
s = s + i
end for
print s

Закрытая форма (по той же проблеме)

s = n * (n + 1 ) /2

Answer 2

Наивный алгоритм - это очень простой алгоритм с очень простыми правилами.Иногда первое, что приходит на ум.Это может быть глупо и очень медленно, это может даже не решить проблему.Иногда это может быть лучшим из возможных.Вот пример проблемы и алгоритмов " naive ":

Проблема: Вы находитесь в (2-мерном) лабиринте.Найди выход.(значение: до места со знаком " EXIT " :)

Наивный алгоритм 1: Начните идти и выберите правильный на каждом перекрестке, который вы встречаете (пока не найдете "EXIT").

Наивный алгоритм 2: Начинайте ходить и выбирайте случайный на каждом перекрестке, который встречаете (пока не найдете «ВЫХОД»).

Алгоритм 1 даже не выведет вас из лабиринтов!

Алгоритм 2 выведет вас из всех лабиринтов (хотя это довольно сложно доказать).

Answer 3

Закрытая форма означает, что вы можете дать одно выражение как решение, которое решает его без рекуррентности / рекурсии.Здесь следует отметить, что не всегда можно найти такую ​​замкнутую форму.

Наивный означает только то, что он говорит: первое, глупое решение проблемы, которое решает ее, но, возможно, не очень эффективно с точки зрения времени / пространства.То, что человек действительно считает «наивным», зависит от говорящего, контекста и погоды на следующий день.Часто оно используется для того, чтобы отличить очень сложное решение (использующее какую-то хитрость) от очевидной реализации.