Bucles anidados funcionamiento java y complejidad computacional

[bartvander]

Tengo una duda en java en cuanto a bucles anidados. Expongo en problema y seguro que debe de ser sencillo, pero yo no logro averiguar como funciona. se trata del ejemplo de subsecuencia de suma máxima. Un algoritmo que busca la máxima suma consecutiva.

Uno de los algoritmos con eficiencia N cubo.

public stactic int subsecuenciaSumaMaxima ( int [] a)
{
     int sumaMax = 0;
     for( int i = 0; i < a.length; i++)   lo tengo claro recorre el vector "a"
          for( int j = i; j < a.length; j++)   por lo que yo entiendo vuelve a recorrer el vector.
          {
                  int sumaActual = 0;
   
                  for (int k = i; k <= j; k++)  coge k el valor de i y va hasta el valor de j y luego el valor de k lo utiliza como posición de vector.
                        sumaActual += a[k];

                  if ( sumaActual < sumaMax)
                  {
                             sumMax = sumaActual;
                             secIni = i;
                             secFin = j;

        }
    }
  return sumaMax;
}


Mi duda es sobre como funciona el anudamiento. En el primer for, coge la i el valor 0. Pasa al segundo vector y la j debe de coger el valor 0 que tiene la i. en el último for la k coge el valor de i que es 0 y lo compara con el valor de j que debe de ser 0. Por lo que no entiendo muy bien como funciona este algoritmo. Si alguien me pudiera explicar como funcionan los anidamiéntos se lo agradecería porque es donde creo que fallo que no se como funcionan, porque el algoritmo es correcto.

[slif33r]

No se si podrias poner todo el codigo completo, con el main osea todo el codigo fuente del programilla, para explicarlo mejor tipo una prueba de escritorio, aunque mejor seria en vivo y en directo  .
Lo que te puedo decir es que:
1er. for( int i = 0; i < a.length; i++) //antes que se se ejecute la i++ pasa a:
  2do. for( int j = i; j < a.length; j++) //antes que se ejecute la j++ pasa a :
     3er. for (int k = i; k <= j; k++)
