Sembra una domanda stupida, ma è una specie di muro e non riesce ad entrarmi per bene in testa questo concetto.
Praticamente devo dare un esame di algoritmi all'università e tra i vari esercizi ce ne sarà uno all'incirca come questo:
1. Se si dimostra che un algoritmo ha tempo di esecuzione O(n^2) nel caso peggiore, è possibile che in qualche caso l'algoritmo termini in O(n) passi?
2. Se si dimostra che un algoritmo ha tempo di esecuzione O(n^2) nel caso peggiore, è possibile che l'algoritmo termini in O(n) passi in tutti i casi?
3. Se si dimostra che un algoritmo ha tempo di esecuzione Θ(n^2) nel caso peggiore, è possibile che in qualche caso l'algoritmo termini in O(n) passi?
4. Se si dimostra che un algoritmo ha tempo di esecuzione Θ(n^2) nel caso peggiore, è possibile che l'algoritmo termini in O(n) passi in tutti i casi?
Ecco le mie risposte:
1. Vero, perchè l'O(n^2) indica che un algoritmo può avere tempo di esecuzione "al più" come n^2, non esclude che ci siano casi in cui l'algoritmo sia più efficiente
2. Falso, ciò implicherebbe che il caso peggiore sarebbe O(n)
3. Vero, ci possono essere dei casi medi o migliori in cui l'algoritmo terminerebbe in O(n) passi.
4. Falso, Θ(n^2) indica che nel caso peggiore l'algoritmo terminerebbe in un intorno di O(n^2) e Ω(n^2) passi.
Sicuramente sono 4/4 sbagliate, non mi entra in testa questo ragionamento sulle complessità asintotiche nonostante mi sia chiuso per mesi sul libro XD
Qualcuno mi può dare una mano? Non c'è bisogno che spiegate interamente l'argomento (su un forum sarebbe impossibile), mi basta solo una delucidata su questi 4 punti dell'esercizio.
Grazie a tutti fin da ora per l'aiuto
Rispondi quotando
