# data[].attributes.body
Observando el programa podemos ver que el tiempo de ejecución es de 1.171 segundos.
Y para solucionar el problema se hizo necesario usar  13 líneas de código

# data[].attributes.body
Observando el resultado del programa podemos ver que el tiempo de ejecución del código es de 0,6431 segundos.
y tan solo se usaron 5 líneas de código para resolver el problema

# data[].attributes.body
Como se puede observar en ambos códigos la eficiencia es muy diferente, tanto el longitud del  código como en el tiempo de ejecución del mismo.

Esta es lo que busca analizar al complejidad computacional, poder establecer la forma mucho mas rápida y fácil de resolver un problema.

# data[].attributes.body
Forma no recursiva : Para esta función no usamos recursividad, simplemente hacemos una suma de cada uno de los elementos del vector.

# data[].attributes.body
Haremos dos programas que tendrán las misma funcionalidad.

El programa busca contar los 10 elementos de un vector, haremos uno de forma recursiva y otro de forma "tradicional".

Forma Recursiva: Para esta función recursiva usamos un ciclo for hará la función de sumar los 10 elementos del vector

# data[].attributes.body
El siguiente experimento tiene como finalidad mostrar a grandes rasgos lo que busca el estudio de la complejidad computacional, comparando dos programas, uno de forma recursiva (mejor) y otro de forma no recursiva(peor).

Para esta prueba de escritorio usaremos un equipo con las siguientes características:

Marca: Portátil HP.
Procesador : Intel Core i5 8th generación 1.60 GHz hasta 1.80 GHz.
Memoria Ram: 8 Gb DDR4 a 2.400 MHz
Disco mecánico de 1 tb a 7200 Rpm

# data[].attributes.headline
Experimento de la complejidad computacional

# data[].attributes.subject
Experimento de la complejidad computacional

# data[].attributes.body
El principal objetivo de la complejidad computacional es buscar la forma en la que el codigo sea mas optimo, y consuma menos recursos para hacer la misma tarea, para hacer una prueba tenemos que tener unos parametros claros:

Las pruebas se deben hacer en el mismo equipo.

Se debe buscar la forma de hacerlo lo mas optimo posible

Un programa no es mejor por ser mas extenso, por el contrario, cuando el programa sea mas pequeño (que tenga menos lienas de codigo) sera mucho mas optimo y por consecuencia, el equipo tendra menos gasto de recursos (Memoria ram, procesador, etc...)

# data[].attributes.body
Un bucle o ciclo, en programación, es una secuencia de instrucciones de código que se ejecuta repetidas veces, hasta que la condición asignada a dicho bucle deja de cumplirse. Los tres bucles más utilizados en programación son el bucle while, el bucle for y el bucle do-while.

# data[].attributes.attachment_link.readable_text
Un bucle o ciclo, en programación, es una secuencia de instrucciones de código que se ejecuta repetidas veces, hasta que la condición asignada a dicho bucle deja de cumplirse. Los tres bucles más utilizados en programación son el bucle while, el bucle for y el bucle do-while.

Código sin utilizar bucles:

Ejemplo con un bucle for

Algunos lenguajes de programación tienen sentencias que permiten "escapar" de los bucles sin llegar a la condición de fin, como el romper o el devolver.

Ejemplos saliendo de un bucle en Visual Basic

Ejemplo saliendo de un bucle en Delphi:

Ejemplo de Bucle en Pseudocódigo:

Pide que el usuario introduzca 10 valores y luego imprime la suma de todos ellos.

Para x=1 Hasta 10 Con Paso 1
     Escribir "Escriba el valor de la posición ",x
     Leer n
     sum=sum+n
FinPara

Imprimir "La suma de la serie es: ",sum

# data[].attributes.attachment_link.description
Un bucle o ciclo, en programación, es una secuencia de instrucciones de código que se ejecuta repetidas veces, hasta que la condición asignada a dicho bucle deja de cumplirse. Los tres bucles más utilizados en programación son el bucle while, el bucle for y el bucle do-while.

# data[].attributes.body
Es un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades.

# data[].attributes.body
-¿Qué es un algoritmo?
-¿Qué es un ciclo o bucle?
-Que es la complejidad computacional?

# data[].attributes.body
Nos permite comparar cual algoritmo es mejor que otro dependiendo de diferentes parámetros que se tiene establecidos para verificar cual es mejor que otro.

