algorithm - programación - tiempo polinomial no deterministico

Tiempo polinomial y tiempo exponencial (7)

Tengo una pregunta sobre la diferencia entre los algoritmos de tiempo polinomiales, los algoritmos de tiempo no polinomiales y los algoritmos de tiempo exponencial, por ejemplo, si un algoritmo toma O (n ^ 2) tiempo, entonces ¿en qué categoría estará?

A continuación se muestran algunas funciones comunes de Big-O al analizar algoritmos.

O ( 1 ) - tiempo constante
O ( log (n) ) - tiempo logarítmico
O ( (log (n)) ^c ) - tiempo de polylogarithmic
O ( n ) - tiempo lineal
O ( n ² ) - tiempo cuadrático
O ( n ^c ) - tiempo polinomial
O ( c ⁿ ) - tiempo exponencial

(n = tamaño de entrada, c = alguna constante)

Aquí está el gráfico modelo que representa la complejidad Big-O de algunas funciones

aplausos :-)

Créditos gráficos http://bigocheatsheet.com/

O (n ^ 2) es el tiempo polinomial. El polinomio es f (n) = n ^ 2. Por otro lado, O (2 ^ n) es el tiempo exponencial, donde la función exponencial implícita es f (n) = 2 ^ n. La diferencia es si la función de n coloca n en la base de una exponenciación, o en el exponente mismo.

Cualquier función de crecimiento exponencial crecerá significativamente más rápido (a largo plazo) que cualquier función polinómica, por lo que la distinción es relevante para la eficiencia de un algoritmo, especialmente para valores grandes de n.

Tiempo polinomial.

Un polinomio es una combinación lineal de términos que se parecen a Constant * x^k Por el contrario, exponencial significa algo como k^x , donde en ambos casos k es una constante yx es una variable.

El tiempo de ejecución de los algoritmos exponenciales crece mucho más rápido que el de los polinomios.

mira esto

http://en.wikipedia.org/wiki/Big_oh#Orders_of_common_functions

exponencial es peor que polinomio.

O (n ^ 2) cae en la categoría cuadrática, que es un tipo de polinomio (el caso especial del exponente es igual a 2) y mejor que el exponencial.

Exponencial es mucho peor que el polinomio. Mira cómo crecen las funciones

n = 10 | 100 | 1000 n^2 = 100 | 10000 | 1000000 k^n = k^10 | k^100 | k^1000

k ^ 1000 es excepcionalmente grande a menos que k sea más pequeño que algo como 1.1. Al igual, algo así como cada partícula en el universo tendría que hacer 100 billones de billones de operaciones por segundo durante billones de billones de billones de años para lograrlo.

No lo calculé, pero ES TAN GRANDE.

o (n sequre) es la complejidad de tiempo polinimal mientras o (2 ^ n) es la complejidad de tiempo exponencial si p = np en el mejor de los casos, en el peor caso p = np no es igual cuando el tamaño de entrada crece tanto o aumenta el tamaño de entrada Ya va al peor de los casos y su manejo aumenta la tasa de crecimiento de complejidad y depende de n tamaño de entrada cuando la entrada es pequeña es polinimal cuando el tamaño de entrada es grande y grande, entonces p = np no es igual significa que la tasa de crecimiento depende del tamaño de la entrada "N ". los conjuntos optimización, sat, clique y independ también se encontraron en exponencial a polinimal.

tiempo polinómico O (n) ^ k significa El número de operaciones es proporcional a la potencia k del tamaño de la entrada

tiempo exponencial O (k) ^ n significa El número de operaciones es proporcional al exponente del tamaño de la entrada

Exponencial (Tiene una función exponencial si MINIMAL ONE EXPONENT depende de un parámetro):

Ej f (x) = constante ^ x

Polinomio (Usted tiene una función polinomial si NO EXPONENTE depende de algunos parámetros de función):

Ej f (x) = x ^ constante