Complessità di tempo ciclo for

[*MATRIX*]

Ciao raga sapreste dirmi qual'è la complessità di una procedura che al suo interno ha due cicli for non annidiati??? Non so se è 0(n) oppure 0(n^2)
grazie per le risposte bye bye

[sottovento]

Immagino che i cicli for di cui parli servano a far qualcosa, e che tu stia cercando di valutare, appunto, detta complessita'.

Cmq se non sono annidati, e' O(n).
Il fatto che siano due cicli non annidati, altro non fa che cambiare una costante, che come ben sai viene 'annegata' nell'operatore in questione

High Flying
Sottovento

[*MATRIX*]

Cmq scusami avevo sbaglito a scrivere il mio dubbio era tra O(n) e 2*0(n)

[sottovento]

Nessuna scusa, mica hai offeso qualcuno
Cmq e' O(n)

[*MATRIX*]

grazie

[leadergl]

Originariamente inviato da *MATRIX*

Cmq scusami avevo sbaglito a scrivere il mio dubbio era tra O(n) e 2*0(n)

diciamo che 2O(n) non si può dire...poichè O(n) è una stima asintotica della complessità, esempio:

Se il calcolo della complessità delle varie parti di un algoritmo era: 3N + 5N + 2 allora la sua complessità era O(n).

Mentre se veniva, ad esempio, 3N + 5N + N^2 + 2 allora la complessità ora O(n^2).

Questo per dire che quando si parla in termini di complessità asintotiche, nelle loro tipologie, si da una stima...un po come quando dici "equazioni di primo grado" ed "equazioni di secondo grado", indichi una categoria ma non sono tutte uguali.

[cdimauro]

Esattamente. Poi c'è anche da dire che se il primo ciclo è O(n) e il secondo è O(m), la complessità sarà O(n + m).

[VegetaSSJ5]

Originariamente inviato da cdimauro

Esattamente. Poi c'è anche da dire che se il primo ciclo è O(n) e il secondo è O(m), la complessità sarà O(n + m).

supponendo che il numero di esecuzioni del primo ciclo for sia dell'ordine O(n) e che quello del secondo sia di O(m) la complessità totale è dell'ordine di O(n * m).
poi se m si può approssimare ad n possiamo dire che a complessità è di O(n^2)

[beppegrillo]

Ma infatti anche a me risulta sia O(n^2)..

[VegetaSSJ5]

Originariamente inviato da beppegrillo

Ma infatti anche a me risulta sia O(n^2)..

ripeto che non è O(n^2)... è O(n^2) solo se m è dello stesso ordine di grangezza di n, cioè se m è teta grande di n.
se vogliamo proprio fare i pignoli la complessità dell'algoritmo rispetto ad n e m che sono riepsttivamente l'ordine di grandezza del numero di esecuzioni del primo for e di quello annidato può essere di uno di questi casi:

