[Algoritmi, complessità counting sort]

Messaggioda zio_mangrovia » 08/12/2019, 13:38

In questo algoritmo non capisco la complessità $O(n+k)$, in particolare se terzo for non ci fosse la complessità dell'algoritmo sarebbe ugualmente $O(n+k)$ ?
La complessità non dovrebbe essere $O(max(n,k))$ che a mio avviso non è la stessa cosa di $O(n+k)$,
dove sbaglio?

Immagine
zio_mangrovia
Senior Member
Senior Member
 
Messaggio: 994 di 1007
Iscritto il: 13/06/2016, 17:42

Re: [Algoritmi, complessità counting sort]

Messaggioda probid » 08/12/2019, 17:39

zio_mangrovia ha scritto:$O(max(n,k))$ che a mio avviso non è la stessa cosa di $O(n+k)$

https://math.stackexchange.com/questions/291465/formally-prove-that-theta-maxf-g-thetafg/

Ciao!
probid
Starting Member
Starting Member
 
Messaggio: 35 di 40
Iscritto il: 01/10/2010, 19:30

Re: [Algoritmi, complessità counting sort]

Messaggioda zio_mangrovia » 08/12/2019, 21:00



Grazie 1000.
Ma il terzo for preso da solo ha complessità $O(k)$ ? E' corretto?
zio_mangrovia
Senior Member
Senior Member
 
Messaggio: 995 di 1007
Iscritto il: 13/06/2016, 17:42

Re: [Algoritmi, complessità counting sort]

Messaggioda vict85 » 09/12/2019, 08:02

zio_mangrovia ha scritto:


Grazie 1000.
Ma il terzo for preso da solo ha complessità $O(k)$ ? E' corretto?


No. Devi ragionare sul while. La somma dei valori dell'array C è uguale a \(n\), quindi quel while è vero per \(n\) volte ed è falso per \(k\) volte (ad un certo punto diventa falso ed esce dal ciclo).
vict85
Moderatore
Moderatore
 
Messaggio: 10015 di 10111
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi, complessità counting sort]

Messaggioda zio_mangrovia » 09/12/2019, 09:52

vict85 ha scritto:No. Devi ragionare sul while.
La somma dei valori dell'array C è uguale a \(n\)

Questo è ok.


quindi quel while è vero per \(n\) volte ed è falso per \(k\) volte (ad un certo punto diventa falso ed esce dal ciclo).

Non mi torna tanto...
Il while è vero per \(n\) volte però solo complessivamente: per ogni iterazione del for il while può essere vero ma per un numero limitato di valori che può non essere \(n\)

k=4
n=10
i=0 while vero per 1 volte
i=1 while vero per 0 volte
i=2 while vero per 4 volte
i=3 while vero per 5 volte
i=4 while vero per 0 volte

E' vero che alla fine complessivamente ho \(n\) iterazioni ma anche \(k\) dettate dal for, no?
Allora qual è la complessità di quest'ultima parte ?
zio_mangrovia
Senior Member
Senior Member
 
Messaggio: 996 di 1007
Iscritto il: 13/06/2016, 17:42

Re: [Algoritmi, complessità counting sort]

Messaggioda vict85 » 09/12/2019, 11:31

Quello che intendevo è che la condizione del while viene calcolata complessivamente \(n+k\) volte, di cui n vere e k false.
vict85
Moderatore
Moderatore
 
Messaggio: 10016 di 10111
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 6 ospiti