算法(4th ed)(213):基础——案例研究:union-find 算法 7.3

阅读数:9 2019 年 11 月 9 日 15:59

算法(4th ed)(213):基础——案例研究:union-find 算法 7.3

(展望)

直观感觉上,我们学习的每种 UF 的实现都改进了上一个版本的实现,但这个过程并不突兀,因为我们可以总结学者们对这些算法多年的研究。我们很明确地说明了问题,解决方法的实现也很简单,因此可以用经验性的数据评估各个算法的优劣。另外,还可以通过这些研究验证将算法的性能量化的数学结论。只要可能,我们在本书中研究各种基础问题时都会遵循类似于本节中讨论 union-find 问题时的基本步骤,在这里我们要再次强调它们。

  • 完整而详细地定义问题,找出解决问题所必需的基本抽象操作并定义一份 API。
  • 简洁地实现一种初级算法,给出一个精心组织的开发用例并使用实际数据作为输入。
  • 当实现所能解决的问题的最大规模达不到期望时决定改进还是放弃。
  • 逐步改进实现,通过经验性分析或(和)数学分析验证改进后的效果。
  • 用更高层次的抽象表示数据结构或算法来设计更高级的改进版本。
  • 如果可能尽量为最坏情况下的性能提供保证,但在处理普通数据时也要有良好的性能。
  • 在适当的时候将更细致的深入研究留给有经验的研究者并继续解决下一个问题。

我们从 union-find 问题中可以看到,算法设计在解决实际问题时能够为程序的性能带来惊人的提高,这种潜力使它成为热门研究领域。还有什么其他类型的设计行为可能将成本降为原来的数百万甚至数十亿分之一呢?

设计高效的算法是一种很有成就感的智力活动,同时也能够产生直接的实际效益。正如动态连通性问题所示,为解决一个简单的问题我们学习了许多算法,它们不但有用有趣,也精巧而引人入胜。我们还将遇到许多新颖独特的算法,它们都是人们在数十年以来为解决许多实际问题而发明的。随着计算机算法在科学和商业领域的应用范围越来越广,能够使用高效的算法来解决老问题并为新问题开发有效的解决方案也越来越重要了。

评论

发布