Šajā apmācībā jūs uzzināsiet, kā darbojas sadalīšanas un iekarošanas algoritms. Mēs arī salīdzināsim sadalīšanas un iekarošanas pieeju salīdzinājumā ar citām pieejām, lai atrisinātu rekursīvu problēmu.
Skaldi un valdi algoritms ir stratēģija, kā atrisināt lielu problēmu
- sadalot problēmu mazākās apakšproblēmās
- apakšu problēmu risināšana un
- tos apvienojot, lai iegūtu vēlamo rezultātu.
Lai izmantotu dalīšanas un iekarošanas algoritmu, tiek izmantota rekursija . Uzziniet par rekursiju dažādās programmēšanas valodās:
- Rekursija Java valodā
- Rekursija Python
- Rekursija C ++
Kā darbojas algoritmu sadalīšana un iekarošana?
Šeit ir iesaistītās darbības:
- Dalīt : sadaliet doto problēmu apakšproblēmās, izmantojot rekursiju.
- Iekarot : rekursīvi atrisiniet mazākās apakšproblēmas. Ja apakšproblēma ir pietiekami maza, tad atrisiniet to tieši.
- Apvienot: apvienojiet apakšproblēmu risinājumus, kas ir daļa no rekursīvā procesa, lai atrisinātu faktisko problēmu.
Ļaujiet mums saprast šo jēdzienu ar piemēra palīdzību.
Šeit mēs kārtosim masīvu, izmantojot dalīšanas un iekarošanas pieeju (ti, apvienošanas kārtojumu).
- Ļaujiet dotajam masīvam būt:
Masīvs apvienošanas kārtošanai - Sadaliet masīvu divās pusēs.
Sadaliet masīvu divās apakšdaļās
Atkal sadaliet katru apakšdaļu rekursīvi divās pusēs, līdz iegūstat atsevišķus elementus.
Sadaliet masīvu mazākās apakšdaļās - Tagad apvienojiet atsevišķos elementus sakārtotā veidā. Šeit iekarot un apvienot soļus iet blakus.
Apvienojiet apakšnodaļas
Laika sarežģītība
Dalīšanas un iekarošanas algoritma sarežģītību aprēķina, izmantojot galveno teorēmu.
T (n) = aT (n / b) + f (n), kur n = ievades lielums a = apakšproblēmu skaits rekursijā n / b = katras apakšproblēmas lielums. Tiek pieņemts, ka visām apakšproblēmām ir vienāds izmērs. f (n) = ārpus rekurzīvā zvana veiktā darba izmaksas, kas ietver problēmas sadalīšanas un risinājumu apvienošanas izmaksas
Ņemsim piemēru, lai atrastu rekursīvas problēmas sarežģītību laikā.
Apvienošanas kārtībai vienādojumu var rakstīt šādi:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Kur a = 2 (katru reizi problēma tiek sadalīta 2 apakšproblēmās) n / b = n / 2 (katras apakšproblēmas lielums ir puse no ievadītās vērtības) f (n) = laiks, kas vajadzīgs problēmas sadalīšanai un apakšproblēmu apvienošanai T (n / 2) = O (n log n) (Lai to saprastu, lūdzu, skatiet galvenā teorēma.) Tagad T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Sadaliet un iekarojiet Vs dinamisko pieeju
Pieeja dalīt un iekarot problēmu sadala mazākās apakšproblēmās; šīs apakšproblēmas tiek tālāk atrisinātas rekursīvi. Katras apakšproblēmas rezultāts netiek saglabāts turpmākai izmantošanai, turpretim dinamiskā pieejā katra apakšproblēmas rezultāts tiek saglabāts turpmākai izmantošanai.
Izmantojiet dalīšanas un iekarošanas pieeju, ja viena un tā pati problēma netiek atrisināta vairākas reizes. Izmantojiet dinamisko pieeju, kad apakšproblēmas rezultāts nākotnē tiks izmantots vairākas reizes.
Ļaujiet mums to saprast ar piemēru. Pieņemsim, ka mēs cenšamies atrast Fibonači sēriju. Tad,
Pieeja sadalīt un iekarot:
fib (n) Ja n <2, atgriež 1 citu, atgriež f (n - 1) + f (n -2)
Dinamiskā pieeja:
mem = () fib (n) Ja n in mem: atgrieziet mem (n) else, ja n <2, f = 1 cits, f = f (n - 1) + f (n -2) mem (n) = f atgriešanās f
Dinamiskā pieejā mem saglabā katra apakšproblēmas rezultātu.
Šķiršanas un iekarošanas algoritma priekšrocības
- Divu matricu reizināšanas sarežģītība, izmantojot naivu metodi, ir O (n 3 ), turpretī, izmantojot dalīšanas un iekarošanas pieeju (ti, Strassena matricas reizinājumu), O (n 2,8074 ). Šī pieeja vienkāršo arī citas problēmas, piemēram, Hanojas torni.
- Šī pieeja ir piemērota daudzapstrādes sistēmām.
- Tas efektīvi izmanto atmiņas kešatmiņas.
Sadaliet un iekarojiet lietojumprogrammas
- Binārā meklēšana
- Apvienot Kārtot
- Ātra kārtošana
- Štrasena Matricas reizināšana
- Karatsuba algoritms
