Ho ragione nel ritenere che questo snippet sia O (n^3)?

collection.Where(i => i.condition) 
.ToList() 
.ForEach(i => SomeComplicatedOpInvolving_i);

Non sto cercando risposte che mi dicano che esiste un modo più semplice per farlo, trattalo come un esperimento mentale.Ho ragione nel ritenere che questo snippet sia O (n^3)?

Per prima cosa, ho ragione nel pensare che si tratta di tre cicli? Where(), ToList() e ForEach()?
In secondo luogo, (supponendo che si tratti di tre cicli) ho ragione nel pensare che questo è n alla potenza di 3 nella notazione O grande?

Grazie a tutti.

fonte

2011-09-01 Adam Naylor

Non dipende da cosa SomeComplicatedOpInvolving_i? – AndrewC

Se si assume che 'collection' sia di tipo' IEnumerable ', allora sarà O (2 * n), a causa del caricamento lento. – ebb

Non utilizzare 'ToList' solo perché non si desidera utilizzare un normale ciclo' foreach() ', poiché la creazione e il riempimento dell'elenco sono di gran lunga l'operazione più intensa in questo snippet. – Dykam

No, in realtà. Penso che dovrebbe essere O (n).

Where() eseguito in O (n) (supponendo condition è costante)

ToList() corre su tutti i risultati di Where e, quindi O (n) anche

ForEach() corre sulla intero elenco prodotto dalla ToList una volta, quindi anche O (n). Presumo che lo SomeComplicatedOpInvolving_i non sia scalabile con il numero di i ...

Il punto chiave qui è che i loop non sono nidificati, corrono uno dopo l'altro - quindi il runtime totale è 3 * O (n), che è uguale a O (n).

fonte

2011-09-01 10:02:29 Peter

+1 per tenere conto della complessità delle sottoespressioni e affermando chiaramente che si può scrivere la complessità di un 3 ma non importa. – delnan

Se vuoi essere pedante, ToList non è O (n), perché a volte deve copiare per crescere :-) – xanatos

Esattamente la spiegazione che stavo cercando grazie per aver dedicato del tempo per scomporla. E 'stato il 3 * n vs n^3 con cui sono stato mescolato. –

No, non sono cicli annidati. È su).

Evitare l'uso di ToList(), che costa memoria O (n) senza una buona ragione. Controlla questo blog post.

fonte

2011-09-01 10:00:41

No, è O(n). Sarebbe solo O(n^3) se ci fosse un ciclo all'interno di un ciclo all'interno di un ciclo.

fonte

2011-09-01 10:00:54

Questo è O(n).

Come Where è O(n) ciò significa che il costo di Where è approssimativamente A x n, per alcuni A.

Allo stesso modo come ToList e ForEach sono anche O(n) che significa che il loro costo è di circa B x n e C x n rispettivo, per qualche B e alcuni C.

Ciò significa che il costo totale è più o meno:

(A x n) + (B x n) + (C x n) 
= (A + B + C) x n 
= D x n

Per alcuni D (non abbiamo mai veramente curato quello A, B e C erano, così anche noi non importa cosa A + B + C è, quindi basta chiamare it D per semplificare la nostra equazione).

Quindi questa operazione è O(n).

fonte

2011-09-01 10:03:12 Justin

collection.Where(i => i.condition) // is O(n) where n is the size of collection 
.ToList() // is O(m) where m is the number if items with i.condition true 
.ForEach(i => SomeComplicatedOpInvolving_i); // O(m) where m is the number if items with i.condition true

Supponendo che SomeComplicatedOpInvolving è O (1), ad esempio non dura più se hai più oggetti.

Dato che

when m is never bigger then n, then 
O(n) + O(m) + O(m) == O(n)

Poi il frammento è O (n)

fonte

2011-09-01 10:03:29

E 'O (collection.Size) * O (SomeComplicatedOpInvolving_i).

fonte

2011-09-01 10:05:40

Ho ragione nel ritenere che questo snippet sia O (n^3)?

risposta

Problemi correlati