(Mis disculpas si este es un duplicado; hice algunas búsquedas, pero no nada más como este en el sitio. Por favor, hágamelo saber si es un duplicado y estaré encantado de eliminarlo.)
Yo estaba leyendo en varios gráfico de algoritmos de Dijkstra el algoritmo y algunas variantes) y se encontró que el tiempo de ejecución $O(m + n \log n)$ donde $m$ es el número de aristas en el grafo y $n$ es el número de nodos. Intuitivamente, esto tiene sentido, pero hace poco me di cuenta de que no sé, formalmente, lo que significa esta declaración.
La definición de big-O la notación que estoy familiarizado con las preocupaciones de una sola variable funciones; es decir, $f(n) = O(g(n))$ si $\exists n_0, c$ tal que $\forall n > n_0. |f(n)| \le c|g(n)|$. Sin embargo, esta definición no tiene sentido que algo como $O(m + n \log n)$, ya que hay dos parámetros libres aquí - $m$$n$. Aunque en el contexto de los gráficos no están bien especificadas las relaciones entre el$m$$n$, en algunos otros algoritmos (por ejemplo, string matching) el tiempo de ejecución puede ser descrito como $O(f(m, n))$ donde $m$ $n$ son completamente independientes el uno del otro.
Mi pregunta es esta: ¿cuál es la definición formal de la declaración de $f(m, n) = O(g(m, n))$? Es una simple generalización de la definición de una variable donde damos a los límites inferiores en ambos $m$ $n$ que debe ser al mismo tiempo satisfecho, o hay algún otra definición se define en términos de límites?
Gracias!
