Skip to content

Latest commit

 

History

History
361 lines (229 loc) · 6.28 KB

Teoria_2do_Parcial.md

File metadata and controls

361 lines (229 loc) · 6.28 KB
Raw

Analisis de Algoritmos

Indice

Introducción

Nos permite comparar algoritmos en forma independiente de una plataforma en particular. Mide la eficiencia de un algoritmo, dependiendo del tamaño de la entrada

Pasos a seguir

  • Caracterizar los datos de entrada del algoritmo
  • Identificar las operaciones abstractas, sobre las que se basa el algoritmo
  • Realizar un análisis matemático, para encontrar los valores de las cantidades del punto anterior

Introducción_al_concepto_T(n)

Debemos enfocarnos en cuán rápido crece una función T(n) respecto al tamaño de la entrada. A esto lo llamamos la tasa o velocidad de crecimiento del tiempo de ejecución.

Ejemplo

Supongamos que un algoritmo, que corre con una entrada de tamaño n, tarda 6n2+100n+300 instrucciones de máquina. El término 6n2 se vuelve más grande que el resto de los términos, 100n+300 una vez que n se hace suficientemente grande, 20 en este caso

Gráfica que muestra los valores de 6n2 y de 100n+300 para valores de n de 0 a 100:

Al descartar los términos menos significativos y los coeficientes constantes, podemos enfocarnos en la parte importante del tiempo de ejecución de un algoritmo, su tasa o velocidad de crecimiento, sin involucrarnos en detalles que complican nuestro entendimiento.

Cuando descartamos los coeficientes constantes y los términos menos significativos, usamos notación asintótica.

Problema_1

Considerando que un algoritmo requiere f(n) operaciones para resolver un problema y la computadora procesa 100 operaciones por segundo.

Si f(n) es:

a. log10 n b. √n

$$ f(n) = log_{10}n\rightarrow 4 op$$

$$ 100op \rightarrow 1seg$$

$$ 4op \rightarrow \frac{4}{100} = 0.04seg $$

$$f(b) = \sqrt{n} \rightarrow 100op$$

$$ 100op \rightarrow 1seg$$

$$ 100op \rightarrow \frac{100}{100} = 1seg$$

Determine el tiempo en segundos requerido por el algoritmo para resolver un problema de tamaño n=10000.

Problema_2

Suponga que Ud. tiene un algoritmo ALGO-1 con un tiempo de ejecución exacto de 10n2. ¿En cuánto se hace más lento ALGO-1 cuando el tamaño de la entrada n aumenta:……….?

  • a. El doble

$$10n^{2}\to 10*(2n)^{2}$$

$$ = 10*(4n)^{2}$$

  • b. El triple

$$10n^{2}\to 10*(3n)^{2}$$

$$ = 10*(9n)^{2}$$

Cálculo_del_Tiempo_de_Ejecución

Programa Resolución 
int sum = 0;
int [] a = new int [n];
for (int i =1; i<= n ; i++ )
    sum += a[i];

$$ T(n)=cte_{1}+\sum_{i=1}^{(n)}cte_{2}=$$ $$ = cte_{1}+(n)*cte_{2}$$ $$ \Rightarrow O(n)$$

 
int sum = 0;
int [] a = new int [n][n];
for (int i =1; i<= n ; i++) {
    for (int j =1; j<= n ; j++)
        sum += a[i][j];
}

$$ T(n)=cte_{1}+\sum_{i=1}^{(n)}\sum_{j=1}^{n}cte_{2}=$$ $$ = cte_{1}+(n)*(n)*cte_{2}$$ $$ \Rightarrow O(n^{2})$$

 
int [] a = new int [n];
int [] s = new int [n];
for ( int i =1; i<= n ; i++ )
    s[i] = 0;
for ( int i =1; i<= n ; i++) {
    for (int j =1; j<= i ; j++)
        s[i] += a[j];
}

$$ T(n)=cte_{1}+\sum_{i=1}^{n}cte_{2}+ \sum_{i=1}^{n} \sum_{j=1}^{i}cte_{3}=$$ $$ = cte_{1}+n*cte_{2}+cte_{3} * \sum_{i=1}^{(n)} i=$$ $$ \Rightarrow O(n^{2})$$

 
int x= 0;
int i = 1;
while ( i <= n) {
    x = x + 1;
    i = i + 2;
}

$$ T(n) = cte_{1}+\sum_{i=1}^{(n+1)/2}cte_{2}$$ $$ cte_{1}+cte_{2}/2 * (n+1)$$ $$ \Rightarrow O(n)$$

 
int x= 1;
while (x < n)
    x = 2 *x;

$$ T(n) = cte_{1}+cte_{2}*log(n)$$

$$ \Rightarrow O(log(n))$$

 
Aclaración:
Si n es potencia de 2: realiza log(n) iteraciones
Si n no es potencia de 2: realiza log(n) + 1 iteraciones

Problema_3

¿Cuál es la expresión correcta respecto al tiempo de ejecución del siguiente segmento de código?

for (i = 0; i < n; i++)
    for (j = 1; j < n; j+=n/2)
        x = x + 1;

// El primer for es lineal y el segundo es logaritmico.
// El segundo for es constante porque no depende 
// de los datos de entrada
//El segundo for se trata como constante

$$ \sum_{i=0}^{n} \sum_{j=1}^{(n*2)}cte_1$$ $$ O(n)$$

Problema_4

Nota: Es cuadratico cuando tengo dos bucles lineales anidados

Considere el siguiente fragmento de código:

int count = 0;
int N = a.length;
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        a[j]++;

$$ cte_{1} + \sum_{i=0}^{N}\sum_{j=0}^{N} cte_{2} \to O(N^{2})$$

$$N = 3500 \to 1seg $$

$$ (3500^{2}) \to 1seg $$

N es el tamaño de la entrada

$$ (35000^{2}) \to 100seg $$

Suponga que tarda 1 seg cuando N=3500, ¿cuánto tardará aproximadamente para N=35000? Justifique su respuesta.

Ejemplo

private void imparesypares(int n){
    int x=0; int y=0;
    for (int i=1;i<=n;i++)
        if (esImpar(i))
            for (int j=i;j<=n;j++)
                x++;
        else
            for (int j=1;j<=i;j++)
                y++;
}
public boolean esImpar(int unNumero){
    if (unNumero%2 != 0)
        return true;
    else
        return false;
}

$$ T(n) = $$

$$\sum_{i=1}^{n}cte_{1}+\sum_{i=1}^{n[paso 2 ]}(\sum_{j=2i-1}^{n}cte_{2} + \sum_{j=1}^{2i}cte_{2})$$

$$\sum_{i=1}^{n}cte_{1}+\sum_{i=1}^{2/n}(\sum_{j=2i-1}^{n}cte_{2} + \sum_{j=1}^{2i}cte_{2})$$

$$cte_{1}n+ \sum_{i=1}^{n/2}cte_{2} (n-2i+1+1+2i-1+1)$$

$$cte_{1}n + cte_{2}(n+2)*n/2$$

$$cte_{1}n + cte_{2}/2(n^2)+cte_{2}*n$$

$$\to O(n^2)$$
  • El metodo esImpar tiene todas las sentencias constantes

$$T_{esImpar}(n) = cte_{1}$$

  • El metodo imparesypares tiene un loop en el que : cada iteración se llama al metodo esImpar y la mitad de las veces se ejecuta uno de los for (para valores de i) y la mitad restante el otro for (para valores de i pares)