У меня есть несколько вопросов относительно семантики терминологии, используемой при описании алгоритмов.
Во-первых, что подразумевается под "наивным" алгоритмом? Как это отличается от других решений данной проблемы? Какие другие формы могут принимать решения?
Во-вторых, я слышал много ссылок на решение "закрытой формы". Я понятия не имею, что это значит, но часто возникает при попытке решить рекуррентные отношения...
Спасибо за ваше время
A Наивный алгоритм обычно является наиболее очевидным решением, когда задается проблема. Возможно, это не умный алгоритм, но, вероятно, он выполнит свою работу (... в конце концов.)
Eg. Попытка поиска элемента в отсортированном массиве. Наивный алгоритм должен был бы использовать Linear Search. Незначительным решением было бы использовать двоичный поиск.
Лучшим примером может быть в случае поиска подстроки Наивный алгоритм гораздо менее эффективен, чем 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
Наивный алгоритм - очень простой алгоритм, один с очень простыми правилами. Иногда первое, что приходит на ум. Это может быть глупо и очень медленно, это может даже не решить проблему. Иногда это может быть наилучшим. Вот пример проблемы и "наивные" алгоритмы:
Проблема: вы находитесь в (двумерном) лабиринте. Найдите свой выход. (значение: на пятно с знаком "ВЫХОД" :)
Наивный алгоритм 1: Начните ходить и выберите правильный в каждом пересечении, которое вы встречаете (пока не найдете "ВЫХОД" ).
Наивный алгоритм 2: Начните ходить и выберите случайный в каждом пересечении, которое вы встречаете (пока не найдете "ВЫХОД" ).
Алгоритм 1 даже не вытащит вас из некоторых лабиринтов!
Алгоритм 2 избавит вас от всех лабиринтов (хотя это довольно сложно доказать).
Закрытая форма означает, что вы можете дать одно выражение как решение, которое решит его без повторения/рекурсии. Здесь следует отметить, что не всегда можно найти такую замкнутую форму.
Наивный означает только то, что он говорит: первое, глупое решение проблемы, которое его решает, но, возможно, не очень эффективное время/пространство. То, что действительно считают "наивным", зависит от говорящего, контекста и от погоды на следующий день. Часто он используется, чтобы отличить очень сложное решение (которое использует какой-то трюк) от очевидной реализации.