Notazione asintotica, alcuni dubbi

[SorinMarkov]

Salve,
non sono sicuro di aver scelto la sezione giusta, vi prego di perdonarmi
Sto studiando le notazioni asintotiche, ovvero le famose O, Θ e Ω. Le definizioni delle tre notazioni mi sono ben chiare, ma ho un dubbio sulla definizione di algoritmo ottimo. Se considero un algoritmo che risolve un problema in un tempo f(n), e supponendo che Ω(g(n)) sia il limite inferiore, l'algoritmo è ottimo se f(n)=Ω(g(n))? È giusto?
Perchè, su alcuni libri e in rete leggo che un algoritmo è ottimo se f(n) = O (g(n)) in quanto un algoritmo, in generale, non può richiedere asintoticamente meno di O(g(n)). Questo mi confonde completamente, che vuol dire?

[Nikopol]

Ciao,
detto informalmente:
f(n) = O(g(n)) se f cresce definitivamente al più come g(n) (più precisamente come a un multiplo di g)
f(n) = Ω(g(n)) se f cresce definitivamente almeno come g(n) (più precisamente come a un sotto-multiplo di g)
f(n) = Θ(g(n)) se f è sia O(g(n)) che Ω(g(n)), ovvero f cresce esattamente come g.

Dunque:

l'algoritmo è ottimo se f(n) = Ω(g(n))? È giusto?

No!
Se ad esempio g(n) = n allora n^2, 2^n, n^n sono tutte funzioni di complessita = Ω(g(n))

Per affermare che un algoritmo A sia ottimo bisogna:
1) dimostrare formalmente che per risolvere il problema occorrono Ω(g(n)) passi (ovvero almeno g(n) passi) nel caso peggiore e che non può esistere un algoritmo risolvente con complessità inferiore a Ω(g(n)); ovvero Ω(g(n)) è il limite inferiore.
2) l'agoritmo A riesce a risolvere il problema con una complessità O(h(n)) (al più in h(n) passi) nel caso peggiore; ovvero O(h(n)) è il limite superiore.
3) g = h, ovvero il limite inferiore teorico del problema equivale al limite superiore dell' algoritmo risolvente

[SorinMarkov]

Inizio a capire. Quindi effettivamente è ottimo se f(n)=O(g(n)) ovvero se f(n) <= c * g(n) dove c è una costante positiva?

[Nikopol]

Quindi effettivamente è ottimo se f(n)=O(g(n))

Ni, f(n) è una funzione nella dimensione dell'input, ovvero n, ma la dimensione dell'input non ci dice niente a proposito della complessità dell'algoritmo.
Ad esempio considerando l'insertion sort su un array di dimensione n ha complessità n se l'array è già ordinato (caso migliore), invece n^2 se non lo è (caso peggiore).

Quindi un algoritmo è ottimo se la sua funzione di complessità nel caso peggiore è O-grande della funzione che rappresenta il limite inferiore del problema.

ovvero se f(n) <= c * g(n) dove c è una costante positiva?

Esatto, ma la relazione vale solo definitivamente, ovvero esiste un N tale che per ogni n maggiore di N, f(n) <= c * g(n), dove c è una costante reale positiva.
La costante moltiplicativa c serve solo a dire che siamo interessati esclusivamente all'andamento asintotico di f e di g e che se ad esempio g = 2x e f = x possiamo ancora considerare f <= g