1

La idea es que este código tenga un costo algorítmico menor a n^3, sin recurrir a estructuras de datos fuera de arreglos simples (o matrices), además sin asumir ningún tipo de límite o rango en el tamaño.

El propósito del código es encontrar Tripletas de números tal que a[i] - a[j] - a[k] = 0. Es importante que la posición [i] > [j] > [k] (posicionalmente) . Además se deben tomar en cuenta aquellas posibles Tripletas repetidas, siempre y cuando las posiciones sean distintas

Aquí un ejemplo: tamaño del vector:10

Vector: 5 5 7 8 2 7 1 9 1 1

Tripletas: (8-7-1) (8-7-1) (8-7-1) (2-1-1) (2-1-1) (2-1-1)

Tripletas:6

public int getCount(){
    int n = this.enteros.length;
    int size = (n-1)*(n-2)/2;
    int combinaciones[] = new int[size];
    int index = 0;      
    int count = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n-1; j++) {
            combinaciones[index] = enteros[i] - enteros[j];
            index++;
        }
    }
        
    int inicial = 2;
    int kte = 2;
        
    for(int c = 0; c < combinaciones.length; c++) {
        for(int k = inicial; k < n; k++) {
            if(combinaciones[c] > 0 && combinaciones[c] == enteros[k]) {
                count++;
            }
        }
            
        inicial++;

        if(inicial == n) {
            kte++;
            inicial = kte;
        }
    }

    return count;
}
1

1 respuesta 1

0

No es posible que el orden de complejidad temporal sea menor a O(n3)

¿Por qué?

Porque si o si requieres comprobar todas las combinaciones posibles, no puedes conocer todas las tripletas si es que no evalúas las combinaciones, por lo que es un ejercicio de combinatoria, donde la fórmula es:

introducir la descripción de la imagen aquí

Donde n es la cantidad de números en el array y el resultado es la cantidad de iteraciones necesarias. Si la formula se simplifica, eliminando constantes para obtener la notación Big O, se puede ver facilmente que es O(n3)

Es importante aclarar que la complejidad temporal es una cota superior a la cantidad de iteraciones. Es decir, la cantidad real de iteraciones siempre es menor y que es un indicador cualitativo, por estas razones es posible eliminar constantes o que por ejemplo n(n-1) sea simplemente O(n2). La idea es que cuando n crece mucho se va acercando a O(n3)

introducir la descripción de la imagen aquí

En azul está graficada la función n3 y en verde n(n−1)(n−2)/6


Otra forma de pensarlo es simplificando el ejercicio

  • De una lista de largo n, necesito encontrar TODOS los números iguales a cero -> Si o si debo recorrer toda la lista O(n)
  • De una lista de largo n, necesito encontrar TODOS los pares de números que su resta de igual a cero, si o si debo comprobar el primero con el segundo, el primero con el tercero y así sucesivamente, y luego lo mismo con el segundo y el tercero...etc entonces es O(n2)
  • Por lo que ya es evidente que, si busco una tripleta que su resta de cero, es de O(n3)

Cabe aclarar que el orden temporal es un indicador cualitativo, y sirve en general para tener una claridad de que pasará cuando la cantidad de muestras crece. Pero que de todas maneras existen técnicas para mejorar el algoritmo sin mejorar la complejidad temporal

Por ejemplo:

Voy a usar javascript, para poder utilizar el snippet de SO y se pueda ver el resultado. Porque lo importante en esta pregunta es el algoritmo no el lenguaje

El siguiente código muestra la cantidad de tripletas y la cantidad de iteraciones realizadas

const lista = [5,5,7,8,2,7,1,9,1,1];
let tripletas = 0;
let iteraciones = 0;

for(let i = 0; i<lista.length-2; i++){
  for(let j=i+1; j<lista.length-1; j++){
    for(let k=j+1; k<lista.length; k++){
        if(lista[i] - lista[j] - lista[k] === 0){
          tripletas++;
        }
        iteraciones++
    }
  }
}
console.log("Tripletas encontradas:", tripletas)
console.log("Iteraciones realizadas:", iteraciones)

Dado que señalaste que son solo números positivos, si la resta de los 2 primeros números es igual o menor a cero es imposible que la resta de un tercer número positivo de como resultado cero. Por lo que usando un if para evaluar dicha condición antes de entrar al tercer if provoca una disminución en la cantidad de iteraciones, mejorando el algoritmo, pero sin mejorar la complejidad temporal

const lista = [5,5,7,8,2,7,1,9,1,1];
let tripletas = 0;
let iteraciones = 0;

for(let i = 0; i<lista.length-2; i++){
  for(let j=i+1; j<lista.length-1; j++){
    let resta = lista[i] - lista[j];
    
    if(resta<=0){ // agregamos una condición para evitar evaluar el tercer for, cuando es imposible que la resta de cero
     iteraciones++
     continue;
    }
    
    for(let k=j+1; k<lista.length; k++){
        if(resta - lista[k] === 0){
          tripletas++;
        }
        iteraciones++
    }
  }
}
console.log("Tripletas encontradas:", tripletas)
console.log("Iteraciones realizadas:", iteraciones)

5
  • Y usando un hashmap?
    – Japv
    Commented el 21 sept. a las 17:12
  • Usando un hashmap para guardar las diferencias y después comprobar con un ciclo si existen elementos en el arreglo iguales a esas diferencias se reduce a orden cuadratico, ese tercer ciclo seria de orden lineal y no estaría anidado con los otros dos
    – Japv
    Commented el 21 sept. a las 17:20
  • @Japv igual necesitas preservar el orden. Yo creo que si sería útil para llevar la cuenta de cada número y quitar aquellos que aparezcan más de 2 veces en el arreglo.
    – Mateo
    Commented el 21 sept. a las 22:34
  • Yo creo que se podría sacar más jugo si se paralelizara el algoritmo. Y no hablo solamente de hilos. De hecho, sería interesante verlo correr en una GPU
    – Mateo
    Commented el 21 sept. a las 22:36
  • @Japv Leí los comentarios que habían puesto, y la verdad no se me ocurre como hacerlo con un hashmap, porque guardar la diferencia puede ser un camino ¿pero qué pasa cuando un par de números distintos tiene la misma diferencia?.- Pero lo que me animó a responder, es que el OP restringe la pregunta a usar solo arrays, por lo que el ejercicio se transforma a uno de combinatoria pura, y por esa razón me aventuro a señalar que no es posible bajar el orden temporal
    – Yussef
    Commented el 22 sept. a las 1:38

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.