爬山算法的时间复杂度是多少？

Question

具体而言，最陡峭山攀登，随机爬山和模拟退火。广义的时间复杂性也可以。谢谢。

Answer 1

您列出的方法可以在任何时候中断，并返回“目前为止最好的结果”。因此，谈论他们返回绝对最佳结果（全球最大值）的时间是有意义的。

您列出的所有方法可能无法达到全局最大值。因此，它们的复杂度是O（∞）。

传统的时间复杂性概念对启发式算法没有意义，只适用于正确的算法。这里是a writeup about the difference between the two。