Contento, pero precavido
Hasta donde puedo ver en este momento (pero tomando en cuenta que la nieve no me deja ver mucho), parece ser que por fin tengo el resultado de complejidad (desfortunadamente, expresado en forma negativa, es decir no existe un algoritmo que ...).
Ese resultado se me ha estado escapando de las manos las últimas semanas, principalmente porque yo creía (y esperaba) que sí era posible encontrar tal algoritmo, pero todos mis intentos por generar tal, obviamente, fracasaron. Aún así, tengo todavía algunas dudas sobre la veracidad de un paso que utilicé, y Franz tiene una duda sobre la equivalencia de unas definiciones en dos artículos distintos (usan los mismos términos, pero con definiciones distintas).
Si tengo este resultado, podré dormir tranquilo, después de tantas decepciones que he dado con resultados falsos en el último mes.
Supongo que sólo me queda esperar a mañana y aclarar mis dudas.
2 comentarios:
En términos muy básicos ¿Qué es la complejidad?
La complejidad es básicamente el mínimo esfuerzo que necesitas para resolver un problema. Este esfuerzo comúnmente se mide en tiempo, y en el tamaño del problema.
Por ejemplo para copiar una cadena de texto, necesitas básicamente tanto tiempo como larga es la cadena. Así, si solo es una letra, necesitas una unidad de tiempo, y si son 15 letras, necesitas 15 unidades de tiempo (el tiempo, como ves, es usado de forma muy abstracta).
En general, uno no busca la cantidad exacta que se necesita, sino clasificarlo dentro de el tipo de función que expresa ese tiempo. En el ejemplo de copiar el texto, necesitas tiempo polinomial porque hay un polinomio (en este caso, simplemente x) que expresa el tiempo que necesitas para resolver el problema.
La cosa se vuelve interesante cuando llegas a las clases exponenciales y más allá.
Espero que más o menos me haya dado a entender. En todo caso, espero mañana tener una entrada, más detallada, al respecto en SaasKun
Saludos.
Publicar un comentario