随机算法与递归算法的区别

随机算法vs递归算法

随机算法通过在算法执行过程中做出随机选择而将随机性融入到其逻辑中。由于这种随机性，即使对于固定的输入，算法的行为也会发生变化。对于许多问题，随机算法提供了最简单和有效的解决方案。递归算法是基于这样一种思想:一个问题的解可以通过找到同一问题的更小的子问题的解来找到。递归在计算机科学中被广泛用于寻找问题的解决方案，许多高级编程语言都支持递归。

什么是随机算法?

随机算法通过做出引导算法执行的随机选择而融入随机性。这通常是通过将伪随机数生成器生成的一组随机数作为额外输入来实现的。因此，即使对于固定的输入，算法的行为也可能会改变。快速排序是一种广为人知的算法，它使用了随机性的概念，不管输入属性是什么，它的运行时间都是O(n log n)。在计算几何中，采用随机增量构造法构造凸壳等结构。在这种方法中，输入点是随机排列的，然后一个一个地插入到结构中。对于相同的问题，实现随机算法比实现确定性算法相对简单。设计随机算法的最大挑战在于对时间和空间复杂度进行渐近分析。

什么是递归算法?

递归算法是基于这样一种思想:一个问题的解可以通过找到同一问题的更小的子问题的解来找到。在递归算法中，函数是根据其自身的早期版本定义的。需要注意的是，这个自我引用应该有一个终止条件，以避免永远引用自己。在引用自身之前检查终止条件。递归算法的初始步骤与问题递归定义的基子句有关。第一步之后的步骤与问题的归纳从句有关。递归算法在许多情况下提供了一种更简单的解决方案，它比迭代算法更接近自然的思维方式来解决相同的问题。但一般来说，递归算法需要更多的内存，而且计算成本很高。

随机算法和递归算法的区别是什么?

随机算法是一种通过做出随机选择来影响算法执行的随机算法，而递归算法是一种基于这样一种思想的算法，即问题的解决方案可以通过寻找同一问题的较小子问题的解决方案来找到。由于随机算法的随机性，即使是相同的输入(在算法的不同执行过程中)，算法的行为也可能发生变化。但这在递归算法中是不可能的，而且递归算法的行为对于固定输入是一样的。