Mai intai trebuie sa te autentifici.
Diferente pentru problema/sdo intre reviziile #6 si #7
Nu exista diferente intre titluri.
Diferente intre continut:
h2. Exemplu table(example). |_. sdo.in |_. sdo.out |
| This is some text written on multiple lines. | This is another text written on multiple lines.
| 8 3 1 10 4 13 7 6 11 14 | 6
| h3. Explicaţie
...
Î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, se găseşte aici, şi ar trebui să obţină ... puncte. Altă soluţie(?) care sortează elementele în ordine crescătoare şi are complexitatea <tex>O(Nlog_{2}N)</tex> ar trebui să obţină ... puncte. O altă soluţie(?), 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ă ... puncte. În final, soluţia(?) 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(?). Complexitatea acestui algoritm este în medie <tex>O(N)</tex>, în cel mai defavorabil caz putând atinge <tex>O(N^2)</tex>
== include(page="template/taskfooter" task_id="sdo") ==