Breve historia
El pionero de los actuales microprocesadores: el 4004 de Intel.
Motorola 6800.
Zilog Z80 A.
Intel 80286, más conocido como 286.
Intel 80486, conocido también como 486SX de 33Mhz.
IBM PowerPC 601.
Parte posterior de un Pentium Pro. Este chip en particular es de 200 MHz, con 256 KiB de cache L2.
AMD K6 original.
Intel Pentium II; se puede observar su estilo de zócalo diferente.
Intel Celeron "Coppermine 128" de 600 MHz.
Intel Pentium III.
Hasta los primeros años de la década de 1970 los diferentes componentes electrónicos que formaban un procesador no podían ser un único circuito integrado, era necesario utilizar dos o tres "chips" para hacer una CPU (un era el "ALU" - Arithmetical Logic Unido, el otro la " control Unido", el otro el " Register Bank", etc ..). El 1971 la compañía Intel consiguió por primera vez de poner todos los transistores que constituían un procesador sobre un único circuito integrado, el"4004 "', nacía el microprocesador. Seguidamente se expone una lista ordenada cronológicamente de los microprocesadores más populares que fueron surgiendo.
El 4004 fue el primer microprocesador del mundo, creado en un simple chip, y desarrollado por Intel. Era un CPU de 4 bits y también fue el primero disponible comercialmente. Este desarrollo impulsó la calculadora de Busicom[1] y dio camino a la manera para dotar de «inteligencia» a objetos inanimados, así como la computadora personal. Codificado inicialmente como 1201, fue pedido a Intel por Computer Terminal Corporation para usarlo en su terminal programable Datapoint 2200, pero debido a que Intel terminó el proyecto tarde y a que no cumplía con la expectativas de Computer Terminal Corporation, finalmente no fue usado en el Datapoint. Posteriormente Computer Terminal Corporation e Intel acordaron que el i8008 pudiera ser vendido a otros clientes.
El SC/MP desarrollado por National Semiconductor, fue uno de los primeros microprocesadores, y estuvo disponible desde principio de 1974. El nombre SC/MP (popularmente conocido como «Scamp») es el acrónimo de Simple Cost-effective Micro Processor (Microprocesador simple y rentable). Presenta un bus de direcciones de 16 bits y un bus de datos de 8 bits. Una característica, avanzada para su tiempo, es la capacidad de liberar los buses a fin de que puedan ser compartidos por varios procesadores. Este microprocesador fue muy utilizado, por su bajo costo, y provisto en kits, para propósitos educativos, de investigación y para el desarrollo de controladores industriales diversos. EL 8080 se convirtió en la CPU de la primera computadora personal, la Altair 8800 de MITS, según se alega, nombrada en base a un destino de la Nave Espacial «Starship» del programa de televisión Viaje a las Estrellas, y el IMSAI 8080, formando la base para las máquinas que ejecutaban el sistema operativo CP/M-80. Los fanáticos de las computadoras podían comprar un equipo Altair por un precio (en aquel momento) de u$s395. En un periodo de pocos meses, se vendieron decenas de miles de estas PC. Se fabrica, por parte de Motorola, el Motorola MC6800, más conocido como 6800. Fue lanzado al mercado poco después del Intel 8080. Su nombre proviene de que contenía aproximadamente 6800 transistores. Varios de los primeras microcomputadoras de los años 1970 usaron el 6800 como procesador. Entre ellas se encuentran la SWTPC 6800, que fue la primera en usarlo, y la muy conocida Altair 680. Este microprocesador se utilizó profusamente como parte de un kit para el desarrollo de sistemas controladores en la industria. Partiendo del 6800 se crearon varios procesadores derivados, siendo uno de los más potentes el Motorola 6809 La compañía Zilog Inc. crea el Zilog Z80. Es un microprocesador de 8 bits construido en tecnología NMOS, y fue basado en el Intel 8080. Básicamente es una ampliación de éste, con lo que admite todas sus instrucciones. Un año después sale al mercado el primer computador que hace uso del Z80, el Tandy TRS-80 Model 1 provisto de un Z80 a 1,77 MHz y 4 KB de RAM. Es uno de los procesadores de más éxito del mercado, del cual se han producido numerosas versiones clónicas, y sigue siendo usado de forma extensiva en la actualidad en multitud de sistemas embebidos. La compañía Zilog fue fundada 1974 por Federico Faggin, quien fue diseñador jefe del microprocesador Intel 4004 y posteriormente del Intel 8080. Una venta realizada por Intel a la nueva división de computadoras personales de IBM, hizo que las PC de IBM dieran un gran golpe comercial con el nuevo producto con el 8088, el llamado IBM PC. El éxito del 8088 propulsó a Intel a la lista de las 500 mejores compañías, en la prestigiosa revista Fortune, y la misma nombró la empresa como uno de Los triunfos comerciales de los sesenta. El 80286, popularmente conocido como 286, fue el primer procesador de Intel que podría ejecutar todo el software escrito para su predecesor. Esta compatibilidad del software sigue siendo un sello de la familia de microprocesadores de Intel. Luego de 6 años de su introducción, había un estimado de 15 millones de PC basadas en el 286, instaladas alrededor del mundo.
Este procesador Intel, popularmente llamado 386, se integró con 275000 transistores, más de 100 veces tantos como en el original 4004. El 386 añadió una arquitectura de 32 bits, con capacidad para multitarea y una unidad de traslación de páginas, lo que hizo mucho más sencillo implementar sistemas operativos que usaran memoria virtual. · 1985: El VAX 78032
El microprocesador VAX 78032 (también conocido como DC333), es de único chip y de 32 bits, y fue desarrollado y fabricado por Digital Equipment Corporation (DEC); instalado en los equipos MicroVAX II, en conjunto con su ship coprocesador de coma flotante separado, el 78132, tenían una potencia cercana al 90% de la que podía entregar el minicomputador VAX 11/780 que fuera presentado en 1977. Este microprocesador contenía 125000 transistores, fue fabricado en tecnologóa ZMOS de DEC. Los sistemas VAX y los basados en este procesador fueron los preferidos por la comunidad científica y de ingeniería durante la década del 1980. La generación 486 realmente significó contar con una computadora personal de prestaciones avanzadas, entre ellas,un conjunto de instrucciones optimizado, una unidad de coma flotante o FPU, una unidad de interfaz de bus mejorada y una memoria caché unificada, todo ello integrado en el propio chip del microprocesador. Estas mejoras hicieron que los i486 fueran el doble de rápidos que el par i386 - i387 operando a la misma frecuencia de reloj. El procesador Intel 486 fue el primero en ofrecer un coprocesador matemático o FPU integrado; con él que se aceleraron notablemente las operaciones de cálculo. Usando una unidad FPU las operaciones matemáticas más complejas son realizadas por el coprocesador de manera prácticamente independiente a la función del procesador principal. Procesadores fabricados por AMD 100% compatible con los códigos de Intel de ese momento, llamados «clones» de Intel, llegaron incluso a superar la frecuencia de reloj de los procesadores de Intel y a precios significativamente menores. Aquí se incluyen las series Am286, Am386, Am486 y Am586. Es un procesador de tecnología RISC de 32 bits, en 50 y 66MHz. En su diseño utilizaron la interfaz de bus del Motorola 88110. En 1991, IBM busca una alianza con Apple y Motorola para impulsar la creación de este microprocesador, surge la alianza AIM (Apple, IBM y Motorola) cuyo objetivo fue quitar el dominio que Microsoft e Intel tenían en sistemas basados en los 80386 y 80486. PowerPC (abreviada PPC o MPC) es el nombre original de la familia de procesadores de arquitectura de tipo RISC, que fue desarrollada por la alinza AIM. Los procesadores de esta familia son utilizados principalmente en computadores Macintosh de Apple Computer y su alto rendimiento se debe fuertemente a su arquitectura tipo RISC. El microprocesador de Pentium poseía una arquitectura capaz de ejecutar dos operaciones a la vez, gracias a sus dos pipeline de datos de 32bits cada uno, uno equivalente al 486DX(u) y el otro equivalente a 486SX(u). Además, estaba dotado de un bus de datos de 64 bits, y permitía un acceso a memoria de 64 bits (aunque el procesador seguía manteniendo compatibilidad de 32 bits para las operaciones internas, y los registros también eran de 32 bits). Las versiones que incluían instrucciones MMX no sólo brindaban al usuario un más eficiente manejo de aplicaciones multimedia, como por ejemplo, la lectura de películas en DVD, sino que también se ofrecían en velocidades de hasta 233 MHz. Se incluyó una versión de 200 MHz y la más básica trabajaba a alrededor de 166 MHz de frecuencia de reloj. El nombre Pentium, se mencionó en las historietas y en charlas de la televisión a diario, en realidad se volvió una palabra muy popular poco después de su introducción.
· 1994: EL PowerPC 620
En este año IBM y Motorola desarrollan el primer prototipo del procesador PowerPC de 64 bit[2], la implementación más avanzada de la arquitectura PowerPC, que estuvo disponible al año próximo. El 620 fue diseñado para su utilización en servidores, y especialmente optimizado para usarlo en configuraciones de cuatro y hasta ocho procesadores en servidores de aplicaciones de base de datos y vídeo. Este procesador incorpora siete millones de transistores y corre a 133 MHz. Es ofrecido como un puente de migración para aquellos usuarios que quieren utilizar aplicaciones de 64 bits, sin tener que renunciar a ejecutar aplicaciones de 32 bits. Lanzado al mercado para el otoño de 1995, el procesador Pentium Pro (profesional) se diseñó con una arquitectura de 32 bits. Se usó en servidores y los programas y aplicaciones para estaciones de trabajo (de redes) impulsaron rápidamente su integración en las computadoras. El rendimiento del código de 32 bits era excelente, pero el Pentium Pro a menudo era más lento que un Pentium cuando ejecutaba código o sistemas operativos de 16 bits. El procesador Pentium Pro estaba compuesto por alrededor de 5,5 millones de transistores. Habiendo abandonado los clones, AMD fabricada con tecnologías análogas a Intel. AMD sacó al mercado su primer procesador propio, el K5, rival del Pentium. La arquitectura RISC86 del AMD K5 era más semejante a la arquitectura del Intel Pentium Pro que a la del Pentium. El K5 es internamente un procesador RISC con una Unidad x86- decodificadora, transforma todos los comandos x86 (de la aplicación en curso) en comandos RISC. Este principio se usa hasta hoy en todas las CPU x86. En la mayoría de los aspectos era superior el K5 al Pentium, incluso de inferior precio, sin embargo AMD tenía poca experiencia en el desarrollo de microprocesadores y los diferentes hitos de producción marcados se fueron superando con poco éxito, se retrasó 1 año de su salida al mercado, a razón de ello sus frecuencias de trabajo eran inferiores a las de la competencia, y por tanto, los fabricantes de PC dieron por sentado que era inferior. Con el K6, AMD no sólo consiguió hacerle seriamente la competencia a los Pentium MMX de Intel, sino que además amargó lo que de otra forma hubiese sido un plácido dominio del mercado, ofreciendo un procesador casi a la altura del Pentium II pero por un precio muy inferior. En cálculos en coma flotante, el K6 también quedó por debajo del Pentium II, pero por encima del Pentium MMX y del Pro. El K6 contó con una gama que va desde los 166 hasta los más de 500 Mhz y con el juego de instrucciones MMX, que ya se han convertido en estándares. Más adelante se lanzó una mejora de los K6, los K6-2 de 250 nanómetros, para seguir compitiendo con los Pentium II, siendo éste último superior en tareas de coma flotante, pero inferior en tareas de uso general. Se introduce un juego de instrucciones SIMD denominado 3DNow! Un procesador de 7,5 millones de transistores, se busca entre los cambios fundamentales con respecto a su predecesor, mejorar el rendimiento en la ejecución de código de 16 bits, añadir el conjunto de instrucciones MMX y eliminar la memoria caché de segundo nivel del núcleo del procesador, colocándola en una tarjeta de circuito impreso junto a éste. Gracias al nuevo diseño de este procesador, los usuarios de PC pueden capturar, revisar y compartir fotografías digitales con amigos y familia vía Internet; revisar y agregar texto, música y otros; con una línea telefónica; el enviar vídeo a través de las líneas normales del teléfono mediante Internet se convierte en algo cotidiano. Los procesadores Pentium II Xeon se diseñan para cumplir con los requisitos de desempeño en computadoras de medio-rango, servidores más potentes y estaciones de trabajo (workstations). Consistente con la estrategia de Intel para diseñar productos de procesadores con el objetivo de llenar segmentos de los mercados específicos, el procesador Pentium II Xeon ofrece innovaciones técnicas diseñadas para las estaciones de trabajo y servidores que utilizan aplicaciones comerciales exigentes, como servicios de Internet, almacenamiento de datos corporativos, creaciones digitales y otros. Pueden configurarse sistemas basados en este procesador para integrar de cuatro o ocho procesadores trabajando en paralelo, también más allá de esa cantidad. Continuando la estrategia, Intel, en el desarrollo de procesadores para los segmentos del mercado específicos, el procesador Celeron es el nombre que lleva la línea de de bajo costo de Intel. El objetivo fue poder, mediante ésta segunda marca, penetrar en los mercados impedidos a los Pentium, de mayor rendimiento y precio. Se diseña para el añadir valor al segmento del mercado de los PC. Proporcionó a los consumidores una gran actuación a un bajo coste, y entregó un desempeño destacado para usos como juegos y el software educativo.
Procesador totalmente compatible con la arquitectura x86. Internamente el Athlon es un rediseño de su antecesor, pero se le mejoró substancialmente el sistema de coma flotante (ahora con 3 unidades de coma flotante que pueden trabajar simultáneamente) y se le incrementó la memoria caché de primer nivel (L1) a 128 KiB (64 KiB para datos y 64 KiB para instrucciones). Además incluye 512 KiB de caché de segundo nivel (L2). El resultado fue el procesador x86 más potente del momento. El procesador Athlon con núcleo Thunderbird apareció como la evolución del Athlon Classic. Al igual que su predecesor, también se basa en la arquitectura x86 y usa el bus EV6. El proceso de fabricación usado para todos estos microprocesadores es de 180 nanómetros. El Athlon Thunderbird consolidó a AMD como la segunda mayor compañía de fabricación de microprocesadores, ya que gracias a su excelente rendimiento (superando siempre al Pentium III y a los primeros Pentium IV de Intel a la misma frecuencia de reloj) y bajo precio, la hicieron muy popular tanto entre los entendidos como en los iniciados en la informática. El procesador Pentium III ofrece 70 nuevas instrucciones Internet Streaming, las extensiones de SIMD que refuerzan dramáticamente el desempeño con imágenes avanzadas, 3D, añadiendo una mejor calidad de audio, video y desempeño en aplicaciones de reconocimiento de voz. Fue diseñado para reforzar el área del desempeño en el Internet, le permite a los usuarios hacer cosas, tales como, navegar a través de páginas pesadas (con muchos gráficos), tiendas virtuales y transmitir archivos video de alta calidad. El procesador se integra con 9,5 millones de transistores, y se introdujo usando en él tecnología 250 nanómetros. El procesador Pentium III Xeon amplia las fortalezas de Intel en cuanto a las estaciones de trabajo (workstation) y segmentos de mercado de servidores, y añade una actuación mejorada en las aplicaciones del comercio electrónico e informática comercial avanzada. Los procesadores incorporan mejoras que refuerzan el procesamiento multimedia, particularmente las aplicaciones de vídeo. La tecnología del procesador III Xeon acelera la transmisión de información a través del bus del sistema al procesador, mejorando el desempeño significativamente. Se diseña pensando principalmente en los sistemas con configuraciones de multiprocesador. Este es un microprocesador de séptima generación basado en la arquitectura x86 y fabricado por Intel. Es el primero con un diseño completamente nuevo desde el Pentium Pro. Se estrenó la arquitectura NetBurst, la cual no daba mejoras considerables respecto a la anterior P6. Intel sacrificó el rendimiento de cada ciclo para obtener a cambio mayor cantidad de ciclos por segundo y una mejora en las instrucciones SSE. Cuando Intel sacó el Pentium 4 a 1,7 GHz en abril de 2001 se vio que el Athlon Thunderbird no estaba a su nivel. Además no era práctico para el overclocking, entonces para seguir estando a la cabeza en cuanto a rendimiento de los procesadores x86, AMD tuvo que diseñar un nuevo núcleo, y sacó el Athlon XP. Este compatibilizaba las instrucciones SSE y las 3DNow! Entre las mejoras respecto al Thunderbird se puede mencionar la prerrecuperación de datos por hardware, conocida en inglés como prefetch, y el aumento de las entradas TLB, de 24 a 32. · 2004: El Intel Pentium 4 (Prescott)
A principios de febrero de 2004, Intel introdujo una nueva versión de Pentium 4 denominada 'Prescott'. Primero se utilizó en su manufactura un proceso de fabricación de 90 nm y luego se cambió a 65nm. Su diferencia con los anteriores es que éstos poseen 1 MiB o 2 MiB de caché L2 y 16 KiB de caché L1 (el doble que los Northwood), prevención de ejecución, SpeedStep, C1E State, un HyperThreading mejorado, instrucciones SSE3, manejo de instrucciones AMD64, de 64 bits creadas por AMD, pero denominadas EM64T por Intel, sin embargo por graves problemas de temperatura y consumo, resultaron un fracaso frente a los Athlon 64. · 2004: El AMD Athlon 64
El AMD Athlon 64 es un microprocesador x86 de octava generación que implementa el conjunto de instrucciones AMD64, que fueron introducidas con el procesador Opteron. El Athlon 64 presenta un controlador de memoria en el propio circuito integrado del microprocesador y otras mejoras de arquitectura que le dan un mejor rendimiento que los anteriores Athlon y que el Athlon XP funcionando a la misma velocidad, incluso ejecutando código heredado de 32 bits.El Athlon 64 también presenta una tecnología de reducción de la velocidad del procesador llamada Cool'n'Quiet,: cuando el usuario está ejecutando aplicaciones que requieren poco uso del procesador, baja la velocidad del mismo y su tensión se reduce. Intel lanzó ésta gama de procesadores de doble núcleo y CPUs 2x2 MCM (módulo Multi-Chip) de cuatro núcleos con el conjunto de instrucciones x86-64, basado en el la nueva arquitectura Core de Intel. La microarquitectura Core regresó a velocidades de CPU bajas y mejoró el uso del procesador de ambos ciclos de velocidad y energía comparados con anteriores NetBurst de los CPU Pentium 4/D2. La microarquitectura Core provee etapas de decodificación, unidades de ejecución, caché y buses más eficientes, reduciendo el consumo de energía de CPU Core 2, mientras se incrementa la capacidad de procesamiento. Los CPU de Intel han variado muy bruscamente en consumo de energía de acuerdo a velocidad de procesador, arquitectura y procesos de semiconductor, mostrado en las tablas de disipación de energía del CPU. Esta gama de procesadores fueron fabricados de 65 a 45 nanómetros. Phenom fue el nombre dado por Advanced Micro Devices (AMD) a la primera generación de procesadores de tres y cuatro núcleos basados en la microarquitectura K10. Como característica común todos los Phenom tienen tecnología de 65 nanómetros lograda a través de tecnología de fabricación Silicon on insulator (SOI). No obstante, Intel, ya se encontraba fabricando mediante la más avanzada tecnología de proceso de 45 nm en 2008. Los procesadores Phenom están diseñados para facilitar el uso inteligente de energía y recursos del sistema, listos para la virtualización, generando un óptimo rendimiento por vatio. Todas las CPU Phenom poseen características tales como controlador de memoria DDR2 integrado, tecnología HyperTransport y unidades de coma flotante de 128 bits, para incrementar la velocidad y el rendimiento de los cálculos de coma flotante. La arquitectura Direct Connect asegura que los cuatro núcleos tengan un óptimo acceso al controlador integrado de memoria, logrando un ancho de banda de 16 Gb/s para intercomunicación de los núcleos del microprocesador y la tecnología HyperTransport, de manera que las escalas de rendimiento mejoren con el número de núcleos. Tiene caché L3 compartida para un acceso más rápido a los datos (y así no depende tanto del tiempo de latencia de la RAM), además de compatibilidad de infraestructura de los zócalos AM2, AM2+ y AM3 para permitir un camino de actualización sin sobresaltos. A pesar de todo, no llegaron a igualar el rendimiento de la serie Core 2 Duo. Intel Core i7 es una familia de procesadores de cuatro núcleos de la arquitectura Intel x86-64. Los Core i7 son los primeros procesadores que usan la microarquitectura Nehalem de Intel y es el sucesor de la familia Intel Core 2. FSB es reemplazado por la interfaz QuickPath en i7 e i5 (zócalo 1366), y sustituido a su vez en i7, i5 e i3 (zócalo 1156) por el DMI eliminado el northBrige e implementando puertos PCI Express directamente. Memoria de tres canales (ancho de datos de 192 bits): cada canal puede soportar una o dos memorias DIMM DDR3. Las placa base compatibles con Core i7 tienen cuatro (3+1) o seis ranuras DIMM en lugar de dos o cuatro, y las DIMMs deben ser instaladas en grupos de tres, no dos. El Hyperthreading fue reimplementado creando núcleos lógicos. Está fabricado a arquitecturas de 45 nm y 32 nm y posee 731 millones de transistores su versión más potente. Se volvió a usar frecuencias altas, aunque a contrapartida los consumos se dispararon. Phenom II es el nombre dado por AMD a una familia de microprocesadores o CPUs multinúcleo (multicore) fabricados en 45 nm, la cual sucede al Phenom original y dieron soporte a DDR3. Una de las ventajas del paso de los 65 nm a los 45 nm, es que permitió aumentar la cantidad de cache L3. De hecho, ésta se incrementó de una manera generosa, pasando de los 2 MiB del Phenom original a 6 MiB.
Entre ellos, el Amd Phenom II X2 BE 555 de doble núcleo surge como el procesador binúcleo del mercado. También se lanzan tres Athlon II con sólo Cache L2, pero con buena relación precio/rendimiento. El Amd Athlon II X4 630 corre a 2,8 GHz. El Amd Athlon II X4 635 continua la misma línea.
AMD también lanza un triple núcleo, llamado Athlon II X3 440, así como un doble núcleo Athlon II X2 255. También sale el Phenom X4 995, de cuatro núcleos, que corre a más de 3,2GHz. También AMD lanza la familia Thurban con 6 núcleos físicos dentro del encapsulado
Llegan para remplazar los chips Nehalem, con Intel Core i3, Intel Core i5 e Intel Core i7 serie 2000 y Pentium G.
Intel lanzó sus procesadores que se conocen con el nombre en clave Sandy Bridge. Estos procesadores Intel Core que no tienen sustanciales cambios en arquitectura respecto a nehalem, pero si los necesarios para hacerlos más eficientes y rápidos que los modelos anteriores. Es la segunda generación de los Intel Core con nuevas instrucciones de 256 bits, duplicando el rendimiento, mejorando el desempeño en 3D y todo lo que se relacione con operación en multimedia. Llegaron la primera semana de Enero del 2011. Incluye nuevo conjunto de instrucciones denominado AVX y una GPU integrada de hasta 12 unidades de ejecución
Ivy Bridge es la mejora de sandy bridge a 22 nm. Se estima su llegada para 2012 y promete una mejora de la GPU, así como procesadores de sexdécuple núcleo en gamas más altas y cuádruple núcleo en las más bajas, abandonándose los procesadores de núcleo doble.
AMD Fusion es el nombre clave para un diseño futuro de microprocesadores Turion, producto de la fusión entre AMD y ATI, combinando con la ejecución general del procesador, el proceso de la geometría 3D y otras funciones de GPUs actuales. La GPU (procesador gráfico) estará integrada en el propio microprocesador. Se espera la salida progresiva de esta tecnología a lo largo del 2011; estando disponibles los primeros modelos (Ontaro y Zacate) para ordenadores de bajo consumo entre últimos meses de 2010 y primeros de 2011, dejando el legado de las gamas medias y altas (Llano, Brazos y Bulldozer para mediados o finales del 2011) problemática que se puede resolver a través del uso racional de los microcomputadores.
La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la compatibilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello. Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.
Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinomio, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P. Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio pero que podrían ser procesados por una máquina no-determinista, están agrupados en la clase NP. Estos problemas no tienen una solución práctica, es decir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.
Ejemplos
· Extraer cualquier elemento de un vector. La indexación en un vector o array lleva el mismo tiempo sea cual fuere el índice que se quiera buscar, por tanto es una operación de complejidad constante O(1). · Buscar en un diccionario tiene complejidad logarítmica. Se puede iniciar la búsqueda de una palabra por la mitad del diccionario. Inmediatamente se sabe si se ha encontrado la palabra o, en el caso contrario, en cuál de las dos mitades hay que repetir el proceso (es un proceso recursivo) hasta llegar al resultado. En cada (sub)búsqueda el problema (las páginas en las que la palabra puede estar) se ha reducido a la mitad, lo que se corresponde con la función logarítmica. Este procedimiento de búsqueda (conocido como búsqueda binaria) en una estructura ordenada tiene complejidad logarítmica O(ln n). · El proceso más común para ordenar un conjunto de elementos tiene complejidad cuadrática. El procedimiento consiste en crear una colección vacía de elementos. A ella se añade, en orden, el menor elemento del conjunto original que aún no haya sido elegido, lo que implica hacer un recorrido completo del conjunto original (O(n), siendo n el número de elementos del conjunto). Este recorrido sobre el conjunto original se realiza hasta que todos sus elementos están en la secuencia de resultado. Se puede ver que hay que hacer n selecciones (se ordena todo el conjunto) cada una con un coste n de ejecución: el procedimiento es de orden cuadrático O(n²). Hay que aclarar que hay diversos algoritmos de ordenación con mejores resultados.
