Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

[Algoritmi, complessità counting sort]

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

Re: [Algoritmi, complessità counting sort]

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!

Re: [Algoritmi, complessità counting sort]

08/12/2019, 21:00

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


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

Re: [Algoritmi, complessità counting sort]

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).

Re: [Algoritmi, complessità counting sort]

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 ?

Re: [Algoritmi, complessità counting sort]

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.
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.