În exemplu, se observă că elementele aranjate în ordine crescătoare sunt: $1 4 **6** 7 10 11 13 14$, prin urmare al 3-lea cel mai mic element este 6.
O primă soluţie(?), care numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de <tex>O(N^2)</tex>, şi ar trebui să obţină ... puncte.
O primă 'soluţie':job_detail/370055?action=view-source, care numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de <tex>O(N^2)</tex>, şi ar trebui să obţină $20$ puncte.
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ă 70 puncte.
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ă 70 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ă $70$ puncte.
În final, 'soluţia':job_detail/369692?action=view-source care ar trebui să obţină $100$ de puncte foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $K$-a statistică de ordine. Practic, acest algoritm este foarte asemănător quicksort-ului, doar că în loc să se sorteze tot şirul se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Acest algoritm este implementat şi în STL, funcţia 'nth_element':http://cplusplus.com/reference/algorithm/nth_element/ găsindu-se în headerul 'algorithm':http://cplusplus.com/reference/algorithm/. O sursă demonstrativă se găseşte 'aici':job_detail/369659?action=view-source. Complexitatea acestui algoritm este în medie <tex>O(N)</tex>, însă teoretic în cel mai defavorabil caz poate atinge <tex>O(N^2)</tex> pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. Dar deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz.
*Marius* Nu ar fi mai bine ca O(N^2^) 20p, O(N logN) 50p, O(N logK) 60-70, O(N) 100? Când atinge O(N^2^) algoritmul O(N)?
*Marius* Nu ar fi mai bine ca O(N^2^) 20p, O(N logN) 50p, O(N logK) 60-70, O(N) 100? [done] Când atinge O(N^2^) algoritmul O(N)?
*Paul:* Parca am citit pe undeva ca $nth_element$ din STL are complexitatea worst case $O(NlogN)$. E si suspect sa mearga sort-ul worst case $O(NlogN)$ si statisticile de ordine $O(N^2)$. Verifica acest fapt.
*Mishu:* "Timpul de execuţie, în cazul cel mai defavorabil este $O(N^2^)$, pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. [...] Deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz." -> Cormen. De aici, probabil se trage faptul că în cel mai defavorabil caz complexitatea se aproximează $O(NlogN)$. Cât despre soluţii, am să modific unele teste astfel încât soluţia în $O(NlogN)$ să ruleze mai slab decât cea în $O(NlogK)$.
