Podstawowe operacje algorytmu Ameba:

- uporządkowanie

F(x0)>F(x1)>…>F(xn)

- odbicie

xr = x + (x - xn)

- F(xr)

a) F(xr)>F(x0) dokonujemy ekspansji

xs = xr + (x - xn)

F(xs)>F(xr)

xs xr

F(xs)<F(xr)

xr xs

b) F(xr)<F(xn-1) kontrakcja

xc = x + (x - xn)

xc xn

- skurczanie

xi = x0 + (xi - x0)

Złożoności obliczeniowe

F(n) = O(g(n)) pesymistyczny wariant złożoności obliczeniowej

0<f(n)<cg(n)

F(n) = (g(n)) optymistyczne ograniczenie od dolu

0<cg(n)<f(n)

F(n) = (g(n)) ograniczona z góry i z dołu jednocześnie

0<c1g(n)<f(n)<c2g(n)

F(n) = o(g(n)) dla dowolnych c>0

0<f(n)<cg(n))

F(n) = w(g(n)) dla dowolnych c>0

0<cg(n)<f(n)

---