elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Complejidad Algoritmo Voraz
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Complejidad Algoritmo Voraz  (Leído 2,413 veces)
afrocardo

Desconectado Desconectado

Mensajes: 23


Ver Perfil
Complejidad Algoritmo Voraz
« en: 10 Mayo 2018, 13:41 pm »

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();
        }
    }
}


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.391


Ver Perfil
Re: Complejidad Algoritmo Voraz
« Respuesta #1 en: 10 Mayo 2018, 14:54 pm »

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)


En línea

afrocardo

Desconectado Desconectado

Mensajes: 23


Ver Perfil
Re: Complejidad Algoritmo Voraz
« Respuesta #2 en: 10 Mayo 2018, 19:19 pm »

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();
      }
   }

}
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Calculo complejidad de un algoritmo
Programación General
kasiko 3 3,054 Último mensaje 3 Marzo 2013, 01:59 am
por [Case]
Complejidad de un programa
Programación General
JonaLamper 5 3,429 Último mensaje 17 Diciembre 2015, 18:03 pm
por DarK_FirefoX
Ayuda con Algoritmo Voraz!!
Programación C/C++
piete2 1 1,773 Último mensaje 4 Abril 2016, 20:00 pm
por piete2
Complejidad o coste del algoritmo
Java
afrocardo 0 1,645 Último mensaje 12 Mayo 2018, 09:22 am
por afrocardo
Algoritmo Voraz
Java
Compila 2 6,580 Último mensaje 5 Julio 2022, 07:58 am
por Compila
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines