Formal Methods II

Could be in 試験
f(a)
..... O(a)
log2 a


You have to think of the input SIZE not the input VALUE.

So the proper complexity would be O(2^a)

ie
g(x) = { O(x) x prime
O(x^2) Not prime

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Local Optima

When you throw those techniques at local optima, you get local optima! So you can use generic local search to try and get yourself out of this.

Greedy Search
You have a partial solution, and you build up a complete solution from that.
Local search is greedy.
Systematic or exhaustive searches are not greedy.
Dijkstras. etc. It can escape local optima.

Korbs version of MF's Chapter 5

Iterated Hill Climber
Stochastic hill climber