algorithm - planas - formula para convertir coordenadas utm a geograficas

Graficar Cálculo en grados desde Adjacency-list

Question

Me encontré con esta pregunta en la que se requería calcular en grados de cada nodo de un gráfico a partir de su representación de lista de adyacencia.

for each u
   for each Adj[i] where i!=u
     if (i,u) ∈ E
         in-degree[u]+=1

Ahora, según yo, su complejidad de tiempo debería ser O(|V||E|+|V|^2) pero la solución a la que me refería en cambio la describía como O(|V||E|) .

Por favor ayuda y dime cuál es correcto.

Answer 1

En lugar de O (| V || E |), la complejidad de la computación de los grados es O (| E |). Consideremos el siguiente pseudocódigo para calcular los grados de cada nodo:

for each u
  indegree[u] = 0;

for each u
  for each v /in Adj[u]
    indegree[v]++;

El primer ciclo tiene una complejidad lineal O (| V |). Para la segunda parte: para cada v, el ciclo interno se ejecuta como máximo | E | veces, mientras que el bucle más externo ejecuta | V | veces. Por lo tanto, la segunda parte parece tener complejidad O (| V || E |). De hecho, el código ejecuta una operación una vez para cada borde, por lo que una complejidad más precisa es O (| E |).