随机与递归算法
随机算法通过在算法执行过程中进行随机选择,在其逻辑中包含了随机性。由于这种随机性,即使对于固定输入,算法的行为也会发生变化。对于许多问题,随机算法提供了最简单有效的解决方案。递归算法基于这样一种思想,即问题的解可以通过找到同一问题的较小子问题的解来找到。递归在计算机科学中被广泛用于寻找问题的解决方案,许多高级编程语言都支持递归。
什么是随机算法?
随机算法通过随机选择来指导算法的执行,从而融入了随机性的感觉。这通常是通过将伪随机数生成器生成的一组随机数作为附加输入来完成的。因此,即使是固定输入,算法的行为也可能会发生变化。Quicksort是一种广泛采用随机性概念的算法,它具有O(n LOGN)的运行时间,而不考虑输入属性。在计算几何中,将随机增量构造方法应用于凸包等结构的施工。该方法将输入点随机排列,然后逐个**结构中。实现随机算法相对简单,而不是对同一问题实现确定性算法。设计随机算法的最大挑战在于对时间和空间复杂度进行渐近分析。
什么是递归算法?
递归算法基于这样一种思想,即问题的解可以通过找到同一问题的较小子问题的解来找到。在递归算法中,函数是根据其早期版本定义的。需要注意的是,这种自引用应该有一个终止条件,以避免永远引用它自己。终止条件在引用自身之前被检查。递归算法的初始步骤与问题递归定义的基子句有关。第一步之后的步骤与问题的归纳从句有关。递归算法在许多情况下提供了一个更简单的解决方案,它比迭代算法更接近于自然思维方式。但一般来说,递归算法需要更多的内存,而且计算成本很高。
随机算法和递归算法有什么区别?