Căutați statistici ordinale

Cea de-a treia statistică a unui set cu elemente n este numită i-a în ordinea ascendentă a elementului setului.

Deci minimul setului este prima statistică ordinală, iar maximul este statistica ordinară n. Median (mediană engleză) înseamnă în mod informal mijlocul setului. Dacă n este ciudat, atunci mediana este unică și indicele său (indicele statisticilor ordinale corespondente) este i = (n + 1) / 2; dacă n este egal, atunci mediile sunt două: i = n / 2 și i = n / 2 + 1.

Formal, sarcina de căutare a statisticilor ordine este definită după cum urmează:

Dat fiind: setul constând din (diferite) numere și numărul

Este necesar să găsim: un element, mai exact alte elemente ale setului

Sarcina poate fi rezolvată într-o oră. Pentru a face acest lucru, este suficient să aranjăm elementele în ordine ascendentă și apoi să luăm elementul i. Dar există algoritmi care pot rezolva această problemă în timp, în medie și chiar și în cel mai rău caz.

Până acum, nu se știe câte comparații trebuie să facem pentru a găsi mediana. Limita inferioară, egală cu 2n prin comparație, a fost găsită de Bent și John, iar limita superioară, egală cu 3n prin comparație, este Shyonhag, Paterson și Pippenger. Dor și Zwick au îmbunătățit ambele granițe; limita superioară a acestora este puțin mai mică de 2.95n, iar fundul este puțin mai mare decât 2n.

Algoritmul pentru găsirea valorii minime și maxime

Separat, statisticile minime și maxime (prima și a noua ordine) ale setului (matricea) pot fi găsite prin compararea fiecăruia. În problemele practice, este adesea necesar să se găsească simultan atât minim cât și maxim. cu căutarea simultană, numărul de comparații poate fi redus de la comparații. Pentru a face acest lucru, trebuie să luați două elemente din set și să le comparați unul cu celălalt. Apoi elementul mai mare este comparat cu maximul curent, și mai puțin - cu minimul curent. Astfel, o comparație este salvată (3 comparații în loc de 4).

O astfel de optimizare este potrivită în cazul în care compararea elementelor din setul A necesită mult timp. De exemplu, dacă comparați text sau grafică.

Căutarea algoritmului prin liniar în timp mediu

Algoritmul se bazează pe principiul "împărți și cuceresc" și funcționează ca un fel rapid. Pentru a asigura un timp de lucru scurt pentru toate datele de intrare posibile, algoritmul introduce randomizarea. Algoritmul la sugerat lui Hoare

Ideea este de a împărți întreaga matrice în două părți, astfel încât fiecare element din prima parte să nu fie mai mare decât oricare din a doua parte. Căutarea continuă poate fi continuată numai în una dintre părți.

Funcția împarte o parte a matricei de la p la al elementului q în două părți mai mici.

Funcție Același lucru, dar face randomizare în dol.

Căutarea statisticilor k în tabelul A este efectuată de către funcție

Analiza algoritmului

În cel mai bun caz (sub condiția de divizare în părți egale), timpul de căutare este descris de ecuația:

Timpul mediu este de asemenea acolo, iar din cauza randomizării, viteza de funcționare la o intrare arbitrară este apropiată de media. Dacă partiția nu este aleasă rău, în cel mai rău caz va fi complexitatea

Algoritmul de căutare liniară în timp (algoritmul BFPRT)

Numit după inventatorii săi: Manual B lum, Robert W. Floyd, Vaughan R. P ratt, Ronald L. R ivest și Robert Endre T arjan. De asemenea, limba engleză cunoscută ca algoritmul median al mediilor

Algoritmul funcționează ca cel precedent, dar garantează o bună partiționare și, prin urmare, cel mai rău caz O (n).

Algoritmul de căutare al statisticilor ordinale k efectuează următorii pași:

Dacă matricea de intrare conține doar un element, atunci returnați acest element și ieșiți.
Toate elementele matricei sunt împărțite în grupuri de câte 5 elemente fiecare și un grup cu elementele (poate fi gol).
Fiecare grup este ordonat după metoda de includere și în fiecare grup este selectat un median.
Prin invocarea recursivă a algoritmului este mediana setului de medii găsite în pasul 3 (dacă mediana este de două, atunci este selectată partea de jos).
Folosind o versiune modificată a procedurii, matricea de intrare este divizată relativ la mediană. Să presupunem că numărul este mai mult decât numărul elementelor din prima parte.
Dacă valoarea este returnată. În caz contrar, algoritmul se numește recursiv, pentru prima parte, dacă pentru al doilea dacă (este înlocuit cu).

Analiza muncii

Timpul de a comanda toate părțile mici ale matricei și timpul la o matrice prietenoasă este O (n). Alegerea elementului partiției x asigură că nu intră mai mult de 7n / 10 + 6 elemente în partea mai mare. În consecință, ecuația pentru timpul de lucru este:

Articole similare

Pagina anterioară

Pagina următoare