Análisis de Algoritmos | Conjunto 4 (Análisis de bucles) – Part 1

Hemos discutido el análisis asintótico ,  los casos peor, promedio y mejor y las notaciones asintóticas en publicaciones anteriores. En este post, se discute un análisis de programas iterativos con ejemplos simples. 

1) O(1): la complejidad de tiempo de una función (o conjunto de declaraciones) se considera como O(1) si no contiene bucle, recursividad ni llamada a ninguna otra función de tiempo no constante. 
 

   // set of non-recursive and non-loop statements

Por ejemplo, la función swap() tiene una complejidad de tiempo O(1). 
Un bucle o recursión que se ejecuta un número constante de veces también se considera como O(1). Por ejemplo, el siguiente bucle es O(1). 
 

   // Here c is a constant   
   for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

2) O(n): La complejidad temporal de un bucle se considera O(n) si las variables del bucle se incrementan/disminuyen en una cantidad constante. Por ejemplo, las siguientes funciones tienen una complejidad de tiempo O(n). 
 

   // Here c is a positive integer constant   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

3) O(n ^c ) : La complejidad temporal de los bucles anidados es igual al número de veces que se ejecuta la instrucción más interna. Por ejemplo, los siguientes bucles de muestra tienen una complejidad de tiempo  O(n ^{2 )}
 

  
   for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i -= c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

Por ejemplo, la ordenación por selección y la ordenación por inserción tienen una complejidad de tiempo  O(n ^{2 ).}
4) O(Logn) Tiempo La complejidad de un bucle se considera O(Logn) si las variables del bucle se dividen/multiplican por una cantidad constante. Y también para la llamada recursiva en la función recursiva, la Complejidad del tiempo se considera como O (Inicio de sesión).
 

   for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

//Recursive function
void recurse(n)
{
    if(n==0)
        return;
    else{
        // some O(1) expressions
    }
    recurse(n-1);
}

Por ejemplo, la búsqueda binaria (consulte la implementación iterativa) tiene una complejidad de tiempo O (inicio de sesión). Veamos matemáticamente cómo es O(Log n). La serie que obtenemos en el primer bucle es 1, c, c ² , c ³ , … c ^k . Si ponemos k igual a Log _c n, obtenemos c ^{Log _c n} que es n. 
5) O(LogLogn) La complejidad temporal de un bucle se considera O(LogLogn) si las variables del bucle se reducen/aumentan exponencialmente en una cantidad constante. 
 

   // Here c is a constant greater than 1   
   for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
   }
   //Here fun is sqrt or cuberoot or any other constant root
   for (int i = n; i > 1; i = fun(i)) { 
       // some O(1) expressions
   }

Vea esto para detalles matemáticos. 
¿Cómo combinar las complejidades temporales de bucles consecutivos?  
Cuando hay bucles consecutivos, calculamos la complejidad del tiempo como la suma de las complejidades del tiempo de los bucles individuales. 
 

   for (int i = 1; i <=m; i += c) {  
        // some O(1) expressions
   }
   for (int i = 1; i <=n; i += c) {
        // some O(1) expressions
   }
   Time complexity of above code is O(m) + O(n) which is O(m+n)
   If m == n, the time complexity becomes O(2n) which is O(n).   

¿Cómo calcular la complejidad del tiempo cuando hay muchas declaraciones if, else dentro de los bucles?  
Como se discutió aquí , la complejidad del tiempo en el peor de los casos es la más útil entre la mejor, la media y la peor. Por lo tanto, debemos considerar el peor de los casos. Evaluamos la situación cuando los valores en condiciones if-else hacen que se ejecute un número máximo de declaraciones. 
Por ejemplo, considere la función de búsqueda lineal donde consideramos el caso cuando un elemento está presente al final o no está presente en absoluto. 
Cuando el código es demasiado complejo para considerar todos los casos if-else, podemos obtener un límite superior ignorando if-else y otras declaraciones de control complejas. 
¿Cómo calcular la complejidad temporal de funciones recursivas? 
La complejidad temporal de una función recursiva se puede escribir como una relación de recurrencia matemática. Para calcular la complejidad del tiempo, debemos saber resolver las recurrencias. Pronto discutiremos las técnicas de resolución de recurrencias en una publicación separada. 

La siguiente es una hoja de trucos de las complejidades temporales de varios algoritmos.

Hoja de trucos de algoritmos

Algoritmo	Mejor caso	Caso promedio	Peor de los casos
Clasificación de selección	O(n^n)	O(n^n)	O(n^n)
Ordenamiento de burbuja	En)	O(n^n)	O(n^n)
Tipo de inserción	En)	O(n^n)	O(n^n)
Clasificación de árbol	O (iniciar sesión)	O (iniciar sesión)	O(n^n)
Clasificación Radix	O(dn)	O(dn)	O(dn)
Ordenar por fusión	O (iniciar sesión)	O (iniciar sesión)	O (iniciar sesión)
Ordenar montón	O (iniciar sesión)	O (iniciar sesión)	O (iniciar sesión)
Ordenación rápida	O (iniciar sesión)	O (iniciar sesión)	O(n^n)
Clasificación de cubo	O(n+k)	O(n+k)	O(n^n)
Clasificación de conteo	O(n+k)	O(n+k)	O(n+k)

Cuestionario sobre análisis de algoritmos 

Para más detalles, consulte:
Diseño y Análisis de Algoritmos .

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.