[ Foro de Java ]

Ayuda sobre complijidad en java

La función filaSumaMax devuelve cuál es la fila de una matriz que contiene la suma
máxima de dos de sus elementos. La matriz se supone que tiene igual cantidad de filas
y columnas y sus elementos son mayores o iguales a cero.
a) calcular la cantidad de instrucciones de SumaMax
b) utilizar a) para calcular el orden de complejidad de filaSumaMax.

static int filaSumaMax(int[][] mat){
           int max = 0, filaMax=0;
           for(int i=0; i<mat.length; i++) {
                if(sumaMax(mat[i])>max) {
                      max = sumaMax(mat[i]);
                      filaMax=i;
                 }
            }
            return filaMax;
}

static int sumaMax(int[] vec){
            int max = 0;
            for(int i=0; i<vec.length; i++)
                for(int j=i+1; j<vec.length; j++)
                       if(vec[i]+vec[j]>max)
                             max = vec[i]+vec[j];
            return max;
}

Es mejor que lo resuelvas vos porque en el  parcial no vas a tener el foro.

Suponiendo que la matriz es de n x n:

a) Hay 2 ciclos anidados. El externo realiza n iteraciones. El interno realiza: (n-1).(n-2).(n-3)... iteraciones. O sea, para la primera iteración del ciclo exterior, el interior realiza (n-1) iteraciones, para la segunda (n-2), para la tercera (n-3) y así siguiendo hasta que para la última (enésima), el interno hace... ¡0!, y digo cero porque el ciclo exterior debería decir "i < vec.length - 1" para  que j no se vaya fuera del vector intentando sumar el último elemento de la fila con el ¿siguiente?

b) Componiendo "sumaMax" con "filaSumaMax" tenés 3 ciclos anidados. El de "filaSumaMax" hace n iteraciones. Imagino que si estás resolviendo un problema de complejidad algorítmica, sabés como calcular el O() de 3 ciclos anidados. ¡Ojo! que en el "if" de "filaSumaMax" se llama -ineficientemente- 2 veces a "sumaMax", esto cambiaría la cantidad de instrucciones (la f(n)) pero no el O() porque se suman, no se multiplican.