/*3er.for (int k = i; k <= j; k++)  aca si esta bucle se realiza normal como si fuera un for independiente claro hata que la condición k<=j(k<=0) sea falsa, una vez terminada este bucle, recien se realiza el incremento de j++ se vuelve a:
   2do for ( int j = 1; j < a.length; j++) si j<a.lenght es verdad se pasa al 3er for
3er. for (int k = i; k <= j; k++)  aca si esta bucle se realiza normal como si fuera un for independiente claro hata que la condición k<=j(k<=1) sea falsa, una vez terminada este bucle, recien se realiza el incremento de j++ se vuelve a:
 2do for( int j = 2; j < a.length; j++) si j<a.lenght es verdad se pasa al 3er for
y se vuelve a repetir la secuencia .....
esto sigue hasta que  j < a.length sea falsa, una vez comprobada su falsedad recien se realiza el incremento de i++
y se pasa al primer 1er for( int i = 1; i < a.length; i++)
volvemos hacer lo mismo osea :
***********************************
1er. for( int i = 0; i < a.length; i++) //antes que se se ejecute la i++ pasa a:
  2do. for( int j = i; j < a.length; j++) //antes que se ejecute la j++ pasa a :
     3er. for (int k = i; k <= j; k++)
/*3er.for (int k = i; k <= j; k++)  aca si esta bucle se realiza normal como si fuera un for independiente claro hata que la condición k<=j(k<=0) sea falsa, una vez terminada este bucle, recien se realiza el incremento de j++ se vuelve a:
   2do for ( int j = 1; j < a.length; j++) si j<a.lenght es verdad se pasa al 3er for
3er. for (int k = i; k <= j; k++)  aca si esta bucle se realiza normal como si fuera un for independiente claro hata que la condición k<=j(k<=1) sea falsa, una vez terminada este bucle, recien se realiza el incremento de j++ se vuelve a:
 2do for( int j = 2; j < a.length; j++) si j<a.lenght es verdad se pasa al 3er for
y se vuelve a repetir la secuencia .....
esto sigue hasta que  j < a.length sea falsa, una vez comprobada su falsedad recien se realiza el incremento de i++
y se pasa al primer 1er for( int i = 1; i < a.length; i++)
***************************************************
y esto acabara cuando en: for( int i = 0; i < a.length; i++) la condición  i < a.length sea falsa.
no se si me deje entender algo despues de tanto palabreo, a ver si me pasas todo el programa completo y te lo explicaria con un ejemplo haciendo una prueba de escritorio

[javi in the sky]

Aquí dejo el programa preparado con un main para poder ejecutarlo, cosa que ya he hecho; sin embargo no veo que esté algoritmo haga nada útil. Voy a poner primero el código y luego lo comento:

Código: [Seleccionar]

import java.util.Arrays;

public class test1 {
 

public static void main (String[] Args){

int [] vector = {-33, -5, -3};

System.out.println ("Vector de entrada: " + Arrays.toString(vector));
System.out.println ("Subsecuencia suma máxima = " + subsecuenciaSumaMaxima(vector));
}

public static int subsecuenciaSumaMaxima ( int [] a) {
     int sumaMax = 0;
     int secIni;
     int secFin;
     for( int i = 0; i < a.length; i++)   
          for( int j = i; j < a.length; j++)   
          {
                  int sumaActual = 0;  //Esta declaración aquí dentro supone que sumaActual se machaca en todas las pasadas menos en la última
   
                  for (int k = i; k <= j; k++) 
                        sumaActual += a[k];

                  if ( sumaActual < sumaMax){
                                                sumaMax = sumaActual;
                                                secIni = i;
                                                secFin = j;
                                            }
    }
  return sumaMax;
}

}
Con un vector de tres enteros positivos el algoritmo devuelve siempre cero. Con un vector de tres enteros negativos el algoritmo devuelve la suma de los tres valores.

¿Es esto lo que se supone que debía hacer? Me harían falta ejemplos de qué es lo que se quiere lograr para poder plantear algo útil, porque ahora mismo es que no sé qué es lo que se querría lograr.

Con un vector de tres enteros positivos tenemos el bucle i que va de 0 a 2, el bucle j que va de 0 a 2 y el bucle k que va inicialmente de 0 a 0. Ejecuta sumaActual = 0 + primer elemento del array, al no ser menor que sumaMax j toma su siguiente valor (ahora j=1) y ocurre lo mismo. Ahora j=2, ocurre lo mismo y termina el bucle j. Se llega al return y se acabó.

Con un vector de tres enteros negativos el proceso es igual, pero en cada ocasión sumaActual es menor que sumaMax por lo que se ejecuta el if y se cambian los valores de secIni y secFin (que no sé para qué sirven). Una vez se ha obtenido la suma de los valores negativos se llega al return y se acabó.

¿Para qué sirve tanto bucle?

[bartvander]

Este es un ejemplo de un método que hay en el libro de estructuras de datos de Java, el libro que se utiliza en la UNED. No hay programa completo, solo este trozo. Se supone que este algoritmo calcula la mayor suma secuencial. O sea va sumando números secuencialmente dentro del vector y devuelve la suma consecutiva mas alta que haya en el vector. Mi duda y mi pregunta es que no se muy bien como funcionan los bucles anidados y por eso no logro comprende este código. Así que me valdría este código o cualquier otro donde me podáis explicar como funcionan los bucles anidados.

[javi in the sky]

Sobre el programa en sí, necesitaría saber exactamente qué es lo que hay que hacer, con varios ejemplos resueltos, para poder hacer un planteamiento.

Sobre los bucles anidados este es un ejemplo sencillo:

public class test {

    public static void main (String[] Args){

        for( int i = 0; i < 2; i++)   {
            System.out.println ("BUCLE EXTERNO con i = " + i);
            for( int j = 0; j <= 4; j++){
                System.out.println ("Estamos en el bucle interno con i = "+i+" y j = " + j);
            }
        }
    }
}

Si se ejecuta se obtiene:

BUCLE EXTERNO con i = 0
Estamos en el bucle interno con i = 0 y j = 0
Estamos en el bucle interno con i = 0 y j = 1
Estamos en el bucle interno con i = 0 y j = 2
Estamos en el bucle interno con i = 0 y j = 3
Estamos en el bucle interno con i = 0 y j = 4
BUCLE EXTERNO con i = 1
Estamos en el bucle interno con i = 1 y j = 0
Estamos en el bucle interno con i = 1 y j = 1
Estamos en el bucle interno con i = 1 y j = 2
Estamos en el bucle interno con i = 1 y j = 3
Estamos en el bucle interno con i = 1 y j = 4


Un bucle define un número de repeticiones, en el ejemplo el bucle externo se repite 2 veces (con i valiendo 0 y 1). Si dentro de un bucle anidamos otro, por cada repetición del bucle externo se producen las n repeticiones que estén establecidas para el bucle interno. En este ejemplo el bucle interno define 5 repeticiones (j de 0 a 4). El resultado es que el total de iteraciones es: nº de repeticiones del bucle externo x número de repeticiones del bucle interno, en este ejemplo 2 x 5 = 10. Fíjate que hay cosas que se producen el número de veces que define el bucle externo (en este ejemplo sólo se muestra 2 veces BUCLE EXTERNO...) mientras que hay cosas que se producen i x j veces (en este ejemplo se muestran 10 veces "Estamos en el bucle...").

Un aspecto importante es la condición para terminación, no es lo mismo poner i < 2 que i<=2. En el primer caso el 2 queda excluido, y en el segundo incluido.

[nosferacento]

Una cuestión interesante es la complejidad que introduce el anidamiento de bucles. Si tenemos un bucle con n repeticiones, el ordenador tiene que realizar n procesos. La complejidad es O(n).

Si tenemos un bucle de tamaño 2 anidado sobre un bucle de tamaño 5 el ordenador tiene que realizar 10 procesos (2x5). Si el tamaño del bucle exterior es n y el del bucle interior es n también, requiere nxn procesos, es decir, n² procesos. Si tuviéramos un triple anidamiento nos iríamos a n³ y así sucesivamente.

Como puede verse el anidamiento de bucles con índice igual al tamaño del problema es poco deseable ya que provoca complejidades poco deseables. O sea, mejor evitarlo cuando tengamos otras alternativas menos costosas.

[bartvander]

En primer lugar gracias por la respuesta. estoy practicando con los bucles a ver si soy capaz de aclararme como funcionan. He creado este sencillo código:

public void bucle(){
       
        for (int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
            System.out.println(j + "zz");
            }
        }
    }

Yo entiendo que debería escribir 10 veces la secuencia del 0 al 9 acompañado de las zz, pero me escribe esto:


3zz
4zz
5zz
6zz
7zz
8zz
9zz
0zz
1zz
2zz
3zz
4zz
5zz
6zz
7zz
8zz
9zz
0zz
1zz
2zz
3zz
4zz
5zz
6zz
7zz
8zz
9zz
0zz
1zz
2zz
3zz
4zz
5zz
6zz
7zz
8zz
9zz
0zz
1zz
2zz
3zz
4zz
5zz
6zz
7zz
8zz
9zz

Cuando pongo un i muy alta no me salen todos los valores. estoy utilizando bluej

[nosferacento]

Ahí no puede haber fallo ninguno, es tal como indicas y a mí me sale sin problema. El problema tiene que ser de otro tipo, mira a hacer esto:

Ejecuta y cuando se te abra la ventana de consola vete al menú options y comprueba que tengas activadas las opciones "Clear screen at method call" y "Unlimited buffering"

Apaga el ordenador, reinicia y ejecuta otra vez.

[bartvander]

No hay nada como saber. Nosferacento, da gusto encontrarse gente como tu por el foro, sin olvidarme de javi in the sky. Sois unos cracks.

[nosferacento]

Gracias bartvander aunque ya me gustaría a mí ser un crack  ... seguimos siendo aprendices