Big O Complessità quando si itera in 3 dimensioni

Question

Big O Complessità quando si itera in 3 dimensioni

#1 da (7 voti)
#2 da (3 voti)
#3 da (0 voti)

1

Che complessità temporale classificheresti come segue?

int n = 100;
for(int x = 0; x < n; x++)
    for(int y = 0; y < n; y++)
        for(int z = 0; z < n; z++)
            DoWork(x,y,z);

Non credo che qualcuno possa obiettare che è O (n ^ 3)

Consideriamo ora uno scenario in cui i limiti per ciascuna dimensione sono forniti come 3 input separati

int bx = 10, by = 1000, bz = 1000
for(int x = 0; x < bx; x++)
    for(int y = 0; y < by; y++)
        for(int z = 0; z < bz; z++)
            DoWork(x,y,z);

Come descriveresti la complessità di quanto sopra? Avrei descritto intuitivamente questo come ancora O (n ^ 3) poiché è ancora necessario iterare in tutte e 3 le dimensioni.

Un amico ha suggerito che la grandezza dell'ingresso entra in gioco e poiché bx è di diversi ordini di grandezza inferiore a by o bz , che dovresti invece definire come O (n ^ 2)

Quale è?

Modifica

Solo per fornire un po 'più di contesto in cui le persone hanno votato per chiudere la domanda.

Questo è uscito da una discussione su AdventOfCode 2018 - Puzzle 6 ( link )

I "limiti" di questo puzzle erano un file di input di 50 righe in cui ogni input definiva un punto. Quindi ogni concorrente stava lavorando su una soluzione limitata da

numero di ingressi: 50 - costante
n = cox max-x: diverso per concorrente - valori di input univoci che abbiamo generato per ciascun utente
m = rapporto max-y: diverso per concorrente - valori di input univoci che abbiamo generato per ciascun utente

Penso basandomi sul feedback qui sotto, che rende il caso migliore O(n*m) come ignoreresti i 50 valori di input costanti.

complexity computer-science big-o

posta Eoin Campbell 07.12.2018 - 18:50

fonte

3 risposte

Leggi altre domande sui tag complexity computer-science big-o

Il modo migliore per trasportare i dati di risposta da una richiesta AJAX? Cosa devo fare quando viene assegnato a un progetto che si basa su una tecnologia che non conosco? [chiuso]

score 7 · Answer 1

Personalmente lo inserisco come O(bx*by*bz) . La ragione è che presumo che i parametri possano cambiare arbitrariamente l'uno con l'altro, ad esempio si potrebbe ottenere il seguente input: bx = 30000, per = 30, bz = 40. Guarda come il grande-Oh ora dipende dal bx, perché è più alto di molti ordini di grandezza? Tuttavia, se tali valori sono sempre costanti, diciamo sempre bx = 10, per = 1000, bz = 1000, quindi sarebbe O (1).

score 3 · Answer 2

La prima cosa che devi studiare dettagliatamente sull'analisi asintotica e l'analisi ammortizzata.

Se consideriamo l'analisi asintotica per il tuo scenario con bx = 10, by = 1000, bz = 1000 come suggerito dal tuo amico se consideri il set di input by e bz allora relativamente bx sta avendo un piccolo valore che può essere considerato costante Tuttavia nel tuo caso tutti questi valori sono costanti e il tempo di esecuzione può essere considerato come O(1) .

Durante il calcolo del limite superiore asintotico Big-O 'O' ignoriamo le costanti.

Tuttavia, se usi solo valori come: %codice% dove la dimensione di input di bx = 1000000000, by = 100000000000, bz = 100000000000 è anche relativamente più alta quindi per definizione di big-o

That is, f(x) = O(g(x)) if and only if there exists a positive real number c and a real number x' such that
f(x) <= c g(x) for all x > x'

puoi indicare la complessità a bx .

Per riassumere nel primo caso hai usato lo stesso valore O(bx*by*bz) per calcolare tutti i loop ma in un altro caso hai usato tre diverse dimensioni di input, quindi la tua complessità sarà sempre n e se uno o più valori di O(bx*by*bz) , bx o by è costante, quindi puoi ometterlo.

score 0 · Answer 3

C'è un grande, importante dettaglio mancante nelle altre risposte alla domanda qui. Questo:

int n = 100;
for(int x = 0; x < n; x++)
    for(int y = 0; y < n; y++)
        for(int z = 0; z < n; z++)
            DoWork(x,y,z);

è non un algoritmo O(n^3) cubico. Il suo runtime dipende dal valore del singolo input n , non dalla dimensione di l'input chiamato n . Questo programma viene eseguito in tempo pseudo-polinomiale perché è polinomiale in valore numerico del suo input ma in realtà è esponenziale nella dimensione del suo input (che è log_2(n) , il numero di bit necessari per rappresentarlo) .

Le altre risposte sono quindi corrette che il tuo algoritmo funziona in O(bx * by * bz) , ma la tua affermazione che

I would have intuitively described this as still being O(n^3) as you still need to iterate in all 3 dimensions.

è sbagliato. Big-O conta il numero di operazioni, non la profondità di un nido di loop.