Estoy empezando a aprender la complejidad del tiempo, y busqué en los ejemplos la complejidad del tiempo para algún tipo simple.Complejidad del tiempo del algoritmo del gráfico profundidad-primer
Quería saber cómo calculamos la complejidad del tiempo promedio para una búsqueda en profundidad en un gráfico con |V|=n y |E|=m, el nodo de inicio debe ser 'u' y el nodo final ser 'v'.
La complejidad del tiempo para DFS es O (n + m). Obtenemos esta complejidad considerando el hecho de que estamos visitando cada nodo solo una vez y en el caso de un árbol (sin ciclos) estamos cruzando todos los bordes una vez.
Por ejemplo, si el nodo de inicio es u, y el nodo final es v, estamos pensando en el peor de los casos cuando v será el último nodo visitado. Así que estamos empezando a visitar el primer componente conectado del vecino, luego el componente conectado del segundo vecino, y así sucesivamente hasta el componente conectado del último vecino, donde encontramos v. Hemos visitado cada nodo solo una vez, y no lo hicimos cruzó el mismo borde más de una vez.
respetado señor, Soy nuevo en el análisis de la complejidad, en realidad estoy haciendo un proyecto sobre el sistema operativo, estoy tratando de encontrar los ciclos en el gráfico de asignación de recursos ... soy Encontrar ciclos usando una modificación de la profundidad de la primera búsqueda. Estoy tratando de comparar la complejidad de este algoritmo con el algoritmo bancario. ¿Puedes dar una derivación matemática del "rendimiento del caso avergae"? – Learner
"Rendimiento promedio de casos" es el valor esperado (es decir un término de la teoría de la probabilidad) del tiempo de ejecución sobre alguna distribución de probabilidad supuesta de entradas. –
será O (n + m) si el gráfico se da en forma de lista de adyacencia pero si el gráfico está en la forma de matriz de adyacencia a continuación, la complejidad es O (n * n), como hemos tiene que atravesar toda la fila hasta que encontremos un borde.
Sé que esto es demasiado tarde. Pero para otros que puedan venir a buscar, aquí hay un análisis detallado. http://techieme.in/depth-first-traversal – dharam