# data[].attributes.body
El objetivo de la complejidad computacional es clasificar los problemas computacionales de acuerdo a su dificultad

# data[].attributes.body
La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se contraen la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clase de complejidad.

# data[].attributes.attachment_link.readable_text
Por favor, En este artículo se detectaron varios problemas. edítalo para mejorarlo:

Puedes avisar al redactor principal pegando lo siguiente en su página de discusión: {{sust:Aviso PA|Teoría de la complejidad computacional|copyedit|referencias adicionales}} ~~~~

La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.​

Un problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de computación matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, como tiempo y memoria.

Una de las metas de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no. Otros campos relacionados con la teoría de la complejidad computacional son el análisis de algoritmos y la teoría de la computabilidad. Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema.

La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.

Antes de que se realizaran investigaciones en torno a la complejidad de los algoritmos, se crearon los cimientos de esta teoría por varios investigadores. Uno de los aportes más influyentes fue la definición de las máquinas de Turing en 1936,​ las cuales resultaron ser una noción de computadora muy flexible y robusta. A medida que las computadoras se desarrollaban en los 40's y los 50's, la Máquina de Turing demostró ser el modelo teórico correcto de cómputo.

Sin embargo, rápidamente se descubrió que el modelo básico de la máquina de Turing fallaba al cuantificar el tiempo y la memoria requerida por una computadora, un problema crítico hoy en día, y aún más en aquellos tiempos. La idea de medir el tiempo y espacio como una función de la longitud de la entrada se originó a principios de los 60s por Hartmanis y Stearns, y así nació la teoría de la complejidad computacional.

En los inicios, los investigadores trataban de entender las nuevas medidas de complejidad, y cómo se relacionaban unas con otras. En 1965, Edmonds definió un "buen" algoritmo como uno con un tiempo de ejecución acotado por un polinomio, es decir, con un tiempo de ejecución polinómico.​ Esto condujo al surgimiento de uno de los conceptos más importantes de la teoría de la complejidad computacional: la NP-completitud y su pregunta fundamental, si P=NP.

El campo comenzó a florecer cuando el investigador estadounidense Stephen Cook y el soviético Leonid Levin, trabajando de manera independiente, probaron que existen problemas relevantes que son NP-completos. En 1972, Richard Karp llevó esta idea un paso más adelante, demostrando que 21 problemas combinatorios y de teoría de grafos, caracterizados por ser computacionalmente intratables, eran NP-completos.​ También en los 70's, se produjo un crecimiento de las clases de complejidad a medida que los investigadores trataban de comprender los distintos modelos de cómputo existentes.

En los 80's, se produjo un auge de los modelos finitos, que analizaban el proceso de cómputo de una manera inherentemente distinta. Surgió un nuevo acercamiento a problemas como P=NP, y aun cuando estos modelos tenían sus limitaciones separando las clases de complejidad, esta aproximación introdujo técnicas combinatorias que permitieron un mejor entendimiento de los límites de estos modelos.

Ya en los 90's, se estudiaron nuevos modelos de cómputo como las computadoras cuánticas, donde una misma tarea puede tener diferente complejidad en la computación clásica y en la computación cuántica. Sin embargo, existen varias limitantes, entre ellas, la de desarrollar un hardware para este modelo, y que se requieren grandes cantidades de espacio para realizar los cálculos.

Problemas, algoritmos y complejidad

Para poder referirnos a problemas como "inherentemente intratables" y problemas de dificultad "equivalente", es necesario comprender algunos términos más básicos.​

Un problema computacional constituye una pregunta a ser respondida, teniendo generalmente varios parámetros, o variables libres, cuyos valores no se han especificado. Un problema se describe mediante:

1. Una descripción general de todos sus parámetros (pueden ser de entrada o de salida).

2. Una sentencia que describa las propiedades que la respuesta, o la solución, debe cumplir.

Una instancia de un problema se obtiene cuando se especifican valores particulares para todos los parámetros del problema. Por ejemplo, consideremos el problema del test de primalidad. La instancia es un número (e.g. 15) y la solución es "sí" si el número es primo, y "no" en caso contrario. Visto de otra manera, la instancia es una entrada particular del problema, y la solución es la salida correspondiente para la entrada dada.

