algorithm
Notación Big-O

Observaciones

Un bucle simple

La siguiente función encuentra el elemento máximo en una matriz:

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

El tamaño de entrada es el tamaño de la matriz, a la que llamé len en el código.

Contemos las operaciones.

int max = INT_MIN;
size_t i = 0;

Estas dos tareas se realizan solo una vez, por lo que son 2 operaciones. Las operaciones que se realizan en bucle son:

if (max < array[i])
i++;
max = array[i]

Como hay 3 operaciones en el bucle, y el bucle se realiza n veces, agregamos 3n a nuestras 2 operaciones ya existentes para obtener 3n + 2 . Así que nuestra función toma 3n + 2 operaciones para encontrar el máximo (su complejidad es 3n + 2 ). Este es un polinomio donde el término de más rápido crecimiento es un factor de n, por lo que es O (n).

Probablemente habrás notado que la "operación" no está muy bien definida. Por ejemplo, dije que if (max < array[i]) era una operación, pero dependiendo de la arquitectura, esta declaración puede compilar, por ejemplo, tres instrucciones: una lectura de memoria, una comparación y una rama. También he considerado todas las operaciones como iguales, aunque, por ejemplo, las operaciones de memoria serán más lentas que las demás y su rendimiento variará enormemente debido, por ejemplo, a los efectos de caché. También he ignorado por completo la declaración de devolución, el hecho de que se creará un marco para la función, etc. Al final, no importa el análisis de complejidad, porque de cualquier forma que elija para contar las operaciones, solo cambiará el coeficiente del factor n y la constante, por lo que el resultado seguirá siendo O (n). La complejidad muestra cómo el algoritmo se escala con el tamaño de la entrada, ¡pero no es el único aspecto del rendimiento!

Un bucle anidado

La siguiente función comprueba si una matriz tiene algún duplicado tomando cada elemento, luego iterando sobre toda la matriz para ver si el elemento está ahí

_Bool contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len; j++) {
            if (i != j && array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

El bucle interno realiza en cada iteración una serie de operaciones que son constantes con n . El bucle externo también realiza algunas operaciones constantes y ejecuta el bucle interno n veces. El propio bucle externo se ejecuta n veces. Así que las operaciones dentro del bucle interno se ejecutan n^2 veces, las operaciones en el bucle externo se ejecutan n veces, y la asignación a i se realiza una vez. Por lo tanto, la complejidad será algo así como an^2 + bn + c , y como el término más alto es n^2 , la notación O(n^2) es O(n^2) .

Como habrá notado, podemos mejorar el algoritmo evitando hacer las mismas comparaciones varias veces. Podemos comenzar desde i + 1 en el bucle interno, porque todos los elementos antes de que ya se hayan verificado con todos los elementos de la matriz, incluido el del índice i + 1 . Esto nos permite soltar el cheque i == j .

_Bool faster_contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

Obviamente, esta segunda versión hace menos operaciones y por lo tanto es más eficiente. ¿Cómo se traduce eso a la notación Big-O? Bueno, ahora el cuerpo del bucle interno se ejecuta 1 + 2 + ... + n - 1 = n(n-1)/2 veces. Este es todavía un polinomio de segundo grado, y por lo tanto es solo O(n^2) . Claramente, hemos reducido la complejidad, ya que dividimos aproximadamente por 2 el número de operaciones que estamos realizando, pero aún estamos en la misma clase de complejidad definida por Big-O. Para reducir la complejidad a una clase más baja, tendríamos que dividir el número de operaciones por algo que tiende a infinito con n .

Un ejemplo de O (log n)

Introducción

Considere el siguiente problema:

L es una lista ordenada que contiene n enteros con signo (siendo n suficientemente grande), por ejemplo [-5, -2, -1, 0, 1, 2, 4] (aquí, n tiene un valor de 7). Si se sabe que L contiene el entero 0, ¿cómo puedes encontrar el índice de 0?

Enfoque ingenuo

Lo primero que viene a la mente es leer cada índice hasta que se encuentre 0. En el peor de los casos, el número de operaciones es n , por lo que la complejidad es O (n).

Esto funciona bien para valores pequeños de n , pero ¿hay una forma más eficiente?

Dicotomía

Considere el siguiente algoritmo (Python3):

a = 0
b = n-1
while True:
  h = (a+b)//2 ## // is the integer division, so h is an integer
  if L[h] == 0:
    return h
  elif L[h] > 0:
    b = h
  elif L[h] < 0:
    a = h

a y b son los índices entre los que 0 es que se encuentran. Cada vez que entramos en el bucle, utilizamos un índice entre a y b y lo utilizan para reducir el área de búsqueda.

En el peor de los casos, tenemos que esperar hasta que a y b sean iguales. ¿Pero cuántas operaciones lleva eso? No n, porque cada vez que entramos en el bucle, dividimos la distancia entre a y b en alrededor de dos. Más bien, la complejidad es O (log n).

Explicación

Nota: Cuando escribimos "log", nos referimos al logaritmo binario, o log base 2 (que escribiremos "log_2"). Como O (log_2 n) = O (log n) (puedes hacer los cálculos) usaremos "log" en lugar de "log_2".

Llamemos a x el número de operaciones: sabemos que 1 = n / (2 ^ x).

Entonces 2 ^ x = n, entonces x = log n

Conclusión

Cuando se enfrente a divisiones sucesivas (ya sea por dos o por cualquier número), recuerde que la complejidad es logarítmica.

O (log n) tipos de algoritmos

Digamos que tenemos un problema de talla n. Ahora, para cada paso de nuestro algoritmo (que necesitamos escribir), nuestro problema original se convierte en la mitad de su tamaño anterior (n / 2).

Así que en cada paso, nuestro problema se convierte en medio.

Cuando el espacio del problema se reduce (es decir, se resuelve por completo), no se puede reducir más (n se vuelve igual a 1) después de salir de la condición de verificación.

1. Digamos en el paso k o número de operaciones:

   problema-tamaño = 1

2. Pero sabemos que en el paso k, nuestro tamaño del problema debe ser:

   tamaño del problema = n / 2 ^k

3. De 1 y 2:

   n / 2 ^k = 1 o

   n = 2 ^k

4. Tomar registro en ambos lados

   log _e n = k log _e 2

   o

   k = log _e n / log _e 2

5. Usando fórmula log _x m / log _x n = log _n m

   k = log ₂ n

   o simplemente k = log n

Ahora sabemos que nuestro algoritmo puede ejecutarse al máximo hasta el registro n, por lo que la complejidad del tiempo se presenta como
O (log n)

Un ejemplo muy simple en código para soportar el texto anterior es:

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

Entonces, si alguien le pregunta si n es 256 cuántos pasos se ejecutarán en bucle (o cualquier otro algoritmo que reduzca su tamaño del problema a la mitad), puede calcularlo muy fácilmente.

k = log ₂ 256

k = log ₂ 2 ⁸ (=> log _a a = 1)

k = 8

Otro muy buen ejemplo para un caso similar es el algoritmo de búsqueda binaria .

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}