¿NP-Qué? Tipos de Complejidad de Problemas de Optimización Explicados

Explicación de los tipos de complejidad de problemas de optimización NP-Qué?

Edificio complejo. Imagen creada con Midjourney por el autor.

Una introducción a una de las preguntas centrales en ciencias de la computación

¿Cómo es que el problema de la ruta más corta es fácil de resolver, pero el problema del viajante de comercio no lo es? ¿Cuáles son las ideas matemáticas sobre esto? ¿Cómo determinar si un problema tomará un número inmanejable de pasos si su tamaño aumenta? En esta publicación aprenderás los conceptos básicos sobre este tema. Y si quieres profundizar en esto, he incluido una breve nota sobre uno de los problemas del premio del milenio relacionado con este tema al final de la publicación.

Antes de comenzar con la NP-dificultad, debes conocer los conceptos básicos de la complejidad temporal. Si estás familiarizado con la complejidad temporal, la notación Big O y el análisis del peor caso, puedes omitir la siguiente sección.

Complejidad Temporal

Cuando trabajamos con computadoras y escribimos programas, a menudo nos enfrentamos a problemas que pueden resolverse de diferentes maneras. Una cosa importante que debemos considerar es qué tan eficientes son estas soluciones. La complejidad temporal nos ayuda a comprender qué tan rápido se ejecuta un algoritmo a medida que el tamaño del problema que resuelve se vuelve más grande.

La notación Big O se puede comparar con etiquetar el algoritmo con una simple pegatina que nos dice cuánto tiempo tarda el algoritmo en finalizar en función de cuántas cosas estamos tratando. Es una forma de describir cómo crece el número de pasos de un algoritmo en relación con el tamaño de entrada del problema.

Nota: La complejidad temporal se relaciona esencialmente con la cantidad de pasos que se toman, en lugar del tiempo real, por lo que es un mal nombre. De lo contrario, podrías usar una computadora más rápida y el mismo algoritmo.

Etiquetando cajas (algoritmos) con una pegatina: ¿qué tan rápido eres? Imagen por el autor.

Por lo general, nos enfocamos en el peor escenario posible porque queremos asegurarnos de que sin importar qué entrada le demos al algoritmo, no tomará más tiempo del especificado. Esto nos ayuda a asegurarnos de que nuestra solución sea confiable incluso cuando las cosas se ponen difíciles.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Inteligencia Artificial

Investigadores de la NTU de Singapur proponen IT3D un nuevo método de refinamiento de IA Plug-and-Play para la generación de texto a 3D.

Ha habido un notable progreso en el dominio de texto a imagen, lo que ha generado una oleada de entusiasmo dentro de ...

Ciencia de Datos

Vuelva a entrenar los modelos de aprendizaje automático y automatice las predicciones por lotes en Amazon SageMaker Canvas utilizando conjuntos de datos actualizados.

Ahora puedes re-entrenar modelos de aprendizaje automático (ML) y automatizar flujos de trabajo de predicción en lote...

Inteligencia Artificial

Investigadores de Apple proponen un nuevo modelo de descomposición de tensores para el filtrado colaborativo con retroalimentación implícita

La capacidad para inferir las preferencias del usuario a partir de comportamientos pasados es crucial para ofrecer su...

Inteligencia Artificial

Falta de representación de nativos americanos en roles tecnológicos en Estados Unidos'.

Un informe encontró que los estudiantes nativos americanos siguen estando subrepresentados en los cursos de ciencias ...

Inteligencia Artificial

Desvelando GPTBot La audaz movida de OpenAI para rastrear la web

En un torbellino de innovación digital, OpenAI ha dado un golpe sorprendente al lanzar GPTBot, un rastreador web dise...