Un problema de decisión es un tipo especial de problema computacional cuya respuesta es solamente "sí" o "no" (o, de manera más formal, "1" o "0").

Un problema de decisión pudiera verse como un lenguaje formal, donde los elementos que pertenecen al lenguaje son las instancias del problema cuya respuesta es "sí", los que no pertenecen al lenguaje son aquellas instancias cuya respuesta es "no". El objetivo es decidir, con la ayuda de un algoritmo, si una determinada entrada es un elemento del lenguaje formal considerado. Si el algoritmo devuelve como respuesta "sí", se dice que el algoritmo acepta la entrada, de lo contrario se dice que la rechaza.

Los problemas de decisión constituyen uno de los principales objetos de estudio de la teoría de la complejidad computacional, pues la NP-completitud se aplica directamente a estos tipos de problemas en vez de a problemas de optimización. Estos problemas tienen gran importancia porque casi todo problema puede transformarse en un problema de decisión.

Podemos decir informalmente, que los algoritmos son procedimientos paso-a-paso para resolver problemas. Se puede pensar en ellos como simples programas de computadora, escritos en un lenguaje artificial específico.​

Se dice que un algoritmo resuelve un problema A, si dicho algoritmo se puede aplicar a cualquier instancia I de A, y se garantiza que siempre produce una solución para dicha instancia. De manera general, nos interesa encontrar el algoritmo más "eficiente" para resolver cierto problema. En su sentido más amplio, la noción de eficiencia involucra a todos los recursos computacionales necesarios para la ejecución de un algoritmo.

Por algoritmo "más eficiente" usualmente nos referimos al más rápido. Debido a que los requerimientos de tiempo son usualmente un factor dominante cuando se trata de determinar si un algoritmo es lo suficientemente eficiente para ser útil en la práctica, nos concentraremos en este recurso.

Los científicos de la computación realizan la distinción entre algoritmos de Tiempo polinómico y algoritmos de tiempo exponencial cuando se trata de caracterizar a los algoritmos como "suficientemente eficiente" y "muy ineficiente" respectivamente.

Un algoritmo de tiempo polinomial se define como aquel con función de complejidad temporal dentro de una cota superior asintótica (denominada a veces "orden") O( p( n)) para alguna función polinómica p, donde n denota el tamaño de la entrada. Los algoritmos de tiempo exponencial, son los que el número de ciclos que tienen que realizarse con el algoritmo es proporcional a la función de modo que el poder computacional necesario para correr el algoritmo crece de forma exponencial al tamaño del problema.

La mayoría de los algoritmos de tiempo exponencial son simples variaciones de una búsqueda exhaustiva, mientras que los algoritmos de tiempo polinomial, usualmente se obtienen mediante un análisis más profundo de la estructura del problema. En la teoría de la complejidad computacional, existe el consenso de que un problema no está "bien resuelto" hasta que se conozca un algoritmo de tiempo polinomial que lo resuelva. Por tanto, nos referiremos a un problema como intratable, si es tan difícil que no existe algoritmo de tiempo polinomial capaz de resolverlo.​

Una clase de complejidad es un conjunto de problemas que poseen la misma complejidad computacional.

Las clases de complejidad más sencillas se definen teniendo en cuenta factores como:

El tipo de problema computacional: Los problemas más comúnmente utilizados son los problemas de decisión, pero las clases de complejidad se pueden definir para otros tipos de problemas.

El modelo de cómputo: El modelo de cómputo más común es la Máquina de Turing determinista, pero muchas clases de complejidad se basan en Máquinas de Turing no deterministas, Máquinas de Turing cuánticas, etc.

El recurso (o recursos) que está(n) siendo acotado(s) y la(s) cota(s): Estas dos propiedades usualmente se utilizan juntas, por ejemplo, "tiempo polinomial", "espacio logarítmico", "profundidad constante", etc.

La clase P contiene a aquellos problemas que son solubles en tiempo polinómico por una máquina de Turing determinista.​

Para la definición anterior se ha fijado el modelo de cómputo: la Máquina de Turing determinista. Existen distintas variantes de la Máquina de Turing y es conocido que la más débil de ellas puede simular a la más fuerte, adicionando a lo sumo un tiempo polinómico. En las décadas posteriores a la Tesis de Church-Turing surgieron otros modelos de cómputo, y se pudo mostrar que la Máquina de Turing también podía simularlos a lo sumo adicionando también un tiempo polinómico. Por tanto, la clase análoga a P para dichos modelos no es mayor que la clase P para el modelo de cómputo de la máquina de Turing.

