Esta pregunta ya tiene respuestas aquí :
Respuesta
Un algoritmo es polinomio (tiene tiempo de ejecución polinomial) si para algunos $ k, C > 0 $, su tiempo de ejecución en entradas de tamaño $ n $ es como máximo $ Cn ^ k $. De manera equivalente, un algoritmo es polinomio si para algunos $ k > 0 $, su tiempo de ejecución en entradas de tamaño $ n $ es $ O (n ^ k) $. Esto incluye lineal, cuadrático, cúbico y más. Por otro lado, los algoritmos con tiempos de ejecución exponenciales no son polinomiales.
Hay cosas intermedias, por ejemplo, el algoritmo más conocido para factorizar se ejecuta en el tiempo $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ para una constante $ C > 0 $; ese tiempo de ejecución se conoce como sub-exponencial . Otros algoritmos podrían ejecutarse en el tiempo $ O (\ exp (A \ log ^ C n)) $ para algunos $ A > 0 $ y $ C > 1 $, y estos se conocen como cuasi-polinomio . Este algoritmo ha sido reclamado recientemente para un registro discreto sobre características pequeñas.
Comentarios
Respuesta
La ejecución de un algoritmo puede llevar algo de tiempo de cálculo. Depende principalmente de la complejidad del algoritmo. Los científicos de la computación han creado una manera de clasificar el algoritmo basándose en su comportamiento de cuántas operaciones necesita realizar (más operaciones toman más tiempo).
Una de esa clase muestra complejidad de tiempo polinomial. Es decir, la complejidad operativa es proporcional a $ n ^ c $ mientras que n es el tamaño de la entrada y c es alguna constante. Obviamente, el nombre proviene de $ n ^ c $ que es un polinomio .
Hay otros «tipos» de algoritmos que toman un tiempo constante independientemente del tamaño de la entrada. Algunos toman $ 2 ^ n $ de tiempo (sí, muy poco la mayor parte del tiempo).
Lo simplifiqué demasiado para el profano y es posible que haya introducido errores. Así que lea más https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Comentarios
Respuesta
En términos sencillos, el tiempo de ejecución de su algoritmo.
El orden de los algoritmos (crecimiento) puede estar en Big-oh (O), little-oh (o), omega (Ω) o theta (Θ).
Si tiene problemas para calcular RR, consulte algunas preguntas que hice antes y vote si las comprende.
Digamos que tiene un ciclo for:
for(i=1 to n) x++
El orden o la complejidad temporal de este fragmento de código es: O (n)
¿Por qué big-oh? Porque queremos el peor de los casos en el que se ejecuta este fragmento de código.
Lea aquí (estos definen la complejidad de un algoritmo y le informan cómo se realizan los algoritmos en tiempo polinomial):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard
Resumen:
http://www.multiwingspan.co.uk/a23.php?page=types
Comentarios