何为启发式?

在之后的学习中,我们经常会看到”启发式“这三个字,看起来很深奥。但实际上启发式算法中的”启发式“只是一个好听点的名字罢了,启发式的真正含义就是——

<aside> ✅

我的直觉告诉我这样好一点!

</aside>

没错,启发式算法就是通过我们的直觉来优化的一种算法。启发式可以理解为灵机一动💡,也就是近似于“猜”的优化。但并不是所有灵机一动的算法都能被称为启发式,至少我是这么理解的:

启发式算法就是先猜,紧接着发现效果不错,最后得到时间复杂度上严谨的证明。

比如在 NOIp 篇 - 树上启发式合并 中,本来让人感觉只是一个小优化,但在经过严谨的证明后,就会发现原本 $\Theta(n^2)$ 的算法在经过这个不起眼甚至不可靠的优化的加持下,可以优化到严格 $\Theta(n\log n)$ 的时间复杂度!

启发式算法的优点?

这就是启发式算法,就像误打误撞,发现了一种强大的优化策略。而一般启发式算法具有以下特点:

  1. 时间复杂度好。
  2. 实现简单,代码短。

第一个特点时间复杂度好,是因为启发式算法的时间复杂度一般都是经过的证明的,既然能放出来让大家学习,那么一定是强大的。

第二个特点实现简单,是因为启发式算法一般都只是一个在暴力程序的基础上看起来很小的优化,而时间复杂度却很好。如果优化过于复杂,可能就直接变成一个完整的算法了吧,而只有短小精悍,强大可靠的算法才能被叫做启发式算法

没错,启发式算法并不是什么很复杂的东西。相反,启发式算法的代码可能比你想象中要短,性能可能比你想象中更优!