La clase P juega un papel importante en la teoría de la complejidad computacional debido a que:

1. P es invariante para todos los modelos de cómputo que son polinómica mente equivalentes a la Máquina de Turing determinista.

2. A grandes rasgos, P corresponde a la clase de problemas que, de manera realista, son solubles en una computadora.

Muchas veces podemos evitar utilizar la fuerza bruta en los problemas para obtener soluciones en tiempo polinómico. Sin embargo, para algunos problemas esto no ha podido lograrse, es decir, no se conocen algoritmos que los resuelvan en tiempo polinómico. Quizás estos problemas tengan algoritmos en tiempo polinomial que se basan en principios por ahora desconocidos, o quizás estos problemas no pueden ser resueltos en tiempo polinómico, debido a que son "inherentemente difíciles".

La clase de complejidad NP consta de los problemas "verificables" en tiempo polinómico. Por verificable se entiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que dicho certificado es correcto en un tiempo polinómico en el tamaño de la entrada. A los problemas en la clase NP usualmente se les llama problemas NP.​

El término NP proviene de no determinista en tiempo polinómico y se deriva de un caracterización alternativa de esta clase, donde se utilizan Máquinas de Turing no deterministas. Informalmente, se puede definir la clase NP en términos de un algoritmo no determinista (recordar la equivalencia entre algoritmo y Máquina de Turing).

El algoritmo mencionado está compuesto por 2 etapas separadas. Dada una instancia del problema I, la primera etapa simplemente "adivina" un candidato a solución S. Entonces, la etapa de verificación recibe como entrada a I y a S, y procede a realizar el cómputo de una manera determinista, finalmente deteniéndose con la respuesta "sí", o con la respuesta "no", o sigue computando sin detenerse.

Al igual que la clase P, la clase NP es insensible a la elección del modelo de cómputo no determinista, debido a que dichos modelos son equivalentes polinómicamente.

Muchas clases de complejidad importantes pueden ser definidas acotando el tiempo o el espacio utilizado por el algoritmo. Algunas de estas clases de problemas de decisión son:

Clase de complejidad

Modelo de cómputo

Restricción de recurso

La pregunta P=NP

La relación entre las clases P y NP es fundamental para la teoría de la NP-completitud. Intuitivamente, creemos que P es un subconjunto de NP. Y, efectivamente, cada problema de decisión resuelto por un algoritmo de tiempo polinomial determinista, también puede ser resuelto por un algoritmo de tiempo polinomial no determinista. Simplemente se necesita observar que cualquier algoritmo determinista puede ser utilizado en la etapa de verificación de un algoritmo no determinista. Si B es un problema de P, y A es un algoritmo de tiempo polinomial para B, entonces se puede construir un algoritmo de tiempo polinomial no determinista para B, simplemente utilizando A en la etapa de verificación e ignorando la etapa de adivinación. Por tanto, si B pertenece a P, entonces B también pertenece a NP.

La pregunta P=NP es una de las más importantes en el campo de las ciencias de la computación, debido a las grandes repercusiones que habría, en caso de encontrarse una solución. Si P=NP, cualquier problema polinómica mente verificable sería polinómica mente decidible. La mayoría de los investigadores cree que estas clases no son iguales, porque se ha realizado bastantes esfuerzos, sin éxito, para encontrar algoritmos de tiempo polinomial para varios problemas en NP. Los investigadores también han tratado de probar que las clases son distintas, pero eso conllevaría a mostrar que no existe un algoritmo "eficiente" para reemplazar a la búsqueda por fuerza bruta.

Una reducción es una transformación de un problema en otro problema. Intuitivamente, un problema Q puede ser reducido a otro problema Q', si cualquier instancia del problema Q puede ser "fácilmente" expresada como una instancia del problema Q', y cuya solución proporcione una solución para la instancia de Q.​

Existen muchos tipos de reducciones: basadas en el método de reducción, como las reducciones de Cook, las reducciones de Karp y las reducciones de Levin, y las basadas en la cota de la complejidad, como la reducción en tiempo polinomial o la reducción de espacio logarítmica. Una de las reducciones más utilizadas es la reducción en tiempo polinomial, lo cual significa que el proceso de reducción toma un tiempo polinomial.

