¿Qué es la compleijidad de los Algoritmos computacionales?
Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo se comportarán cuando las implementemos, especialmente al atacar problemas "grandes".
La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. En muchos cursos y libros se elude el tema porque a menudo se considera farragoso.
Pero eso no es necesariamente cierto. La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todos tenemos y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es un concepto difícil de entender.
Por hacer una similitud acerca de lo complicado que es este concepto, la dificultad de la complejidad es -salvando las distancias- como la de la predicción meteorológica: todos intuimos lo complicado que es hacer una predicción meteorológica... miles de datos, fórmulas, modelos y cálculos... sin embargo, cuando un meteorólogo nos explica con algo de gracia la predicción del tiempo, la podemos entender bastante bien. Ya estamos muy acostumbrados a cosas como borrasca, anticiclón, marejadilla, cota de nieve... Lo mismo pasa en cierto modo con la complejidad: enfrentarnos a un algoritmo para hacer un estudio de su complejidad requiere de un gran esfuerzo. Sin embargo, cuando alguien estudia un algoritmo y nos habla de su complejidad, entender el concepto no es tan complicado.
Entender la complejidad es importante porque a la hora de resolver muchos problemas, utilizamos algoritmos ya diseñados. Saber valorar su valor de complejidad puede ayudarnos mucho a conocer cómo se va a comportar el algoritmo e incluso a escoger uno u otro.
Así que en este artículo, nos vamos a dedicar a intentar exponer qué es la complejidad de un algoritmo desde un punto de vista sencillo y sin pretensiones, intentado distinguir qué impacto tiene el que un algoritmo tenga una u otra complejidad. Y, como de costumbre, adoptamos grandes simplificaciones, con el único ánimo de obtener una visión general de los conceptos. En cuanto a cómo obtener la complejidad de un algoritmo... no nos vamos a meter mucho: los formalismos necesarios quedan totalmente fuera del alcance de éste breve artículo divulgativo. No obstante, si estás interesad@, al final te proponemos algunos artículos y libros sobre el tema.
Primeramente, debemos tener claro qué es un algoritmo. Podemos entender por algoritmo una secuencia de intrucciones cuyo objetivo es la resolución de un problema. El término clave aquí es el de problema.
Existen multitud de problemas de computación que se pueden resolver mediante un algoritmo (aunque algunos pocos no tienen un algoritmo que los solucione :-o )
Bueno... pues para resolver cada problema, podemos obtener más de un algoritmo (
propio, por supuesto) que lo solucione... pero... ¿Cuál de ellos es el mejor? Sería conveniente poder aplicar algún tipo de "puntuación" a los algoritmos, y que cuanta más puntuación sacara un algoritmo, pues supondremos que es mejor. Eso es, en cierto modo, la complejidad.
Saber si un algoritmo es mejor que otro puede estudiarse desde dos puntos de vista: un algoritmo es mejor cuanto menos tarde en resolver un problema, o bien es tanto mejor cuanta menos memoria necesite.
A la idea del tiempo que consume un algoritmo para resolver un problema le llamamos complejidad temporal y a la idea de la memoria que necesita el algoritmo le llamamos complejidad espacial.
La complejidad espacial, en general, tiene mucho menos interés. El tiempo es un recurso mucho más valioso que el espacio. (Esto lo podemos ver también en el mundo real: si tienes dinero puedes comprarte una casa más grande, pero no puedes comprarte unos cuantos años más de vida).
Así que cuando hablamos de complejidad a secas, nos estamos refiriendo prácticamente siempre a complejidad temporal.
Bueno... pues ya hemos presentado de manera intuitiva esto de la complejidad: la complejidad de un algoritmo es un "valor", por así decirlo, que nos da una idea de cuánto va a tardar un algoritmo en resolver el problema para el que fue diseñado.
Los diferentes tipos de complejidad:
Sean f y g dos funciones definidas sobre el conjunto de números naturales, f; g : N ! N.
Definición: El orden de crecimiento de g es menor o igual que el de f, lo cual se denota por
g = O(f), si existe una constante k > 0 tal que g(n) _ kf(n), para todo n 2 N (excepto a
lo sumo un numero _nito de valores).
Ejemplo: si g(n) = 2n2 + 3n 5 entonces g = O(n2).
Jerarquía de _ordenes (en orden creciente):
O(1); O(log n); O(n); O(n log n); O(n2); O(n3); O(2n); O(n!); O(nn):
Comparación de tiempos de ejecución (1 segundo por operación elemental):
Un algoritmo de complejidad f es más eficiente que un algoritmo de complejidad g si
f = O(g) y g 6= O(f).
Un algoritmo es eficiente si su complejidad es poli nómica, es decir, O(nk), donde k 2 N.
La complejidad de un problema computacional es la menor de las complejidades de los
Algoritmos que lo resuelven. (Generalmente solo se conocen cotas de la complejidad).
Un problema decisional se clásica como:
Problema de la clase P, si se ha encontrado un algoritmo eficiente (de coste polinomico)
que lo resuelve.
Problema de la clase NP (Nondeterministic Polynomial) si:
En el supósito de tener una prueba o `certificado' de su solución esta puede verificarse en
tiempo polinomico.
La búsqueda de dicha prueba puede que requiera un tiempo exponencial.
P NP pero no se sabe si P = NP (se conjetura que no).
Un problema pi admite una reducción polinomica a un problema _, lo cual se denota por
´ , si toda instancia de _0 puede convertirse en tiempo polinomico en una instancia del
problema.
Un problema decisionales de la clase NP-completo si:
El problema es de la clase NP;
Para todo problema pi de la clase NP se cumple que ´ .
Si se hallase un algoritmo eficiente para resolver un problema de la clase NP-completo
entonces P = NP (se `sospecha' que tal algoritmo no existe).
¿Cómo se mide la complejidad de un algortimo?
En vez de calcular el tiempo exacto que va a tardar nuestro algoritmo… se calcula la cantidad de operaciones en función del tamaño (n).
Por lo general para estimar el tiempo de ejecución, esta función de crecimiento se multiplica por una constante c que representa una estimación del tiempo que la computadora se tarda en realizar una operación.
Como se mide?
En estos tiempos podemos asumir que una PC de escritorio puede realizar aproximadamente 10 a la 9operaciones por segundo. Sin embargo, este indicador no es absoluto dado que unas operaciones son más lentas que otras.
Ahora que nuestro archivo .class ha sido creado con el Applet correspondiente es el momento de crear nuestro archivo en HTML. Primeramente nos dirigiremos hasta la carpeta donde está ubicado nuestro archivo .class para facilitarnos la ruta para enlazar los dos archivos en este caso es:
