Cosa è considerato un miglioramento asintotico per gli algoritmi dei grafici?

Question

Diciamo che stiamo cercando di risolvere qualche problema algoritmico $A$ che dipende dall'input della dimensione $n$.Diciamo algoritmo $B$ che corre nel tempo $T(n)$, è asintoticamente migliore dell'algoritmo $C$ che corre nel tempo $G(n)$ se abbiamo:$G(n) = O(T(n))$, Ma $T(n)$ non è $O(G(n))$.

La mia domanda è legata al tempo di esecuzione asintotico degli algoritmi grafici, da cui di solito dipende $|V|$ E $|E|$.Nello specifico voglio concentrarmi sull'algoritmo di Prim.Se implementiamo la coda con priorità con un heap binario, il tempo di esecuzione sarebbe $O(E\logV)$.Con l'heap di Fibonacci potremmo ottenere un tempo di esecuzione di $O(V\log V + E)$.

La mia domanda è: lo diciamo? $O(V\log V + E)$ è asintoticamente migliore di $O(E\logV)$?

Vorrei chiarire:So che se il grafico è denso la risposta è sì.Ma se $E=O(V)$ entrambe le soluzioni sono identiche.Sono più interessato a ciò che è di solito definito come miglioramento asintotico nel caso in cui abbiamo più di una variabile e, peggio ancora, le variabili non sono indipendenti ($V-1\le E<V^2$, poiché assumiamo che il grafo sia connesso per l'algoritmo di Prim).

Grazie!

Answer 1

La definizione più permissiva è la seguente.

Supporre che $f(V,E),g(V,E)$ sono due tempi di esecuzione di algoritmi grafici che risolvono lo stesso problema.

Lo diciamo $f$ è un miglioramento asintotico in alcuni regimi SU $g$ se esiste una sequenza $V_n,E_n$ con $V_n \a \infty$ tale che$$ lim_ {n to infty} frac {f (v_n, e_n)} {g (v_n, e_n)} = 0.$$

A volte il regime non è ritenuto interessante, ma questa è una questione più soggettiva.

Si noti inoltre che il problema si manifesta già per le funzioni a una variabile.Prendere in considerazione$$ f (n) = n^2, qquad g (n) = inizio {casi} 2^n & text {if} n = 2^m, n & text {altrimenti}.\end{casi} $$È $f$ un miglioramento asintotico oltre $g$?È per input di una certa lunghezza, ed è effettivamente così secondo la nostra definizione permissiva di cui sopra.