Sarcina de a calcula statisticile ordinelor este de a găsi cel mai mic element k într-o secvență de elemente n. Această problemă este numită uneori problema găsirii statisticilor ordinale k. Când k = 1, problema se reduce la găsirea celui mai mic element al secvenței, iar pentru k = n cel mai mare element și se rezolvă nu mai mult de O (n) pași. Una dintre soluțiile evidente la problema calculului statisticilor ordinale este următoarea: ordonați secvența inițială în ordinea elementelor care nu se scad și luați elementul k. În același timp, însă, este necesar să se țină seama de cerințele problemei reale, în interesul cărora se calculează statisticile ordinelor.
În primul rând, se poate dovedi că într-o secvență ordonată, cheile mai multor elemente (k-d, (k + 1) -d.) ...] au același înțeles. Apoi, este necesar să se ia în considerare dacă astfel de elemente trebuie să se urmeze unul pe altul în aceeași ordine ca în secvența inițială sau nu este necesar. În primul caz, ordonarea secvenței inițiale trebuie efectuată printr-una din metodele de sortare stabilă, în cel de-al doilea caz poate fi utilizată orice metodă de sortare.
În al doilea rând. Sunt găsite una sau mai multe statistici ordinale? În funcție de aceasta, poate fi avantajos să se aplice un algoritm.
În al treilea rând. alegerea algoritmului este afectată de numărul de elemente n din secvența inițială.
În cele din urmă, dacă secvența originală ar trebui să rămână neschimbată, atunci pentru a găsi statisticile comenzii va fi necesar să se creeze o copie a secvenței originale sau a unui șir de chei din elementele secvenței inițiale. Utilizarea unui șir de chei poate fi benefică în cazul în care elementele secvenței inițiale au o structură complexă, iar permutările lor în timpul calculului structurilor de comandă necesită un timp considerabil. Dacă cerința de sortare stabilă nu este necesară, puteți aplica o procedură recursivă bazată pe sortarea rapidă a quarsortului, care oferă cea mai rapidă sortare medie.
Diferența dintre procedura recursivă pentru găsirea statisticilor ordinale k de la procedura de sortare rapidă a lui Hoar este că, în primul rând, după divizarea în două grupe, grupul în care este situat elementul k este selectat și, în al doilea rând, în Mai departe, numai acest grup este procesat, și nu ambele grupuri, așa cum se face în sortarea rapidă a lui Hoare.
Timpul petrecut pentru găsirea statisticilor ordinale k, fie printr-o metodă, fie prin alta, depinde de alegerea reușită a elementului suport atunci când este împărțită în grupuri. Timpul va fi minim dacă la fiecare trecere grupurile conțin aproximativ același număr de elemente. Se demonstrează că în cazul în care fiecare trecere este efectuată chiar și pe un set de 9/10 din cel precedent, timpul de execuție va fi de ordinul O (n), iar în cel mai rău caz - nu va depăși O (n 2). O metodă liniară de a găsi statistici ordinale asigură, în cel mai rău caz, timpul pentru executarea ordinului O (n). Această metodă se bazează pe căutarea unui element de susținere "bun" și se folosește pentru secvențe cu un număr mare de elemente.
Articole similare
Trimiteți-le prietenilor: