Nopea Shell-algoritmi

Nopea rungon  algoritmi on algoritmi kuperan rungon rakentamiseksi tasolle. Käyttää Hoaren ideaa pikalajittelusta

Kuvaus

Pistejoukko on jaettu kahteen osajoukkoon, joista jokainen sisältää yhden katkoviivan, joiden liitos antaa kuperan rungon monikulmion.

  1. Otetaan kaksi joukon S ääripistettä - vasen L ja oikea P. Piirretään niiden läpi suora viiva. Merkitään S1:llä pisteiden osajoukko, joka sijaitsee pisteiden A ja P kautta kulkevan suoran yläpuolella tai sen kautta, ja S2:lla alajoukkoa, joka sijaitsee samalla viivalla tai alapuolella.
  2. Tarkastellaan ylempää osajoukkoa S1. Valitsemme pisteen Pi, jolla on suurin etäisyys suorasta LP (kolmiolla LPiP on suurin pinta-ala). Jos tällaisia ​​pisteitä on useita, valitaan se, jolla on suurin kulma PiLP. Piste Pi on joukon kuperan rungon kärki. Todellakin, jos pisteen Pi kautta vedetään suoran LP yhdensuuntainen suora, niin tämän suoran yläpuolella ei ole yhtäkään joukon S pistettä. On mahdollista, että konstruoidulla suoralla on muita pisteitä, mutta tehdyn valinnan mukaan Pi on niistä vasemmanpuoleisin. Että. Pistettä Pi ei voi esittää joukon S kahden muun pisteen kuperalla yhdistelmällä. Muodostetaan suorat LPi ja PiP. Molempien viivojen oikealla puolella olevat pisteet voidaan jättää tarkastelun ulkopuolelle, koska ne ovat kolmion LPiP sisäpisteitä, eli ne eivät kuulu CH(S), kuperan rungon rajaan.
  3. Tarkastellaan nyt suoran ЛPi vasemmalla puolella tai sillä olevaa pisteiden S11 osajoukkoa ja suoran PiП vasemmalla puolella tai sen päällä olevaa pisteiden osajoukkoa S12. Jokaiselle osajoukolle rakennetaan kupera runko. Joukon S1 kupera runko muodostetaan liimaamalla yhteen järjestetyt kärkilistat CH(S11) ja CH(S12).
  4. Ratkaisemme S2:n ongelman.

Algoritmin monimutkaisuus

Algoritmin monimutkaisuus koostuu tarkasteltavan joukon O(N) kahden osajoukon muodostamisen monimutkaisuudesta ja kunkin osajoukon aliongelmien ratkaisemisen monimutkaisuudesta: T(N) = T(a) + T(b) + O( N).

Parhaassa tapauksessa, kun tehtävä on jaettu kahteen yhtä voimakkaaseen osatehtävään, algoritmin monimutkaisuus on rekursiivisen yhtälön ratkaisu:

(1) T(N) = 2 T(N/2) + O(N) =>

(2) T(N) = O(N log N).

Pahimmillaan:

(3) T(N) = T(1) + T(N1) + O(N) =>

(4) T(N) = O(N^2).

Lemma Yhtälön (1) ratkaisu on funktio (2) Olkoon N = 2k. Sitten T(2k) = 2 T(2k 1) + C 2k; T(2k 1) = 2 T(2k 2) + C 2k 1 => T(2k) = 4 T(2k 2) + 2 °C 2k 1 + С 2k = 4 T(2k 2) + 2 °C 2k => T(2k) = 2m T(2k m) + m C 2k Jos m = k (= logN), algoritmi päättyy: T(N) = NT(1) + C logN N = O(N logN)

Katso myös

Linkit