- n ~ O(m) --> m ~ o(n) --> complessità O(n)
- n ~ m (teta grande di m, non c'è il simbolo sulla tastiera ) --> complessità O(n^2)
- n ~ o(m) --> m ~ O(n) --> complessità O(m)
- m ~ teta di log(n) --> complessità O(n * log(n))
- n ~teta di log(m) --> complessità O(m * log(m))

[fuocofatuo]

Ma lui ha detto che i cicli NON sono annidiati, perciò è corretto O(n+m).

[VegetaSSJ5]

Originariamente inviato da fuocofatuo

Ma lui ha detto che i cicli NON sono annidiati, perciò è corretto O(n+m).

hai ragione non avevo letto bene!
anche in questo caso però devo correggervi. per definizione, le notazioni di O (o grande), o (o piccolo) e § (scusate se la indico così, visto che non c'è il simbolo sulla tastiera, ma voglio intendere teta grande) non riguardano le costanti moltiplicative (figuriamoci quindi l'addizione...). questo vuol dire che se io ho un numero n scrivere O(n) e scrivere O(n*10000000000000000) è la stessa cosa in quanto queste sono notazione riferite a variabili che tendono a + infinito per cui qualsiasi costante moltiplicativa (che sia 9999999999 oppure 0,0000000000001) non avrebbe peso ai fini del calcolo dell'ordine di grandezza, che è il vero scopo per cui esistono queste notazioni.
in questo specifico problema quindi, la complessità dell'intero algoritmo è pari a:

- n ~ o(m) --> complessità O(m)
- m ~ o(n) --> complessità O(n)
- m ~ teta di log(n) --> complessità O(n)
- n ~ teta di log(m) --> complessità O(m)

[Brazorv]

Originariamente inviato da VegetaSSJ5

hai ragione non avevo letto bene!
anche in questo caso però devo correggervi. per definizione, le notazioni di O (o grande), o (o piccolo) e § (scusate se la indico così, visto che non c'è il simbolo sulla tastiera, ma voglio intendere teta grande) non riguardano le costanti moltiplicative (figuriamoci quindi l'addizione...). questo vuol dire che se io ho un numero n scrivere O(n) e scrivere O(n*10000000000000000) è la stessa cosa in quanto queste sono notazione riferite a variabili che tendono a + infinito per cui qualsiasi costante moltiplicativa (che sia 9999999999 oppure 0,0000000000001) non avrebbe peso ai fini del calcolo dell'ordine di grandezza, che è il vero scopo per cui esistono queste notazioni.
in questo specifico problema quindi, la complessità dell'intero algoritmo è pari a:

- n ~ o(m) --> complessità O(m)
- m ~ o(n) --> complessità O(n)
- m ~ teta di log(n) --> complessità O(n)
- n ~ teta di log(m) --> complessità O(m)

secondo me stai facendo un pò di confusione. Tu stai parlando di costanti, ma in questo caso n ed m non sono costanti, ma sono le variabili che definiscono la complessità dell'algoritmo, per cui ha senso scrivere O(n+m).

[VegetaSSJ5]

Originariamente inviato da Brazorv

secondo me stai facendo un pò di confusione. Tu stai parlando di costanti, ma in questo caso n ed m non sono costanti, ma sono le variabili che definiscono la complessità dell'algoritmo, per cui ha senso scrivere O(n+m).

non ci siamo capiti, cerco di essere più chiaro...

- se n è minore di m (ovvero n~ o(m)) allora non ha senso sommare ad m che è di almeno un ordine di grandezza superiore un numero n di grandezza inferiore. si deduce che la complesità in questo caso è pari a O(m)
- se n è magigore di m (ovvero m~ o(n)) vale il discorso contrario e la complessità è O(n)
- se n e m sono dello stesso ordine di grandezza allora dire O(n+m) significherebbe dire O(2*n) oppure O(2*m) che secondo queste notazioni equivarrebbe a dire O(n) oppure O(m)

spero di essere stato più chiaro...

EDIT
se n e m sono dello stesso ordine di grandezza allora vorrebbe dire che O(n+m) è assimilabile a O(2*n) ma anche a O(10000000000*n) - con la stessa cosa che vale anche per m. quindi più in generale O(n+m) ~ O(k*n) ~ O(k*m) con k costante.

[Brazorv]

Originariamente inviato da VegetaSSJ5

non ci siamo capiti, cerco di essere più chiaro...

- se n è minore di m (ovvero n~ o(m)) allora non ha senso sommare ad m che è di almeno un ordine di grandezza superiore un numero n di grandezza inferiore. si deduce che la complesità in questo caso è pari a O(m)
- se n è magigore di m (ovvero m~ o(n)) vale il discorso contrario e la complessità è O(n)
- se n e m sono dello stesso ordine di grandezza allora dire O(n+m) significherebbe dire O(2*n) oppure O(2*m) che secondo queste notazioni equivarrebbe a dire O(n) oppure O(m)

spero di essere stato più chiaro...

EDIT
se n e m sono dello stesso ordine di grandezza allora vorrebbe dire che O(n+m) è assimilabile a O(2*n) ma anche a O(10000000000*n) - con la stessa cosa che vale anche per m. quindi più in generale O(n+m) ~ O(k*n) ~ O(k*m) con k costante.

tu fai delle supposizioni sulle variabili n ed m, ma ogni istanza del problema può avere diversi valori di n e di m, ed in generale noi non possiamo sapere che relazione ci sia tra n ed m. La notazione O(n+m) serve ad indicare che l'algoritmo dipende in modo lineare dai paramtri n ed m.

[VegetaSSJ5]

Originariamente inviato da Brazorv

tu fai delle supposizioni sulle variabili n ed m, ma ogni istanza del problema può avere diversi valori di n e di m, ed in generale noi non possiamo sapere che relazione ci sia tra n ed m. La notazione O(n+m) serve ad indicare che l'algoritmo dipende in modo lineare dai paramtri n ed m.

si per questo si dovrebbe esaminare il problema, ma quello che ho detto rimane comunque vero, è matematica, mica un'opinione!

[Brazorv]

si dal punto di vista della complessità O(n) O(m) oppure O(n+m) sono tutti algoritmi lineari, il discorso che volevo fare io è che in questo caso è giusto scrivere O(n+m) perchè si specifica meglio da cosa dipende la complessità dell'algoritmo. Non è solo una questione matematica.

[cdimauro]

Originariamente inviato da VegetaSSJ5

si per questo si dovrebbe esaminare il problema, ma quello che ho detto rimane comunque vero, è matematica, mica un'opinione!

Non c'è nulla da esaminare: non ti puoi mettere a vedere caso per caso.
Infatti la notazione che ho riportato è quella giusta quando si ha che la complessità (o velocità) di un algoritmo dipende da più variabili.

[beppegrillo]

Originariamente inviato da beppegrillo

Ma infatti anche a me risulta sia O(n^2)..

avevo capito che si trattasse di due cicli for su n .