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:
CPP
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.
CPP
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:
CPP
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++; }
Java
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.
C#
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.
Javascript
<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.
CPP
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 2 n).
Problema 5: encuentre la complejidad del siguiente programa:
CPP
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.
CPP
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 2 logn).
Problema 6: encuentre la complejidad del siguiente programa:
CPP
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:
CPP
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.
CPP
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 5 ).
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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA