crivero1
commented
6 years ago Hola Rudyard,
Es posible demostrar que el tamaño de P es a los más |Q|, el número de estados. Inductivamente uno puede demostrar que después de cada iteración de update set, para cada q, existe a lo más un k tal que (q, k) en P. Básicamente, siempre que vas agregar un par (q,k), eliminas el anterior y lo agregas. ¿Se entiende?
Suerte!
Estaba calculando la complejidad del algorimto y quede trabado en una parte. La funcion principal evalLeftmostLongest claramente hace |w| iteraciones. En cada iteracion hace un llamado a updateSet. Luego la complejidad sera |w| por la complejidad de updateSet
Esta funcion tiene un for anidado dentro de otro for. El for interior es for each q∈\delta(p;ai);hay a lo mas |Q| iteraciones ya que en el peor caso desde el estado p podemos llegar a cualquier estado.
Lo que no me queda claro es cuantas iteraciones pueden haber en el for anterior; for each(p;k)∈P. Es decir cuando elementos hay en el peor de los casos en P.
Desde ya gracias.