Atascado con notación O

Question

Estoy comparando dos algoritmos, Prim y Kruskal.

entiendo el concepto básico de la complejidad del tiempo y cuando los dos funcionan mejor (/ grafos densos dispersos)

Lo encontré en Internet, pero estoy luchando para convertirlo en Inglés.

dense graph: Prim = O(N2) 
       Kruskal = O(N2*log(N)) 

sparse graph: Prim = O(N2) 
       Kruskal = O(N log(N)) 

Es un poco de una posibilidad remota, pero podría alguien explicar lo que está pasando aquí?

Answer 1

Prim es O (N^2), donde N es el número de vértices.

Kruskal es O (E log E), donde E es el número de aristas. El "E log E" proviene de un buen algoritmo que ordena los bordes. Luego puede procesarlo en tiempo E lineal.

En un gráfico denso, E ~ N^2. Entonces Kruskal sería O (N^2 log N^2), que es simplemente O (N^2 log N).

Answer 2

OK, aquí va. O (N2) (2 = cuadrado) significa que la velocidad del algoritmo para N grande varía como el cuadrado de N; por lo tanto, el doble del tamaño del gráfico dará como resultado cuatro veces el tiempo para calcular.

Las filas de Kruskal se simplifican y suponen que E = c * N2. c aquí es presumiblemente una constante, que podemos suponer que es significativamente menor que N ya que N se hace grande. Necesita conocer las siguientes leyes de logaritmos: log(ab) = log a + log b y log(a^n) = n * log a. Estos dos combinados con el hecho de que log c < < log N (es mucho menor que y se puede ignorar) deben permitirle comprender las simplificaciones allí.

Ahora, en cuanto a las expresiones originales y de dónde se derivaron, necesitaría verificar la página de la que las obtuvo. Pero supongo que si miras a Prim y Kruskal, podrás entender la derivación, o al menos eso, si no puedes, que yo te lo explique no te va a ayudar en el largo plazo. ...

Answer 3

Los dos algoritmos tienen un gran O definido para diferentes entradas (nodos y bordes). Entonces están convirtiendo uno para el otro para compararlos.

N es el número de nodos en el gráfico E es el número de bordes.

para un gráfico denso hay O (N^2) Bordes

para un gráfico escasa hay O (n) de los bordes.

constantes son por supuesto irrelavent para Big-O, por lo tanto la c cae

Answer 4

La idea es que en un gráfico denso, el número de aristas es O (N^2), mientras que en grafos dispersos, el número de los bordes es O (N). Entonces toman el O (E \ lg E) y lo expanden con esta aproximación de E para compararlo directamente con el tiempo de ejecución de Prim's O (N^2).

Básicamente, muestra que Kruskal es mejor para gráficos dispersos y Prim es mejor para gráficos densos.

Answer 5

Kruskal es sensible a la cantidad de aristas (E) en un gráfico, no a la cantidad de nodos. Prim sin embargo, solo se ve afectado por el número de nodos (N), que se evalúa en O(N^2).

Esto significa que en los gráficos densos donde el número de bordes se aproxima a N^2 (todos los nodos conectados) su factor de complejidad es O(E*log(E)) es aproximadamente equivalente a O(N^2*log(N)).

La c es una constante para tener en cuenta el "casi" y es irrelevante en la notación O. También log (N^2) es del mismo orden de magnitud que log (N) ya que el logaritmo supera la potencia de 2 por un margen sustancial (log(N^2) => 2*log(N) que en notación O es O(log(N))).

En un gráfico disperso E está más cerca de N que le da O(N*log(N)).

Answer 6

Primero: n es el número de vértices.

Prim es O (n^2) esa parte es bastante fácil.

Kruskal es O (Elog (E)) donde E es el número de aristas. en un gráfico denso, hay tantos como N eligen 2 aristas, que es aproximadamente n^2 (en realidad es n (n-1)/2, pero ¿quién está contando?) así que es aproximadamente n^2 log (n^2) que es 2n^2 log n que es O (n^2logn) que es mayor que O (n^2)

En un gráfico disperso, hay tan solo n bordes, por lo que tenemos n log n que es menor que O (n^2).