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.
Î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. Există şi o soluţie care garantează $O(N)$ pe cel mai defavorabil caz, care se poate găsi în Cormen la capitolul "Statistici de Ordine".
Î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. Există şi un algoritm teoretic ce garantează $O(N)$ pe cel mai defavorabil caz, care se poate găsi în Cormen la capitolul "Statistici de Ordine".
*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 am înţeles ultima frază, ar trebui să bag în loc de sursa cu pivot aleator, o sursă care alege un pivot fixat (primul număr în cazul ăsta), şi să menţionez că există şi un algoritm care garantează O(N)? *Marius* Scuze, ziceam că pe lângă sursa cu pivot aleator să mai bagi una care alege primul element ca pivot pentru a face o comparaţie. Şi decât să menţionezi că există un algoritm ce garantează O(N).
*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* 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 :)
