Problema interesanta triunghi dreptunghic

[•Doru_AC]

Salutare,

Sa presupunem ca avem N betisoare. Cum construiesc un algoritm mai eficient decat O(N^3)  care determina daca printre cele N betisoare exista o combinatie de trei betisoare care formeaza un triunghi dreptunghic ?
Lungimea betisoarelor se presupune cunoscuta.

Multumesc

[•MciprianM]

Poti sa sortezi betisoarele dupa lungimea lor, iei perechi de cate doua betisoare (sa zicem ca astea ar fi catetele) si pentru fiecare pereche, verifici daca exista un betisor cu lungimea egala cu lungimea ipotenuzei(lungimea ipotenuzei o determini cu teorema lui Pitagora). Verificarea o faci cautand binar lungimea catetei in sirul sortat de betisoare. Complexitate: O(n^2 logn).
Cu hashuri poti sa obtii un timp mediu de O(n^2).

[•klamathix]

Poti obtine O(n ^ 2) curat, worst-case. Ideea e ca pentru o cateta i fixata, cu cat cresti lungimea catetei j creste si ipotenuza, deci in loc sa faci cautare binara de fiecare data doar cresti un iterator care in total trece prin maxim toate n elemente.

[•Doru_AC]

Foarte tare. Cum mai putin de O(n^2) nu se poate, e perfect. Multumesc  

L.E. Am incercat sa o implementez in O(n^2) insa nu cred ca se poate fara cautare binara. Poti sa dai mai multe detalii in legatura cu iteratorul pe care il incrementez?

[•savim]

Uite mai explicit. Sortezi initial cele N valori in N log N.

Apoi, iti fixezi ipotenuza -> O(n).
Iti fixezi o cateta -> pana acum ai O(n^2).
A treia cateta stii cu cat este egala (stii ipotenuza si o cateta), deci ce ramane de facut este sa verifici daca valoarea se afla in sirul tau.
Poti face asta cautand binar in log N.
Dar - daca ai ipotenuza fixata, si valoarea primei catete creste, valoarea celei de-a doua catete va scadea.

Cu alte cuvinte, daca ai sirul X1 < X2 < .. < Xn, si presupunem ca ai gasit tripletul ipotenuza,cateta,cateta = Xi,Xj,Xk. Daca vei alege o cateta Xj+x, a doua cateta poate fi aleasa doar in stanga lui k, adica Xk-y. Ideea e sa-ti tii un pointer care initial arata spre cel mai mare element, si atata timp cat valoarea spre care pointeaza e mai mare decat ce ai tu nevoie, sa-l decrementezi. Iese O(N^2) per total, sper ca ai inteles.

[•Doru_AC]

L-am implementat. Multumesc mult pentru explicatii.