Autor Tema: Lo computable es polinómico  (Leído 182 veces)

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado Amom

  • Principiante
  • *
  • Mensajes: 53
    • Grafos
Lo computable es polinómico
« en: Junio 08, 2017, 21:38:15 »
Reflexionando sobre el artículo de satisfacibilidad lógica he llegado a la siguiente conclusión:

Sabiendo que la complejidad del problema que hemos computado es θ(s+1) dónde s es el número de sumas (Y lógica).

Todo reside en cómo desarrollamos el algoritmo. Sea como fuere el algoritmo, la complejidad siempre será lineal pero, ¿y si el algoritmo se llama a sí mismo n veces?, es decir tiene que ejecutarse n veces. Ya sea el caso por ejemplo, el cálculo de un número factorial (n!) o la resolución de un sistema lineal de n ecuaciones con n incógnitas, recurrencias...

El número de llamadas al algoritmo es también lineal (n). En este caso la complejidad del algoritmo será n veces la complejidad del algoritmo, es decir: θ(n·s+n). Polinómico en este caso.

Si el número de llamadas fuese polinómica P(n) la complejidad del algoritmo, es decir, los tiempos de cálculo o computación, también será polinómica: θ(P(n)·s+P(n))

Un saludo.
"Dios no juega a los dados"- Albert Einstein

Desconectado javiucm

  • Supermoderador
  • Científico loco
  • *****
  • Mensajes: 3.126
Re:Lo computable es polinómico
« Respuesta #1 en: Junio 14, 2017, 00:19:06 »
¿de qué algoritmo en concreto estás hablando?
no todos tienen complejidad lineal ni polinómica, por ejemplo el cálculo del mcd y mcm tienen complejidad logarítmica O(log(n)). Además depende de la implementación concreta. Por ejemplo el factorial de un número entero, con implementación de bucle, tiene una complejidad O(n log(n) ^2) pero una implementación recursiva tiene una complejidad O(n)

Desconectado Amom

  • Principiante
  • *
  • Mensajes: 53
    • Grafos
Re:Lo computable es polinómico
« Respuesta #2 en: Octubre 11, 2017, 21:13:14 »
Sabiendo que: O(n log(n)^2) < O(n^3).

Implementándolo:  O((n^3)·s + n^3) = O((n^3) · (s+1))

Siendo s una constante de la implementación, el tiempo en el peor de los casos es polinómico.

Un saludo.
"Dios no juega a los dados"- Albert Einstein