4

Specifically, the Steepest-Ascent Hill Climbing, Stochastic Hill Climbing and Simulated Annealing. The generalized time complexity would be fine too. Thanks.

Jopet Copiaco
  • 85
  • 1
  • 4
  • 2
    This question appears to be off-topic because it is about theory, rather than programming. – Jim Lewis Sep 01 '13 at 06:57
  • 1
    @jim If you are going to close it because its off topic, it would be helpful to leave a reference for where it is appropriate to post such a question. Try http://cs.stackexchange.com/ for theory questions next time. – yekta Oct 15 '16 at 18:09

1 Answers1

7

The methods you list can be interrupted at any time, and return “the best result so far”. Therefore, it only makes sense to talk about the time they take to return the absolute best result (the global maximum).

All the methods you list may fail to reach the global maximum. Therefore, their complexity is O(∞).

Traditional time complexity notions do not make sense for heuristics, only for proper algorithms. Here is a writeup about the difference between the two.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
  • It depends on the number of hills, like Pascal points out. However since he didn't mention it, it will be at worst linear with `O(n)` and at best can be `O(log n)` using random reset. – yekta Oct 15 '16 at 18:09