什么是“朴素”算法，什么是“闭式”解决方案？

Question

关于算法描述中术语的语义，我有几个问题。

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

其次，我听说过“closed - form”解法很多，但我不知道这是什么意思——但通常在尝试解决递归关系时出现...

感谢您的时间

- user559142

Answer 1

当面临问题时，朴素算法通常是最明显的解决方案。它可能不是最智能的算法，但很可能会完成任务（...最终）。

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

更好的例子是在子字符串搜索的情况下，朴素算法远不如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

- st0le

Answer 2

朴素算法是一种非常简单的算法，具有非常简单的规则。有时它是脑海中首先想到的算法。它可能很愚蠢而且非常慢，甚至不能解决问题。但有时候它可能是最好的选择。以下是一个问题和“朴素”算法的示例：

问题：你在一个（二维）迷宫中。找到出口。（意思是走到一个带有“EXIT”标志的地方 :)

朴素算法1：开始走，每次在交叉口选择右侧的路线（直到找到“EXIT”）。

朴素算法2：开始走，每次在交叉口随机选择一条路线（直到找到“EXIT”）。

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

算法2可以让你走出所有迷宫（虽然这很难证明）。

- ypercubeᵀᴹ

---

沿着右边的墙壁一直走，总能让你走出迷宫。 - potrzebie

@potrzebie，不是所有迷宫！ - ypercubeᵀᴹ

@potrzebie 墙随行策略仅适用于简单连通的迷宫。 - Martin

Answer 3

闭式意味着你可以给出一个表达式作为解决方案，它可以在不需要递归的情况下解决问题。但需要注意的是，并不总是可能找到这样的闭式形式。

朴素意味着就是字面上的意思：对于问题的第一种愚蠢的解决方案，虽然可以解决问题，但可能不太时间/空间有效。什么才被认为是“朴素”的取决于说话者、上下文和明天的天气。通常用于区分非常复杂的解决方案（使用某种技巧）和显而易见的实现。

- flolo