Passa al tema normale
Discussioni su Analisi Numerica e Ricerca Operativa

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

complessità subesponenziale

23/05/2020, 08:17

Salve,
Ho trovato due definizioni diverse di algoritmo a tempo subesponenziale.
La prima, un algoritmo è a tempo subesponenziale se la sua funzione running time è del tipo $2^{o(n)}$
La secondo, un algoritmo è a tempo subesponenziale se la sua funzione running time sta nella classe $\bigcap_{\epsilon>0} O(2^{\epsilon n})$.
Chiaramente la prima classe è contenuta nella seconda. Mi chiedo se ho una funzione del tipo $2^{g(n)}$ che appartiene alla seconda classe, questa deve appartenere necessariamente alla prima?
Quindi in realtà le due classi coincidono?
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.