De ceva vreme am obsevat cu totii ca nu prea exista activitate pe forum si ma gandeam sa introducem poate o sectiune numita Problema zilei care ar consta in propunerea unei mici probleme de algoritmica. In functie de caracteristicle datelor de intrare se pot discuta solutii cat mai bune. Pot sa incep eu cu urmatoarea problema:

Se dau doua siruri de numere naturale A, B si un numar S. Sa se determine toate combinatiile de 2 numere, unul din A si altul din B, astfel incat suma lor sa fie S. Care e cea mai mica complexitate care se poate obtine?

Edit:
A si B contin numere in ordine aleatoare

Ok ii dau o incercare. Pai am putea lua primul sir de numere A si le-am compara cu S. Tot ce este mai mic sau egal trece primul test. Apoi am face acelasi lucru si cu sirul B. Pentru fiecare numar din sirul A care a trecut testul facem adunarea cu fiecare numar din sirul B care a trecut testul iar atunci cand rezultatul este egal cu S avem o pereche de numere care satisface cerintele.

Ce zici de complexitatea solutiei tale? Eu afirm ca este de ordinul lui O(N*M) unde N este lungimea primului sir si M este lungimea celui de-al doilea.
Cu siguranta se poate si mai bine, cine poate gasi O(N logM)?

Se parcurge fiecare sir si se contruieste cate un arbore binar cu valorile ordonate, in cazul primului sir de la mare la mic, in cazul celui de-al doilea, ordonate de la mic la mare (pt. acelasi tip de parcurgere). Se adauga doar valorile < suma.

Se parcurge apoi primul arbore si pt. fiecare valoare se parcurge arborele 2, oprindu-se in cazul arborelui 2 cand suma este mai mare decat targetul.

In cazul cel mai defavorabil toate valorile sunt mai mici ca suma. Constructia celor doi arbori are complexitatea O(NlogN + MlogM).

Consideram sirurile sortate:

A: 50 40 30 20 10
B: 10 20 40 60 90

si S = 120

Incepem cu 50 si cautam in al doilea sir, ne oprim abia la sfarsitul celui de-al doilea sir. Incepem cu 40 si ne oprim tot la sfarsitul celui de-al doilea sir. Acesta este un exemplu extrem, pentru ca in practica am face mult mai putine operatii. Totusi complexitatea finala este T2(N,M) = O(NlogN + MlogM + O(N*M)) care desi pare mai mare decat T1(N,M)=O(N*M) este mai buna in practica datorita constantei ascunse din fata lui O(N*M) din T2.

In concluzie, ideea cautarii intr-o entitate sortata e buna...

Acuma orice algoritm din asta isi are inamicul, inclusiv grozavul quicksort.

Idea oricum asta e, sa nu treci de 2 ori peste valorile care nu pot face suma.

Se pot de ex. crea X "galeti" si pus in fiecare valorile [Sum/X * (n-1), Sum/X * n), n apartine [1..x] in fiecare astfel de galeata. Aici caz extrem ar fi ca toate valorile sa fie in aceeasi galeata.

Pe de alta parte, cu binary tree, dupa prima cautare in arborele 2, poti mentine pointeri la "marginile" ferestrei de cautare pe care o largesti/translatezi cu fiecare noua iteratie din primul arbore. Nu e musai ca arborele secund sa fie parcurs in intregime sau pana se indeplineste conditia de > Sum.

Solutia cred ca e mult mai simpla. Sortam vectorul B si procedam astfel:



Complexitate sortare B: O(MlogM), complexitate algoritm max(O(NlogM), O(MlogM)).

Corect, insa daca is ambele ordonate poti folosi proprietatea ca odata o valoare gasita in B sau conditia de terminare atinsa, valoarea urmatoare trebuie sa fie in preajma acelei pozitii. Se reduce drastic timpul de cautare in B cu compromisul adaosului timpului necesar crearii arborelui A.
Pt. fiecare valoare din A se cauta mult mai putine valori in B decat prin parcurgerea unui intreg arbore binar.

Nu te cred, demonstreaza-mi! Asa mi-a zis un profesor din comisia de licenta cand ii spuneam eu ca din scena nu lipseste nici macar un poligon . Dar referitor la ce spui tu, cam ce complexitate obtii?

Ce fel de poligon era? Adica din ce ti-ai dat tu licenta? Suna interesant. Omul are dreptate oarecum pentru ca una e in teorie si alta, pe masurate, in practica.

E complicat de estimat ordinul pt. solutia mea, probabil ca e mai lenta totusi decat solutia ta, mai ales ca navigarea pe arbore presupune sau recursivitate sau memorie multa initializata la fiecare parcurgere. Ar trebui masurat insa .

Era vorba de calcularea seturilor PVS(pentru rasterizarea interioarelor ), si eu spuneam ca oricum ai privi fiecare set PVS e calculat corect. Iar proful amuzat probabil de entuziasmul meu mi-a spus zambind: Nu te cred! Demonstreaz-mi! Din fericire n-am izbucnit in ras. Licenta avea titlul: Tehnici de partitionare spatiala

Sa nu imi zici ca exista in Romania facultati serioase cu ore de grafica 3D !?

Hmm, depinde ce intelegi prin serios.. la cursul de grafica din anul 3 am facut destule chestii interesante

presupun ca se pot pune orice fel de probleme
ca mai aveam pe acasa diverse teste cerute pe la interviuri etc
poate nu uit sa pun una cand ajung acasa sa vad ce zice lumea

Un prieten de-ai mei a primit urmatoarea problema la un test de programare pe C#(a primit o parte de algoritmica si o parte de C#). Se da o matrice de m x n cu valori intregi(fiecare linie si coloana sunt sortate crescator) si o valoare x. Sa se determine daca x apartine matricii sau nu. Cu siguranta se cauta ceva mai bun decat O(N*M) (adica doua for-uri imbricate ).

Exemplu de matrice:

1 2 3 4 5
2 3 4 5 6
3 4 5 6 7

Atentie: se cauta doar existenta unui element nu toate pozitiile pe care apare. E destul de interesanta problema, poate putin prea complicata pentru incepatori dar merita incercata .