Una función g(n) pertenece a O(f(n)) si existen las constantes g y n g(n)<=c.f(n) , para todo c>=n se entiende T(n)>=cn. El orden de la magnitud de una funcion es el orden del termino de la funcion mas grande respecto de n.

ROTACION ASINTONICA “Omega” GRANDE

Se utiliza para especificar una cosa inferior a la velocidad de crecimiento T(n) y significa que existe una constante c tal que cn>=c(g(n)) para un numero infinito de valores n.

TIEMPO DE EJECUCION DE ALGORITMOS

El tiempo de ejecución de un programa en función de n (no de datos) de denomina T(n) se calcula sobre código contando las instrucciones ejecutadas multiplicando x el tiempo requerido para cada instrucción

s (sentencia=n)

For (int i=0; i

T(n)=t1+t2*n

Los algoritmos bn estructurados

a) sentencia sencilla. Contempla las sentencia de asignación entrada y salida de datos y tiene una complejidad constante orden 1=O(1)

b) secuencia de sentencias. La complejidad de ella es la suma de las complejidades individuales de cada una de ellas

c) decisión (if). Una condicion es de complejidad O(1) ya sea en la rama then o en la rama else

d) decisión multiple. Se tomara la complejidad de la flor de las ramas

e) cilco de conador explicito (for). Se realiza un numero especifico de veces independientemente de el.

Como se conecta Nodo A y Nodo B
A=New Apc Nodo;
B=New Apc Nodo;
A->siguiente=B;

Como se conecta Nodo B y Nodo A
B-> Siguiente =A;

Invertir el orden del nodo A y B

M=A;
A=B;
B=M;

Uno de los grandes problemas que se presentan es cuando el algoritmo tiene que tomar una decisión. Los problemas se clasifican en conjuntos de complejidad llamadas clases de complejidad.

CLASE DE COMPLEJIDAD P

Es el conjunto de problemas de decisión que pueden ser resueltos en tiempo polinomico calculando a partir de la entrada a una maquina de turing determinista y que corresponde a problemas que puede ser resuelto a un en el peor de los casos

Ej. Conocer un número primo.

CLASE DE COMPLEJIDAD NP

NO PROCESABLE

Es el conjunto de problemas de decisión que pueden ser resuelto por una marina de turing no determinista en tiempo polinomico las cuales tienen la propiedad de que su solución puede ser verificada.

CLASE DE COMPLEJIDAD NP COMPLETO

Es el conjunto de problemas de dedición en NP que destacan por su extrema complejidad y que decimos que se encuentran en la frontera externa de la clase NP.

NOTACION ASINTONICA O GRANDE

Se utilizan para hace referencia para la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrar su limite superior de tiempo de ejecución de un algoritmo en el peor de los casos.

La O

Es una función g(n) pertenece a O(f (n))

Rotacion asintótica “OMEGA”

Se utiliza para especificar una cosa inferior o la velocidad

Tiempo de ejecución del algoritmo

El riempo de ejecución de un programa en función de n (definición de datos) se denimina T(n)

Pendiente

Después que la teoría de computabilidad fue desarrollada se comenzó analizar la complejidad de los algoritmos. En 1960 Rabin fue el primer hombre en plantear en forma explicita cual es la complejidad computacional. Rabin sugirió el axioma que fue la base para el desarrollo de la teoría de la complejidad abstracta de blum y otros.

Una pequeña aportación (1965) aparecía en el articulo J. Hartmanis and R.E. stearns on the computacional complexity of algorithms. En este introduce la noción fundamental de medida de complejidad la cual queda definida como el tiempo de computación sobre de una maquina de Turing multicinta.

Se puede computar cualquier número irreal algebraico en tiempo real del número a una velocidad de un digito cada 100 paso.

Posteriormente Cobham publico un articulo the intrinsic computacional difficulty or funtion enfatizo el termino intrínseco es decir el estaba interesado en una teoría innovadora de maquinas. Se pregunto si la multiplicación es más compleja que la suma y considero que la pregunta podía ser contestada hasta que se desarrollaba la teoría.

También definió y caracterizo la importante de las clases de funciones llamadas función es de números naturales que son computables en tiempo contando por un polinomio cuyo argumento es longitud de entrada.