Altă 'soluţie':job_detail/369661?action=view-source care sortează elementele în ordine crescătoare şi are complexitatea <tex>O(Nlog_{2}N)</tex> ar trebui să obţină $50$ puncte.

O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex>O(Nlog_{2}K)</tex>, care foloseşte un heap pentru a menţine cele mai mici $K$ elemente ar trebui să obţină $60$ puncte. O 'soluţie':job_detail/371237?action=view-source care obţine tot $60$ de puncte este cea de complexitate <tex>O(N+Klog_{2}K)</tex>. Deşi complexitatea este teoretic mai bună, ea se comportă mai slab decât cea menţionată anterior, datorită folosirii unei structuri de date destul de înceată, $priority_queue$.

O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex>O(Nlog_{2}K)</tex>, care foloseşte un heap pentru a menţine cele mai mici $K$ elemente ar trebui să obţină $60$ puncte. O 'soluţie':job_detail/371237?action=view-source care obţine tot $60$ de puncte este cea de complexitate <tex>O(N+Klog_{2}K)</tex>. Deşi complexitatea este teoretic mai bună, ea se comportă mai slab decât cea menţionată anterior, datorită folosirii unei structuri care rulează mai încet, $priority_queue$.

O 'soluţie':job_detail/371166 care sortează elementele în timp aproape liniar, folosind radix sort ar trebui să obţină în jur de $70$ de puncte.

*Marius* Ideal ar fi ca O(N^2^) *10*, O(N*K) *20*, O(N logN) 40, O(N logK) 50, O(N+KlogK) 60, *O(N) cu radix sort* 70, O(N) 100. Am vorbit cu Paul şi am ajuns la concluzia că implementat de mână ca în Cormen avem worst case O(N^2), însă cu STL worst case e O(N logN) deoarece... aici mă mai gândesc, dar tind să cred că se bazează pe introsortul lui QuickSort. Algoritm O(N) de selecţie este cel cu împărţire în bucăţi de câte 5 elemente, însă, în practică, se comportă mai prost decât cel care alege un pivot aleator. Eu zic să bagi o sursă care nu alege un pivot aleator (ci pe primul) pentru comparaţie cu cea care alege pivotul aleator şi să zici decât că există acest algoritm teoretic cu cu ordinul de execuţie O(N) (şi nu O(N) în medie). Nu mă gândeam că ies atâtea surse. :)
*Mishu* Nu este cam mare diferenţa între O(N + K) si O(N). În plus, atât soluţia în O(N^2^), cât şi cea în O(N*K) sunt cam bulăneli, cred că este cam mică diferenţa (10 puncte) între O(N*K) si O(NlogN). *Marius* Am rectificat punctajele în 10 şi 20 pentru O(N^2^) şi O(N*K). Nu e mare diferenţa între O(N) cu radix sort şi O(N) cu statistici, pentru că radix sort consumă şi memorie şi timp. Nu sunt bulăneli, pentru că obţii rezultatul corect întotdeauna. :P

*Mishu* Am încercat şi soluţia cu pivot fixat (primul element), dar datorită faptului că testele sunt generate random, se comportă aproximativ la fel cu celelalte soluţii în $O(N)$. Să o mai menţionez printre surse?

*Mishu* Mie mi-a mers mai repede soluţia în O(NlogK) decât cea în O(N + KlogK), proabil din cauza priority_queue-ului, care din ce am văzut este destul de încet. De aceea propun modificarea puţin a punctajelor, O(N^2^) 10 O(N*K) 20 O(NlogN) 50 O(NlogK) 60 O(N) cu radix sort 70, O(N) 100 :) *Marius* Era de aşteptat să fie greu de departajat. Poate cu seturi ar fi mers mai repede. Dar dacă tot ai implementat-o să o menţionezi pe undeva, măcar ca idee. :)
Am menţionat-o ca idee, cu seturi merge chiar mai slab, pentru că set-urile sparg des linia de cache, prin urmare se lucrează mai încet cu ele. :)