algorithm - 什么是 "naive"算法，什么是 "closed - form"解法？

Question

我有几个关于描述算法时使用的术语语义的问题。

首先，“朴素”算法是什么意思？这与给定问题的其他解决方案有何不同？解决方案还可以采用哪些其他形式？

其次，我听说过很多关于“封闭式”解决方案的说法。我也不知道这意味着什么 - 但在尝试解决递归关系时经常出现...

谢谢你的时间

Answer 1

Naive algorithm 通常是当一个人被问到问题时最明显的解决方案。它可能不是一个智能算法，但可能会完成工作(...最终。)

例如。尝试在排序数组中搜索元素。一个朴素的算法是使用 Linear Search .一个不太天真的解决方案是使用二进制搜索。

一个更好的例子，是在子字符串搜索的情况下 Naive Algorithm远低于 Boyer–Moore 或 Knuth–Morris–Pratt 算法

闭式解决方案是一种简单的解决方案，无需任何循环、函数等即可立即运行。

例如:1到n整数求和的迭代算法

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

封闭式(针对同一问题)

s = n * (n + 1 ) /2