Comprender el cálculo de la complejidad del tiempo para el algoritmo de Dijkstra

Posterior a de esta extensa búsqueda de información hemos podido resolver esta duda que presentan ciertos usuarios. Te ofrecemos la solución y deseamos servirte de gran ayuda.

Solución:

El algoritmo de ruta más corta de Dijkstra es O(ElogV) dónde:

• V es el número de vértices
• E es el número total de aristas

¡Tu análisis es correcto, pero tus símbolos tienen significados diferentes! Dices que el algoritmo es O(VElogV) dónde:

• V es el número de vértices
• E es el número máximo de aristas asociadas a un solo nodo.

Cambiemos el nombre de su E a N. Entonces un análisis dice O(ElogV) y otro dice O(VNlogV). Ambos son correctos y de hecho E = O(VN). la diferencia es que ElogV es una estimación más estricta.

Sea n el número de vértices y m el número de aristas.

Ya que con el algoritmo de Dijkstra tienes O(n) eliminar-mins y O(m) disminuir_claves, cada uno con un costo de O(logn), el tiempo de ejecución total usando montones binarios será O(log(n)(m + n)). Es totalmente posible amortizar el costo de disminuir_clave hasta O(1) utilizando montones de Fibonacci, lo que da como resultado un tiempo de ejecución total de O(nlogn+m), pero en la práctica esto no suele hacerse, ya que las penalizaciones de factor constante de los FH son bastante grandes y, en gráficos aleatorios, la cantidad de disminuir_claves es mucho más bajo que su límite superior respectivo (más en el rango de O(n*log(m/n), que es mucho mejor en gráficos dispersos donde m = O(n)). Así que siempre tenga en cuenta el hecho de que el tiempo de ejecución total depende de sus estructuras de datos y de la clase de entrada.

Agregar una explicación más detallada como lo entendí por si acaso:

• O(para cada vértice usando el montón mínimo: para cada borde linealmente: empuje los vértices al montón mínimo al que apunta el borde)
• V = número de vértices
• O(V * (pop vértice del montón mínimo + encontrar vértices no visitados en los bordes * empujarlos al montón mínimo))
• E = número de aristas en cada vértice
• O(V * (pop vértice del montón mínimo +E* empujar los vértices no visitados al montón mínimo)). Tenga en cuenta que podemos presionar el mismo nodo varias veces antes de “visitarlo”.
• O(V * (log(tamano de la pila) + E * log(tamano de la pila)))
• O(V * ((E + 1) * log(tamano de la pila)))
• O(V * (E * log(tamano de la pila)))
• E = V porque cada vértice puede hacer referencia a todos los demás vértices
• O(V * (V * log(tamano de la pila)))
• O(V^2 * log(tamano de la pila))
• el tamaño del montón es V^2 porque lo presionamos cada vez que queremos actualizar una distancia y podemos tener hasta V comparaciones para cada vértice. Por ejemplo, para el último vértice, el primer vértice tiene una distancia 102do tiene 93ro tiene 8etc, entonces, presionamos cada vez para actualizar
• O(V^2 * log(V^2))
• O(V^2 * 2 * log(V))
• O(V^2 * log(V))
• V^2 es también un número total de aristas, así que si dejamos E = V^2 (como en el naming oficial), obtendremos el O(E * log(V))

Reseñas y puntuaciones de la guía

Agradecemos que desees reafirmar nuestro quehacer fijando un comentario y dejando una puntuación te lo agradecemos.

---

---

Utiliza Nuestro Buscador