1

¿Podrían ayudarme con la complejidad de este algoritmo? No comprendo que valor tendría el for si está dentro del while y el valor del segundo while estando dentro de ese for

int algoritmo1(int a[], int n) {
    int k, x, i;
    if (n < 3) return -1;
    x = n; i = 0;
    while (i < n - 2) {
        for (int j = i + 1; j < n - 1; j++) {
            k = j + 1;
            while (k < n) {
                k++; x = x + (a[i] * a[j] * a[k - 1]);
            }
        }
        i++;
    }
    return x;
}
1
  • 3
    No creo que tu pregunta sea de Python...
    – Rodrigo
    Commented el 5 mar. 2021 a las 18:47

2 respuestas 2

1

La complejidad del algoritmo que presentas es O(n^3).

Vamos a asumir una subrutina f() que se ejecuta en tiempo constante. Queremos saber cuántas veces llamamos a esta subrutina en función de n.

Ahora bien, si solo tuvieras el while más externo, tendríamos algo así

int i = 0;
while (i < n - 2) {
    f() // Recuerda que una llamada a esta función es constante
    i++;
}

Tomemos algunos valores de n para ver cuantas veces se llama la subrutina f.

Para n = 2

Se llama 0 veces por lo que la condición del ciclo no se cumple ni la primera vez.

Para n = 4

La subrutina f será llamada 2 veces. (i = 0, i = 1)

Para n = 100

La subrutina f será llamada 98 veces.

En general

La subrutina f se llamará O(n-2) veces.

Ahora bien, cuando hablamos de complejidad algorítmica, nos preocupamos por la tasa a la que crece un algoritmo con respecto a la entrada, por lo que las constantes se omiten.

Entonces tenemos que esta parte es O(n).

Ahora, seguimos con el ciclo for.

 int i = 0;
 while (i < n - 2) {
    for (int j = i + 1; j < n - 1; j++) {
        f();
    }
    i++;
}

Sabemos que el while se ejecuta O(n) veces. La pregunta es entonces ¿cuantas veces se ejecuta el for por cada una de esas n veces?.

Para n = 5

Para i = 0; f será llamada cuando j = 1, 2, 3 (3 veces)

Para i = 1; f será llamada cuando j = 2, 3 (2 veces)

Para i = 2; f será llamada cuando j = 3 (1 vez)

Por lo que tenemos que el número total de veces que se llama a f es 3+2+1 cuando n = 5.

Para el caso general esto se reduce a una sumatoria.

1 + 2 + ... + (n-3) + (n-2) = (n-2) * (n-1) / 2

(n-2) * (n-1) / 2 = O(n^2)

Tenemos que la complejidad es de O(n^2)

Finalmente, al agregar el ciclo más anidado.

int i = 0;
int k = 0;
 while (i < n - 2) {
    for (int j = i + 1; j < n - 1; j++) {
        k = j + 1;
        while (k < n) {
            f();
            k++;
        }
    }
    i++;
}

Ya sabemos que el while más afuera y el for son O(n^2).

Analicemos el mismo caso que teníamos antes cuando n = 5.

Para i = 0, j = 1; f será llamado cuando k = 2, 3, 4 (3 veces)

Para i = 0, j = 2; f será llamado cuando k = 3, 4 (2 veces)

Para i = 0, j = 3; f será llamado cuando k = 4 (1 vez)

Para i = 1, j = 2; f será llamado cuando k = 3, 4 (2 veces)

Para i = 1, j = 3; f será llamado cuando k = 4 (1 vez)

Para i = 2, j = 3; f será llamado cuando k = 4 (1 vez)

En total se llamó 10 veces.

En general la subrutina f se llama la siguiente cantidad de veces.

introducir la descripción de la imagen aquí

Nótese que aunque 5^3 = 125, solo se ejecuta 10 veces para ese caso f. Esto es porque este tipo de análisis se preocupa para cuando la entrada se vuelve más grande. Por ejemplo, este algoritmo resulta impráctico si hubiesen 10000 elementos, por lo que la subrutina f se ejecutaría cerca de 166x10^9 veces.

Como curiosidad la sumatoria anterior es igual a

O(n + n(n + 1)(n - 4) / 6)

O(n^3/6 - n^2/2 + n/3)

1
  • A esto es a lo que me referia el orden mas exacto es como tu dices O(n^3/6-n2/2+n^3), decir que solo es O(n^3) es muy general
    – Japv
    Commented el 6 mar. 2021 a las 5:56
0

Tanto el while como el for, son bucles.

Dicho de manera coloquial, estás iterando un bucle, en un bucle, en un bucle.

Por lo tanto, estamos hablando de una matriz tridimensional, es decir un algoritmo de complejidad O(n³). Y así sucesivamente a medida que añades bucles. Por ejemplo, si colocases todo tu algoritmo dentro de otro for (bucle) sería O(n⁴).

Espero haberte ayudado

10
  • No se si lo de matriz tridimensional venga al caso. En el código del OP solo es un arreglo.
    – JhonRM
    Commented el 5 mar. 2021 a las 21:32
  • @JhonRayo99 precisamente un arreglo es una matriz de 1 dimensión
    – TomuRain
    Commented el 5 mar. 2021 a las 22:42
  • Si, de acuerdo, pero y lo de matriz tridimensional de donde sale?
    – JhonRM
    Commented el 5 mar. 2021 a las 22:48
  • @TomuRain, realmente no es tan así, que halla 3 ciclos no necesariamente quiere decir que el orden sea O(n3), bien podría ser O(n3 + nlog(n)) o cualquier otro orden, n3 es cuando todos los ciclos hacen la misma cantidad de iteraciones ej todos van de 1 a 5, y por otra parte que haya 3 ciclos anidados no quiere decir que estés recorriendo una matriz tridimensional, en este caso particular no creo que el orden sea O(n3)
    – Japv
    Commented el 5 mar. 2021 a las 23:24
  • De hecho si es O(n^3). Solo pues que lo que dices si es cierto, la justificación no es que haya 3 ciclos. La razón es que el bucle más externo se ejecuta n-2 veces que viene a ser lo mismo que n en términos asintóticos. Luego el for se ejecuta (n-2+n-3+...) (n-2) veces. Que es O(n^2). Y lo mismo sucede con el while más anidado. Y se concluye que es O(n^3). Aunque fácilmente yo podría tener un ciclo que sea O(logn). Por ejemplo la implementación iterativa de búsqueda binaria.
    – JhonRM
    Commented el 6 mar. 2021 a las 1:04

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.