Complejidad Algoritmo Voraz

Iniciado por afrocardo, 10 Mayo 2018, 13:41 PM

0 Miembros y 1 Visitante están viendo este tema.

afrocardo

Qué complejidad tiene este algoritmo????

package the.trip.pkg2007;

import java.util.Arrays;
import java.util.Scanner;


public class TheTrip2007 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num;

        while ((num = in.nextInt()) != 0) {
            int[] arr = new int[num];
            for (int i = 0; i < num; i++) {
                arr = in.nextInt();
            }

            Arrays.sort(arr);

            int ans = 1;
            for (int j = 1, i = 1; i < num; i++) {
                if (arr == arr[i - 1]) {
                    j++;
                } else {
                    j = 1;
                }
                ans = Math.max(ans, j);
            }
            System.out.println(ans);

            for (int i = 0; i < ans; i++) {
                System.out.print(arr);
                for (int j = i + ans; j < num; j += ans) {
                    System.out.print(" " + arr[j]);
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}

Serapis

A grandes rasgos... tienes varios bucles anidados (con profundidad de 2, más de 1 vez aunque con diferente cantidad) y una llamada a un 'array.sort', así que probablemente ronde a partir de O(4n^2)

afrocardo

La operaciones elementales de cada línea de código estarían bien?????????

import java.util.Arrays;
import java.util.Scanner;


public class Main {
   public static void main(String[] args) {

      Scanner entrada = new Scanner(System.in);
      int numero;                                                                                       // 1OE

      while ((numero = entrada.nextInt()) != 0) {                                // 1OE

         int[] array = new int[numero];                                // 1OE
                                       

         // For que va metiendo mochilas por teclado en el array.
         for (int i = 0; i < numero; i++) {                            //1 OE
            array = entrada.nextInt();                             // 1OE
         }

         Arrays.sort(array);                                         // 1OE
                              
         
         int resultado = 1;                                // 1OE

         for (int j = 1, i = 1; i < numero; i++) {                              // 1OE
            if (array == array[i - 1]) {                                 // 1OE
               j++;                                   // 1OE      
            } else {
               j = 1;                            // 1OE
            }
            resultado = Math.max(resultado, j);                      // 2OE

         }
         System.out.println("result" + resultado);                               // 1OE
                                          

         for (int i = 0; i < resultado; i++) {                                     //1OE
            System.out.print(array);                                       //1OE
            for (int j = i + resultado; j < numero; j += resultado) {     //1OE
               System.out.print(" "+array[j]);                                  //1OE
            }   
            System.out.println();
         }
         System.out.println();
      }
   }

}