什么是“天真”？算法，以及什么是“封闭形式”？解决方案？

Question

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

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

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

感谢您的时间

Answer 1

当有人提出问题时，朴素算法通常是最明显的解决方案。它可能不是一个聪明的算法，但可能会完成工作（......最终。）

例如。尝试在已排序的数组中搜索元素。
朴素算法是使用线性搜索。
一个不那么幼稚的解决方案是使用二分搜索。

一个更好的例子是子字符串搜索 Naive Algorithm 远远不够效率低于 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

朴素算法是一种非常简单的算法，具有非常简单的规则。有时候第一个想到的就是这个。它可能很愚蠢而且很慢，甚至可能无法解决问题。有时这可能是最好的。下面是一个问题和“简单”算法的示例：

问题：您处于一个（二维）迷宫中。找到出路。 （意思是：到一个带有“EXIT”标志的地点：）

朴素算法 1：开始行走，并在遇到的每个十字路口选择正确的十字路口（直到找到“EXIT”）。

朴素算法 2：开始行走并在遇到的每个十字路口中随机选择一个十字路口（直到找到“出口”）。

算法 1 甚至无法让你走出某些迷宫！

算法 2 会让你走出所有迷宫（尽管这很难证明）。

Answer 3

封闭形式意味着您可以给出一个表达式作为解决方案，这确实可以解决它而无需递归/递归。这里应该指出，并不总是能够找到这样一种封闭的形式。

天真的意思就是它所说的：对问题的第一个愚蠢的解决方案，解决了它，但可能不是非常时间/空间效率。人们真正认为什么是“天真”取决于说话者、上下文和第二天的天气。通常它用于区分非常复杂的解决方案（使用某种技巧）和明显的实现。