Ho analizzato il mio algoritmo e ho dedotto che nel migliore dei casi richiede n ^ 3 iterazioni mentre nel peggiore dei casi richiede n ^ 4 iterazioni. Quindi ho affermato che il mio algoritmo è in \ Omega (n ^ 3) e in \ BigO (n ^ 4). Questa asserzione è corretta e utile?
(mi dispiace per il formato, ma non sono in grado di aggiungere testo LaTeX, quindi se puoi, per favore, dimmi come formattare questo presto, grazie)
Se sei sicuro che n ^ 4 / n ^ 3 è la complessità migliore / peggiore del tuo algoritmo, è certamente corretto affermare che l'algoritmo è in O (n ^ 4) e Omega (n ^ 3) .
Meteo ha senso aggiungere questo alla descrizione degli algoritmi, dipende dal pubblico di destinazione:
La complessità computazionale fornisce una visione molto astratta dell'algoritmo. Per considerazioni teoriche è proprio quello che vuoi. In pratica ci possono essere molte altre proprietà che sono molto più importanti, perché puoi considerare i fattori specifici del problema.
Dipende da ciò che fai in ogni iterazione. Se esegui al massimo un numero costante di calcoli primitivi in ogni iterazione, allora sì il tuo tempo di esecuzione è O (n ^ 4). Tuttavia, Theta (n ^ 3) significherebbe che il tempo di esecuzione ha sia il limite inferiore che superiore n ^ 3, che non ha. Puoi usare Omega (n ^ 3) per indicare il limite inferiore.
Leggi altre domande sui tag complexity