Duda del libro

Duda del libro

de Bruno Emanuel Gandos Telis -
Número de respuestas: 1

duda

Buenas noches, leyendo del libro me surgieron las siguientes dudas: primero no entendi como se pudo deducir tan facilmente que ordenar las aristas por coste llevara O(m log(m)), y lo segundo es la desigualdad m<=n^2, tampoco logro ver como se llega a eso, podrian ayudarme? Gracias.

En respuesta a Bruno Emanuel Gandos Telis

Re: Duda del libro

de Fernando Fernandez -
Hola.
Acerca del problema de ordenar conocemos de cursos anteriores algoritmos, mergesort, que tienen ese orden. En el capitulo 2 del libro hay un pequeño repaso de merge y una descripción en alto nivel de mergesort en la sección O( n log n).

Acerca de la cota de m. Como ahí dice, cada arista está determinada por un par de vértices. Entonces la máxima cantidad de aristas que puede haber es n (n-1) en un grafo completo dirigido y n (n-1) /2 en uno no dirigido.