> Esto: O(m + n log n) equivale a esto O(nlogn) ya que siempre se coje el limite superior y se obvia el resto.
No, me temo que te equivocaste pensando que "m" es una constante, como si fuese independiente de n... Pero NO.
El "m" es el número de aristas y si aumentas "n" debes aumentar "m", al menos en el contexto de Dijkstra que se trata de rutas y encaminamiento.
Si tienes "n" vértices, y si ningún vértice está desconectado, tendrás que tener mínimo m = n-1 aristas para conectar los n vértices.
Y el máximo m en grafos dirigidos es n^2 si admitimos que un vértice esté conectado a sí mismo, o bien, n•(n-1) si no lo permitimos.
Entonces,
O(m + n log n) estaría entre:
Mínimo : O(n-1 + n log n) ~ O(n log n)
Máximo : O(n^2 + n log n ) ~ O(n^2)
Luego, en tu comparativa de Wolfram has cambiado "m" por n... Pero, como dije antes, m podría ser del orden de n^2 ... aunque es cierto que si es del orden de… » ver todo el comentario
> Entonces el nuevo algoritmo mejora a diskjtra tanto en el mejor como en el peor caso lo cual es decir muchisimo.
Dijkstra
[Nota: tiene ijk , que son letras consecutivas en el abecedario, y que, además, son letras usadas como índices en sumatorios y algoritmos de programación... For i = 1... For j = ... For k = ...]
Y... NO, en el caso peor el nuevo algoritmo propuesto EMPEORA, no mejora al de Dijsktra, cuando n tiende a infinito.
El caso peor es m ~ n^2
O( n^2 • log^(2/3) n )
es peor que
O (n^2 + n log n) ~ O(n^2)
> Esto: O(m + n log n) equivale a esto O(nlogn) ya que siempre se coje el limite superior y se obvia el resto.
No, me temo que te equivocaste pensando que "m" es una constante, como si fuese independiente de n... Pero NO.
El "m" es el número de aristas y si aumentas "n" debes aumentar "m", al menos en el contexto de Dijkstra que se trata de rutas y encaminamiento.
Si tienes "n" vértices, y si ningún vértice está desconectado, tendrás que tener mínimo m = n-1 aristas para conectar los n vértices.
Y el máximo m en grafos dirigidos es n^2 si admitimos que un vértice esté conectado a sí mismo, o bien, n•(n-1) si no lo permitimos.
Entonces,
O(m + n log n) estaría entre:
Mínimo : O(n-1 + n log n) ~ O(n log n)
Máximo : O(n^2 + n log n ) ~ O(n^2)
Luego, en tu comparativa de Wolfram has cambiado "m" por n... Pero, como dije antes, m podría ser del orden de n^2 ... aunque es cierto que si es del orden de… » ver todo el comentario
> Entonces el nuevo algoritmo mejora a diskjtra tanto en el mejor como en el peor caso lo cual es decir muchisimo.
Dijkstra
[Nota: tiene ijk , que son letras consecutivas en el abecedario, y que, además, son letras usadas como índices en sumatorios y algoritmos de programación... For i = 1... For j = ... For k = ...]
Y... NO, en el caso peor el nuevo algoritmo propuesto EMPEORA, no mejora al de Dijsktra, cuando n tiende a infinito.
El caso peor es m ~ n^2
O( n^2 • log^(2/3) n )
es peor que
O (n^2 + n log n) ~ O(n^2)