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:
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)
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)