Question

Este algoritmul destul de eficient din punct de vedere al memoriei si al timpului de executie?
Daca da, de ce?
Daca nu, cum poate fi schimbat ca sa devina mai eficient?

Answer 1

Problema poate fi redusa la urmatoarea cerinta: gaseste doi termeni consecutivi in al doilea sir care pot sa cuprinda primul sir: adica un termen sa fie mai mic decat cel mai mic termen al primului sir, iar termenul consecutiv sa fie mai mare decat cel mai mare termen din primul sir.
Asta face algoritmul tau si este cel mai eficient din punct de vedere al memoriei si vitezei de executie.
Este eficient din punct de vedere al memoriei pentru ca nu folosesti doi vectori pentru a memora datele respective, ci folosesti cate 2 variabile in cadrul fiecarui sir: variabilele minim,maxim pentru primul sir, si variabilele x,y pentru al doilea sir. Presupunand ca lungimile celor doua siruri ar fi de ordinul miilor, exemplu: n=10000 m=10000 si ai declara vectorii de date de tip int, ti-ar trebui vectori de zeci de mii de pozitii de tip int. Fiecare data de tip int ocupa 2B(bytes) adica 16 biti pe sistemele vechi, sau 4B pe sistemele noi(cele de la 32 de biti in sus) Asta inseamna ca ti-ar trebui o memorie de nivelul kB pentru a acoperi acele date. In schimb tu ai folosit 4 variabile de tip  int, adica maximum 16B.

Algoritmul este cel mai rapid pentru ca citeste o singura data ambele siruri de date si le proceseaza o data, ceea ce inseamna ca are rapiditate O(n) unde n este lungimea sirului. Mai mult, citesti doar primul sir o data. Pe al doilea sir il citesti doar pana la intalnirea celor 2 pozitii consecutive care reprezinta solutia, deci are rapiditate de executie O(n+m-i) unde m-i este diferenta de sir pe care nu o citesti pentru ca deja ai gasit solutia. Daca este imposibil, atunci valoarea lui i=0, si executia devine O(n+m) cat trebuie pentru citirea ambelor siruri.

Felicitari pentru solutie.