Selles õpetuses saate teada, kuidas jagamise ja vallutamise algoritm töötab. Rekursiivse probleemi lahendamiseks võrdleme ka jagamise ja vallutamise lähenemist teiste lähenemisviisidega.
Jaga ja valitse algoritm on strateegia lahendada suur probleem
- probleemi jaotamine väiksemateks alamprobleemideks
- alamprobleemide lahendamine ja
- ühendades need soovitud väljundi saamiseks.
Jagamise ja vallutamise algoritmi kasutamiseks kasutatakse rekursiooni . Lisateave rekursiooni kohta erinevates programmeerimiskeeltes:
- Rekursioon Java keeles
- Rekursioon Pythonis
- Rekursioon C ++ keeles
Kuidas algoritme jagada ja vallutada?
Siin on etapid:
- Jaga : jagage antud probleem rekursiooni abil alamprobleemideks.
- Valluta : lahendage väiksemad alamprobleemid rekursiivselt. Kui alaprobleem on piisavalt väike, siis lahendage see otse.
- Kombineeri: tegeliku probleemi lahendamiseks kombineerige rekursiivses protsessis osalevate alamprobleemide lahendused.
Mõistame seda mõistet näite abil.
Siin sorteerime massiivi jagamise ja vallutamise lähenemisviisi abil (st. Ühendamise sort).
- Olgu antud massiiv:
massiivi ühendamise sortimiseks - Jagage massiiv kaheks pooleks.
Jagage massiiv kaheks alamrubriigiks
Jällegi jagage iga alamrühm rekursiivselt kaheks pooleks, kuni saate üksikud elemendid.
Jagage massiiv väiksemateks alamrühmadeks - Nüüd ühendage üksikud elemendid järjestatud viisil. Siin lähevad vallutamise ja kombineerimise sammud kõrvuti.
Ühendage alamrubriigid
Aja keerukus
Jagamise ja vallutamise algoritmi keerukus arvutatakse põhiteoreemi abil.
T (n) = aT (n / b) + f (n), kus, n = sisendi suurus a = rekursioonis olevate alamprobleemide arv n / b = iga alamprobleemi suurus. Eeldatakse, et kõigil alamprobleemidel on sama suurus. f (n) = väljaspool rekursiivset kõnet tehtud töö maksumus, mis sisaldab probleemi jagamise ja lahenduste ühendamise kulu
Võtame näite rekursiivse probleemi ajalise keerukuse leidmiseks.
Ühendamissordi jaoks võib võrrandi kirjutada järgmiselt:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) kus a = 2 (iga kord on probleem jaotatud kaheks alamprobleemiks) n / b = n / 2 (iga alamülesande suurus on pool sisendist) f (n) = aeg, mis kulub probleemi jagamiseks ja alaprobleemide liitmiseks T (n / 2) = O (n log n) (Selle mõistmiseks vaadake palun põhiteoreem.) Nüüd on T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Jagage ja vallutage Vs-dünaamiline lähenemine
Jaga ja võida lähenemine jagab probleemi väiksemateks alamprobleemideks; neid alamprobleeme lahendatakse edasi rekursiivselt. Iga alamprobleemi tulemust ei salvestata edaspidiseks kasutamiseks, samas kui dünaamilises lähenemises salvestatakse iga alamprobleemi tulemus edaspidiseks kasutamiseks.
Kasutage jagamise ja vallutamise lähenemist, kui sama alamprobleemi ei lahendata mitu korda. Kasutage dünaamilist lähenemist, kui alamprobleemi tulemust tuleb tulevikus mitu korda kasutada.
Mõistame seda ühe näitega. Oletame, et proovime leida Fibonacci sarja. Siis,
Jaga ja võida lähenemine:
fib (n) Kui n <2, tagastab 1 muu, tagastab f (n - 1) + f (n -2)
Dünaamiline lähenemine:
mem = () fib (n) Kui n mälus: tagastage mem (n) muu, kui n <2, f = 1 muu, f = f (n - 1) + f (n -2) mem (n) = f tagastus f
Dünaamilises lähenemises salvestab mem iga alamprobleemi tulemuse.
Jaga ja võida algoritmi eelised
- Naiivse meetodi abil on kahe maatriksi korrutamise keerukus O (n 3 ), jagamise ja vallutamise lähenemisviisi (st Strasseni maatriksi korrutamine) kasutades O (n 2,8074 ). Selline lähenemine lihtsustab ka muid probleeme, näiteks Hanoi torn.
- See lähenemine sobib mitmetöötlussüsteemide jaoks.
- See kasutab tõhusalt mälu vahemälusid.
Jagage ja vallutage rakendusi
- Binaarotsing
- Ühenda sortimine
- Kiire sortimine
- Strasseni maatriksi korrutamine
- Karatsuba algoritm
