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

阅读数:6 2019 年 11 月 9 日 15:45

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

为了说明我们设计和分析算法的基本方法,我们现在来学习一个具体的例子。我们的目的是强调以下几点:

  • 优秀的算法因为能够解决实际问题而变得更为重要;
  • 高效算法的代码也可以很简单;
  • 理解某个实现的性能特点是一项有趣而令人满足的挑战;
  • 在解决同一个问题的多种算法之间进行选择时,科学方法是一种重要的工具;
  • 迭代式改进能够让算法的效率越来越高。

我们会在本书中不断巩固这些主题思想。本节中的例子是一个原型,它将会为我们用相同的方法解决许多其他问题打下坚实的基础。

我们将要讨论的问题并非无足轻重,它是一个非常基础的计算性问题,而我们开发的解决方案将会用于多种实际应用之中,从物理化学中的渗流到通信网络中的连通性等。我们首先会给出一个简单的方案,然后对它的性能进行研究并由此得出应该如何继续改进我们的算法。

评论

发布