Complessità computazionale

[valder]

Salve ragazzi,sono ad un punto morto con un esercizio/argomento del corso di algoritmi. Purtroppo la prof al momento non può ricevere,ne nessun compagno di corso mi sa fornire delucidazioni chiare sull argomento.

Come si fa a calcolare,date due funzioni,se sono O(g(n)) o viceversa?

Questo è il testo dell esercizio.
-Siano date le seguenti funzioni
Dire se ognuna è O grande dell'altra. In caso affermativo, mostrare una coppia (n0, c), altrimenti fornire una motivazione.

10x^4 se x<100
f(x) = x se x>=100 e quadrato perfetto
4x altrimenti



12x^3 se x multiplo di 5
g(x) =
3x+2 altrimenti


Io cerco di ragionare cosi. Considero dapprima i casi peggiori della f(x),cioè x e 4x...questi li confronto con tutti e due i casi della g(x) ..e quindi x O(12x^3) e O(3x)...idem per 4x...stesso procedimento svolgo per la g(x),che viene confrontata solo con il secondo e terzo caso della f(x),perchè,il primo,essendo per le x<100,non è rilevante.

Procedo nella maniera corretta?
Qualcosa da tener sott'occhio?
Grazie

[Kaamos]

Originariamente inviato da valder
Salve ragazzi,sono ad un punto morto con un esercizio/argomento del corso di algoritmi. Purtroppo la prof al momento non può ricevere,ne nessun compagno di corso mi sa fornire delucidazioni chiare sull argomento.

Come si fa a calcolare,date due funzioni,se sono O(g(n)) o viceversa?

Questo è il testo dell esercizio.
-Siano date le seguenti funzioni
Dire se ognuna è O grande dell'altra. In caso affermativo, mostrare una coppia (n0, c), altrimenti fornire una motivazione.

10x^4 se x<100
f(x) = x se x>=100 e quadrato perfetto
4x altrimenti



12x^3 se x multiplo di 5
g(x) =
3x+2 altrimenti


Io cerco di ragionare cosi. Considero dapprima i casi peggiori della f(x),cioè x e 4x...questi li confronto con tutti e due i casi della g(x) ..e quindi x O(12x^3) e O(3x)...idem per 4x...stesso procedimento svolgo per la g(x),che viene confrontata solo con il secondo e terzo caso della f(x),perchè,il primo,essendo per le x<100,non è rilevante.

Procedo nella maniera corretta?
Qualcosa da tener sott'occhio?
Grazie

(se vuoi mantenere gli spazi usa il tag [CODE])

In queste analisi tralascia anche i fattori moltiplicativi oltre a quelli additivi, si parla di O(x^3) e O(x) piuttosto che di O(12x^3) e O(3x).

Io prima analizzerei le due funzioni singolarmente per vedere di che ordine sono, e poi paragonerei i due risultati dimenticandomi a quel punto dei vari casi delle funzioni.
f(x) è in O(x) perché per x che tende all'infinito la funzione è sempre lineare, x oppure 4x, come dici.
g(x) direi che è esponenziale, perché per x grande può essere 3x+2 o 12x^3, e la seconda ovviamente è di ordine superiore alla prima, quindi g(x) è in O(x^3).

A questo punto è chiaro che f(x) sia in O(g(x)) e non viceversa, gli esponenziali sono asintoticamente superiori ai polinomi; se devi dimostrarlo ti basta applicare la definizione di O(g(x)), ovvero trovare un coefficiente c e un numero x0 t.c.:

f(x) <= c*g(x) per ogni x >= x0
(scritta un po' alla buona - fra l'altro, è per questo c che si possono tralasciare i fattori moltiplicativi)

E di solito è piuttosto semplice dimostrare che un funzione f(x) sia in O(g(x)), basta prendere c e x0 grandi.

[MItaly]

x^3 non è un esponenziale (che sarebbe a^x), è polinomiale (anzi, in effetti è un monomio)

[Kaamos]

Originariamente inviato da MItaly
x^3 non è un esponenziale (che sarebbe a^x), è polinomiale (anzi, in effetti è un monomio)

Sì, ovviamente hai ragione (e l'ho pure scritto più volte).