Análisis de Algoritmos | Serie 5 (Problemas de práctica)

Hemos discutido el análisis asintótico , los casos peor, promedio y mejor , las notaciones asintóticas y el análisis de bucles en publicaciones anteriores.
En este post se discuten problemas prácticos sobre el análisis de algoritmos.
Problema 1: encuentre la complejidad de la siguiente recurrencia:  

         { 3T(n-1), if n>0,
T(n) =   { 1, otherwise

Solución:  

Let us solve using substitution.
T(n) = 3T(n-1)
     = 3(3T(n-2)) 
     = 32T(n-2)
     = 33T(n-3)
       ...
       ...
     = 3nT(n-n)
     = 3nT(0) 
     = 3n
This clearly shows that the complexity 
of this function is O(3n).

Problema 2: Encuentra la complejidad de la recurrencia:  

        { 2T(n-1) - 1, if n>0,
T(n) =   { 1, otherwise

Solución: 

Let us try solving this function with substitution.
T(n) = 2T(n-1) - 1
     = 2(2T(n-2)-1)-1 
     = 22(T(n-2)) - 2 - 1
     = 22(2T(n-3)-1) - 2 - 1 
     = 23T(n-3) - 22 - 21 - 20
       .....
       .....
     = 2nT(n-n) - 2n-1 - 2n-2 - 2n-3
       ..... 22 - 21 - 20

     = 2n - 2n-1 - 2n-2 - 2n-3
       ..... 22 - 21 - 20
     = 2n - (2n-1) 
[Note: 2n-1 + 2n-2 + ...... +  20 = 2n - 1]
T(n) = 1
Time Complexity is O(1). Note that while 
the recurrence relation looks exponential
the solution to the recurrence relation 
here gives a different result.

Problema 3: encuentre la complejidad del siguiente programa: 
 

function(int n)
{
    if (n==1)
       return;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            printf("*");
            break;
        }
    }
}

Solución: Considere los comentarios en la siguiente función. 

function(int n)
{
    if (n==1)
       return;
    for (int i=1; i<=n; i++)
    {
        // Inner loop executes only one
        // time due to break statement.
        for (int j=1; j<=n; j++)
        {
            printf("*");
            break;
        }
    }
}

Complejidad temporal de la función anterior O(n). Aunque el ciclo interno está limitado por n, pero debido a la instrucción break, se ejecuta solo una vez.
 
Problema 4: encuentre la complejidad del siguiente programa: 

void function(int n)
{
    int count = 0;
    for (int i=n/2; i<=n; i++)
        for (int j=1; j<=n; j = 2 * j)
            for (int k=1; k<=n; k = k * 2)
                count++;
}

static void function(int n)
{
    int count = 0;
    for (int i = n / 2; i <= n; i++)
        for (int j = 1; j <= n; j = 2 * j)
            for (int k = 1; k <= n; k = k * 2)
                count++;
}
 
// This code is contributed by rutvik_56.

static void function(int n)
{
    int count = 0;
    for (int i = n / 2; i <= n; i++)
        for (int j = 1; j <= n; j = 2 * j)
            for (int k = 1; k <= n; k = k * 2)
                count++;
}
 
// This code is contributed by pratham76.

<script>
function function1(n)
{
    var count = 0;
    for (i = n / 2; i <= n; i++)
        for (j = 1; j <= n; j = 2 * j)
            for (k = 1; k <= n; k = k * 2)
                count++;
}
 
// This code is contributed by umadevi9616
</script>

Solución: Considere los comentarios en la siguiente función. 

void function(int n)
{
    int count = 0;
    for (int i=n/2; i<=n; i++)
 
        // Executes O(Log n) times
        for (int j=1; j<=n; j = 2 * j)
 
            // Executes O(Log n) times
            for (int k=1; k<=n; k = k * 2)
                count++;
}

Complejidad temporal de la función anterior O(n log ² n).
 
Problema 5: encuentre la complejidad del siguiente programa: 

void function(int n)
{
    int count = 0;
    for (int i=n/2; i<=n; i++)
        for (int j=1; j+n/2<=n; j = j++)
            for (int k=1; k<=n; k = k * 2)
                count++;
}

Solución: Considere los comentarios en la siguiente función. 
 

void function(int n)
{
    int count = 0;
 
    // outer loop executes n/2 times
    for (int i=n/2; i<=n; i++)
 
        // middle loop executes  n/2 times
        for (int j=1; j+n/2<=n; j = j++)
 
            // inner loop executes logn times
            for (int k=1; k<=n; k = k * 2)
                count++;
}

Complejidad temporal de la función anterior O(n ² logn).
 
Problema 6: encuentre la complejidad del siguiente programa: 
 

void function(int n)
{
    int i = 1, s =1;
    while (s <= n)
    {
        i++;
        s += i;
        printf("*");
    }
}

Solución: Podemos definir los términos ‘s’ según la relación s _i = s _i-1 + i. El valor de ‘i’ aumenta en uno por cada iteración. El valor contenido en ‘s’ en la i ^-ésima iteración es la suma de los primeros enteros positivos ‘i’. Si k es el número total de iteraciones tomadas por el programa, entonces el bucle while termina si: 1 + 2 + 3 ….+ k = [k(k+1)/2] > n Entonces k = O(√n).
Complejidad temporal de la función anterior O(√n).
 
Problema 7: encuentre un límite superior ajustado en la complejidad del siguiente programa: 
 

void function(int n)
{
    int count = 0;
    for (int i=0; i<n; i++)
        for (int j=i; j< i*i; j++)
            if (j%i == 0)
            {
                for (int k=0; k<j; k++)
                    printf("*");
            }
}

Solución: Considere los comentarios en la siguiente función. 
 

void function(int n)
{
    int count = 0;
 
    // executes n times
    for (int i=0; i<n; i++)
 
        // executes O(n*n) times.
        for (int j=i; j< i*i; j++)
            if (j%i == 0)
            {
                // executes j times = O(n*n) times
                for (int k=0; k<j; k++)
                    printf("*");
            }
}

Complejidad temporal de la función anterior O(n ⁵ ).

Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.