Come dovrei esprimere la complessità di due loop annidati su dataset diversi nella notazione Big O?

Question

Come dovrei esprimere la complessità di due loop annidati su dataset diversi nella notazione Big O?

#1 da (3 voti)

1

Sto più o meno insegnando a me stesso una grande notazione O, quindi per favore perdonami se questo è un duplicato di una domanda che si applica alla mia domanda senza che io abbia la saggezza di realizzarlo. Per il mio divertimento / sviluppo personale, sto cercando di esprimere la complessità di una funzione che funziona su 2 set di dati diversi che si riferiscono l'un l'altro: ho bisogno di scorrere su un elenco, e per ogni elemento in un elenco, scorrere su un altro elencare il controllo se gli articoli sono correlati.

Pseudocodice:

for things in list_a {
  for things in list_b {
    if (list_a.thing relates to list_b.thing) go ping
  }
}

Quello che ho attualmente sulla carta è O (n) * O (m), ma mi chiedo se debba essere espresso come O (n * m) invece, dove n = dimensione dell'insieme b e m = dimensione di set a? O è qualcos'altro interamente? Ancora una volta, mi scuso se si tratta di una domanda stupida / duplicata, ma non sono riuscito a trovare nessuno che specificasse specificamente un ciclo annidato su due set di dati diversi. Questa risposta suggerirebbe che si tratta di O (n ^ 2), ma questo mi sembra sbagliato, dal momento che le dimensioni di i due set di dati stessi sono diversi e indipendenti.

big-o

posta Toadfish 08.02.2016 - 06:17

fonte

1 risposta

Leggi altre domande sui tag big-o

Dove memorizzare standalone.xml e altri file in modo che sia accessibile nel mio server CI? Posso applicare l'override dei metodi GetHashCode () ed Equals () per gli utenti di una classe contenitore generica?

score 3 · Accepted Answer

Sarebbe O (n * m) dove il caso peggiore è n = m o n * n quindi O (n ^ 2). Siamo interessati al tempo di esecuzione del caso peggiore per Big O. Se le dimensioni dei set di dati sono diverse, sarà comunque in O (n ^ 2) poiché non possiamo garantire che, ad esempio, il secondo set di dati sia una relazione logaritmica al primo Se potessimo, non sarebbero necessariamente indipendenti. Potrebbero esserlo ma, di nuovo, guardiamo al caso peggiore e O (nlogn) è all'interno di O (n ^ 2).

Un esempio potrebbe essere un algoritmo che coinvolge spigoli e nodi in un grafico. Nel peggiore dei casi, potresti avere ogni nodo connesso ad ogni altro nodo ma non sarai mai in grado di essere certo che esiste una relazione specifica tra i due in anticipo senza alcun tipo di pre-elaborazione.