Somma regola per Big-O con parità di complessità-funzioni?

Question

Una proprietà della Big-O-notation è il regola della somma , che afferma che quando ho due funzioni $ f_1 $ e $ f_2 $ e le loro corrispondenti funzioni di complessità sono $ G_1 $ e $ G_2 $ , quindi la complessità combinata è F_1 + F_2= O (\ MAX (G_1, G_2)) $ .

Ma cosa prendiamo se entrambe le funzioni di complessità sono uguali? Ad esempio, se $ f_1 (n) $ è l'ordinamento di un array e $ _ f2 (m) $ Inoltre, le complessità sono $ o (n \ log (n)) $ e $ o (m \ log ( m)) $ . L'applicazione della regola sarebbe $ o (\ max (n \ log (n), m \ log (m))) $ . Penso che scegliere uno di questi produrrebbe una stima valida ma molto poco inuitiva come caderebbe una variabile. Oltre a ciò, non è chiaro quale scegliere.

è il caso in cui non si suppone di utilizzare la regola quando ci sono più variabili coinvolte?

Answer 1

Dipende da se alcune variabili dipendono da un altro, o se vengono fornite come parametri nel problema. Ad esempio, in molti problemi relativi al grafico, $ N $ può essere il numero di vertici e $ m $ può essere il numero di bordi. In questo caso, $ m $ può essere grande come $ o (n ^ 2) $ . Quindi, nel caso generale, ad esempio se abbiamo un algoritmo la cui prima fase viene eseguita in $ o (n) $ e la seconda fase funziona in $ O (m) $ , aggiungiamo solo i due termini insieme e non tentiamo di semplificare --- il runtime finale è $ o (n + m) $ .

In termini di diverse variabili dati come parametri che non sono necessariamente correlati: l'equipaggiamento più variabili all'interno dell'equazione finale è standard, ad es. Posso dire che moltiplicando una classe $ m \ volte N $ matrice e una classe $ n \ volte P $ matrice prende $ o (MNP) $ -time utilizzando la moltiplicazione della cartella scolastica o risolvere il problema dello zaino prende $ o (NT) $ < / span> -time dove $ N $ è il numero di elementi e $ T $ è la somma di destinazione .

In casi speciali come grafici planare e altri grafici sparsi, sappiamo che $ m= o (n) $ , quindi possiamo tranquillamente sostituire $ N $ al posto di $ m $ nel tempo di esecuzione finale per la semplificazione.

Come digressione, questo illustra perché sui grafici sparse (dove $ m= o (n) $ ) uno preferirebbe usare dijktra in un anello per tutti coppie il percorso più breve (in contrasto con un algoritmo a base di chiusura transitiva come Floyd-Warshall); Poiché ora Dijkstra funziona in $ o (m \ log n)= o (n \ log n) $ , la complessità complessiva per l'utilizzo di Dijkstra in un anello diventa $ o (n ^ 2 \ log n) $ , che è meglio di Floyd-Warshall. Al contrario, notare che Dijkstra funziona in $ m \ log n $ per il caso generale, il che significa sui grafici densi in cui m= o (n ^ 2) $ , diventa meno efficiente di Floyd-Warshall in termini di tempo di esecuzione del caso peggiore.

In altri casi, ci possono essere variabili non sono nemmeno delimitate in polinomia da un determinato parametro --- prendere l'esempio di zaino sopra, dove $ T $ può essere Esponenziale in $ N $ .

Answer 2

Non c'è risposta generale.A proposito, se si desidera semplificare la $ o (\ max (n \ log (n), m \ log (m))) $ , è possibile riscrivereCome come $ O ((N + M) \ Log (N + M)) $ .

Inoltre, se $ G_1 $ e $ G_2 $ sono eqaul e aumentando le funzioni, puoi scrivere $ O (G_1 (N + M)) $ anziché $ o (\ max (G_1 (n), G_2 (m)))) $ .

Answer 3

per definizione $ o (g) $ deve essere sempre definita la variabile e il punto limite rispetto a quanto considerare $ o $ . Ad esempio in $ o (n ^ 3), n \ to \ Infty $ variabile è $ n $ e punto limite $ \ Infty $ . In $ o (x ^ 3), x \ a 0 $ variabile è $ x $ e punto limite $ 0 $ .

Quindi quando scriviamo $ f= o (g) $ , quindi formalmente intendiamo qualche variabile e un punto limite. Ad esempio $ F (n)= o (G (n)), n \ to \ Infty $ è un record esatto. Nota, che record $ f (m)= o (g (m)), m \ to \ Infty $ significa esattamente uguale alla frase precedente.

Quando stiamo parlando di proprietà $ f_1 + f_2= o (\ max (G_1, G_2)) $ , quindi anche qui dovrebbe essere dichiarato alcune variabili (s ) E un certo punto limite. Quindi il record esatto dovrebbe essere qualcosa di simile $$ F_1 (n) + f_2 (n)= o (\ max (G_1, G_2) (n)), n \ a Infty $$ O abbiamo bisogno di più chiarimenti rispetto alle variabili, assumendo il punto limite $ \ INFTY $ .