adsd




INGENIERÍA EN SISTEMAS COMPUTACIONALES



Estructura de datos



Docente: Gustavo Miranda



Actividad: Investigación





Nombre: Vladimir Gerardo Quiñones Calderón
No. De control: 13231294
GRUPO: 3 “B”

COMPLEJIDAD EN TIEMPO

1. El tiempo de Ejecución de un programa se mide en función de N, lo que designaremos como T(N).

2. Esta función se puede calcularfísicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de código como:
S1;
for(x = 0; x < N; x++)
S2;
Demanda: T(N) = t1 + t2 * N
Donde t1 es el tiempo que lleva ejecutar la serie S1 de sentencias, y t2 es el que lleva laserie S2.

1 Habitualmente todos los algoritmos contienen alguna sentencia condicional o selectiva, haciendo que las sentencias ejecutadas dependan de la condición lógica, esto hace que aparezca más de un valor para T(N), es por ello que debemos hablar de un rango de valores:
Tmin(N) ≤ T(N) ≤ Tmax(N)


2 Estos extremos son llamados "el peor caso" y "el mejor caso" y entre ambos se puede hallar"el caso promedio" o el más frecuente, siendo este el más difícil de estudiar; nos centraremos en el "el peor caso" por ser de fácil cálculo y se acerca a "el caso promedio", brindándonos una medida pesimista pero fiable.

3 Toda función T(N) encierra referencias al parámetro N, y a una serie de constantes Ti dependientes de factores externos al algoritmo. Se tratará de analizar los algoritmosdándoles autonomía frente a estos factores externos, buscando estimaciones generales ampliamente válidas, a pesar de ser demostraciones teóricas.

Análisis de Complejidad de Tiempo
El tiempo de ejecución depende de diversos factores. Se tomará como más relevante el relacionado con la entrada de datos del programa, asociando a un problema un entero llamado tamaño del problema, el cual es unamedida de la cantidad de datos de entrada.
Análisis de complejidad en tiempo de las instrucciones de un lenguaje
A continuación, se presentan algunas reglas para evaluar la complejidad en tiempo de los programas, tomando como base, el análisis para unas instrucciones en un pseudo-lenguaje.
Regla 1: La función de complejidad en tiempo de una instrucción de asignación simple es una constante (quedepende de la arquitectura donde se ejecutará el algoritmo), independientemente del tamaño de la entrada de datos, y es de orden O (1). No todas las asignaciones son O (1).
Regla 2: La complejidad en tiempo de una operación simple de entrada/salida es T(n)=c (constante), por lo tanto es de orden O (1).
Regla 3: De la regla de la suma se deriva que la complejidad en tiempo de una secuencia de kinstrucciones cualesquiera P1;P2;...;Pk, siendo Ti(n)=O(fi(n)) la complejidad de la instrucción Pi.
Ejemplo:
Las tres instrucciones {b ¬ 100; a ¬ a+1; a ¬ (b div 5) mod 7 - 3} son de complejidad
T1(n)=c1, T2
(n)=c2, T3
(n)=c3 respectivamente con c1£c2£c3. Así, la función de complejidad de las tres instrucciones en conjunto es:
T(n)=T1(n)+T2(n)+T3(n)=max{c1,c2,c3}=c3 Þ T(n)=O(1).
Nótese que noes relevante cual instrucción se tarda más y cual menos, porque al final T(n) es una constante y por ende de orden O(1). Por esto, la complejidad de cada instrucción simple la tomaremos como la misma constante "c" para simplificar los razonamientos.
Regla 4: La complejidad en tiempo de una instrucción selectiva condicional simple de la forma:
si entonces f si está dado por complejidad T1(n) desumado a la complejidad T2(n) de (porque en el peor caso se ejecutan ambas). Por regla de la suma, si T1(n)= O(f(n)) y T2(n)=O(g(n)), entonces el tiempo requerido para ejecutar el condicional simple es la suma T1(n)+T2(n), lo cual es O(max{f(n),g(n)}).
Análogamente, para una instrucción selectiva de la forma: si entonces { es de complejidad T1(n)=O(f(n)) }
{ de complejidad T2(n)=O(g(n))...