PDA

Visualizza la versione completa : [Algoritmi e strutture dati] Problemi con complessità asintotiche


Ethoel
05-09-2013, 11:04
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 :) :ciauz:

cigiri18
05-09-2013, 18:33
La complessità asintotica puoi vederla come un modo rapido per fare conti a spanne sulla durata di un algoritmo.

O(n^2) sta a significare che, in quel dato caso, il tempo di esecuzione, calcolato in funzione del numero di cose con cui si lavora, ha andamento al più quadratico.

Per la definizione matematica delle varie complessità vedi qui http://it.wikiversity.org/wiki/Complessit%C3%A0_asintotica. credevo di ricordarmi tutto decentemente, invece ho già rimosso.

Per le domande, sono tutte giuste, ma mi sento di darti 2/4, già solo perché hai scritto due volte le stesse domande :messner:

Ethoel
06-09-2013, 15:13
XD ho copia-incollato il testo dell'esercizio, quindi è proprio così come lo leggi.

Beh già che 2/4 sia giusto mi conforta, grazie del link, ora mi mangio l'argomento (e la prof all'esame)

cigiri18
06-09-2013, 19:26
Colpa mia, è theta, non omega.

Dovrebbero esser giuste anche le altre due

Loading