Las reducciones en tiempo polinomial nos dotan de elementos para probar, de una manera formal, que un problema es al menos tan difícil que otro, con una diferencia de un factor polinomial. Estas son esenciales para definir a los problemas NP-completos, además de ayudar a comprender los mismos.

La clase de los problemas NP-completos contiene a los problemas más difíciles en NP, en el sentido de que son los que estén más lejos de estar en P. Debido a que el problema P=NP no ha sido resuelto, el hecho de reducir un problema B, a otro problema A, indicaría que no se conoce solución en tiempo polinomial para A. Esto es debido a que una solución en tiempo polinomial para A, tendría como consecuencia la existencia de una solución polinomial para B. De manera similar, debido a que todos los problemas NP pueden ser reducidos a este conjunto, encontrar un problema NP-completo que pueda ser resuelto en un tiempo polinomial significaría que P=NP.

Quizás la razón de mayor peso por la cual los científicos de la computación creen que P es distinto de NP, es la existencia de la clase de problemas "NP-completos". Esta clase tiene la curiosa propiedad de que si algún problema NP-completo puede ser resuelto en tiempo polinomial, entonces todo problema en NP tiene una solución en tiempo polinomial, es decir, P=NP. A pesar de años de estudio, ningún algoritmo de tiempo polinomial se ha descubierto para ningún problema NP-completo.

Desde el punto de vista teórico, un investigador intentando mostrar que la clase P es distinta de la clase NP, pudiera enfocarse en un problema NP-completo. Si algún problema en NP requiere más que un tiempo polinomial, entonces uno NP-completo también. Además, un investigador intentando demostrar que P=NP, solo necesita encontrar un algoritmo de tiempo polinomial para un problema NP-completo para lograrlo.

Desde el punto de vista práctico, el fenómeno de la NP-completitud puede prevenir la pérdida de tiempo cuando se busca un algoritmo de tiempo polinomial no existente para resolver un problema determinado. Aun cuando no se posean los elementos matemáticos para demostrar que cierto problema no se puede resolver en tiempo polinomial, creemos que P no es igual a NP, así que demostrar que el problema es NP-completo, es una fuerte evidencia de su no "polinomialdad".

Teniendo en cuenta la definición de problema intratable, si no se cumple que P=NP, entonces los problemas NP-completos son intratables.

Muchos problemas de la práctica son NP-completos, y son muy importantes como para desistir simplemente porque no sabemos cómo encontrar una solución óptima en tiempo polinomial. Aunque un problema sea NP-completo, puede haber esperanza. Existen tres estrategias fundamentales para lidiar con un problema NP-completo:

Si la entrada es pequeña, un algoritmo con tiempo de ejecución exponencial pudiera ser perfectamente aceptable.

Se pudieran aislar algunos casos especiales que se pudieran resolver en tiempo polinomial.

Podríamos utilizar aproximaciones para encontrar soluciones lo suficientemente cercanas al óptimo en tiempo polinomial. En la práctica, obtener soluciones cercanas al óptimo es bastante aceptable. A estos algoritmos se les denomina algoritmos de aproximación, y en muchos casos se apoyan en heurísticas y metaheurísticas.

Véase también

1. Dean, Walter (2016). "Computational Complexity Theory". The Stanford Encyclopedia of Philosophy (en inglés). Metaphysics Research Lab, Stanford University.

2. Senen Barro, Ameneiro (2002). "1". Fronteras de la computación (2 edición). Diaz de Santos. p. 11. .

3. Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture.

4. Richard M. Karp (1972), "Reducibility Among Combinatorial Problems", en R. E. Miller and J. W. Thatcher (editors), ed., Complexity of Computer Computations, New York: Plenum, pp. 85-103.

5. García Merayo, Félix (2015). "11.3". Matemática discreta (3 edición). Ediciones Paraninfo, S.A. p. 548. .

6. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press and McGraw-Hill, (page 1049).

# data[].attributes.attachment_link.description
Por favor, En este artículo se detectaron varios problemas.

# data[].attributes.headline
                         Complejidad computacional 

# data[].attributes.subject
                         Complejidad computacional 