Există o funcție pentru numărarea inversiilor într-un matrice care necesită o perioadă O (n2):
De asemenea, există o funcție de sortare a unei matrice prin abordarea divizării și cucerire. care necesită timp O (n * log (n)):
Este necesar să se implementeze algoritmul pentru numărarea inversiilor într-un matrice cu abordarea diviziune și cucerire. care ar necesita timp O (n * log (n)).
Din păcate, este destul de dificil pentru mine să înțeleg recursiunea atunci când prima metodă numește o altă metodă, iar cealaltă cheamă prima metodă, cu condiția.
Su 16 noiembrie '14 la ora 9:24
Mai întâi trebuie să vă ocupați de tipul de îmbinare, și anume să înțelegeți ideea algoritmului și apoi să vă ocupați de inversiune.
Voi spune pe scurt: am împărțit matrice în două părți, fiecare dintre aceste părți, la rândul său, de asemenea, este împărțit în două părți, etc. În timp ce piesele noastre nu vor consta dintr-un singur element. După ruperea perechilor fuzionăm într-una, astfel încât partea rezultată a fost sortate - compara elementele de o singură piesă cu celelalte elemente, respectiv, și să le scrie în ordinea corectă în rezultat. Apoi vom relua părțile rezultate și așa mai departe. până când nu avem o parte, care va fi o matrice sortată.
Textul este greu de înțeles, așadar vă recomand să examinați demonstrația grafică (pe aceeași Wikipedia există o hifă). Când înțelegeți ideea, puteți deja să vă implicați în implementare.
Când îmbinăm ambele părți, așa cum am spus, comparăm elementele unei părți (prima, stânga) cu elementele celeilalte (dreapta, a doua) parte. Și dacă elementul din partea stângă este mai mare decât elementul din partea dreaptă, respectiv, atunci aceasta este inversiunea.
Și cum toate elementele rămase ale stângii vor fi și ele mai mari, pentru că părțile din stânga și din dreapta sunt sortate. Prin urmare, numărul de inversiuni ar trebui să fie mărit cu numărul de elemente rămase + 1 (element curent).
Indexarea este de la 0. Nu am descris că adăugăm elemente la partea care rezultă, cred că este de înțeles. Descriu doar acele părți în care există inversiuni. Erori sunt posibile, deoarece repede. Da, și au făcut atât de compact elementele, astfel încât imaginea să fie afișată complet pe hashcode.
Trimiteți-le prietenilor: