Šioje pamokoje sužinosite, kaip veikia padalijimo ir užkariavimo algoritmas. Mes taip pat palyginsime skaldymo ir užkariavimo metodą, palyginti su kitais rekursinės problemos sprendimo būdais.
Skaldyk ir valdyk algoritmas yra spręsti didelę problemą strategija
- išskaidant problemą į mažesnes subproblemas
- spręsdamas subproblemas ir
- derinant juos norimam rezultatui gauti.
Norint naudoti dalijimo ir užkariavimo algoritmą, naudojamas rekursija . Sužinokite apie rekursiją skirtingomis programavimo kalbomis:
- Rekursija „Java“
- Rekursija „Python“
- Rekursija C ++
Kaip veikia skaldymo ir užkariavimo algoritmai?
Štai keli veiksmai:
- Padalinti : padalykite pateiktą problemą į subproblemas naudodami rekursiją.
- Užkariauti : rekursyviai spręskite mažesnes subproblemas. Jei subproblema yra pakankamai maža, išspręskite ją tiesiogiai.
- Sujungti: sujunkite subproblemų, kurios yra rekursyvaus proceso dalis, sprendimus, kad išspręstumėte faktinę problemą.
Supraskime šią sąvoką pavyzdžio pagalba.
Čia mes surūšiuosime masyvą naudodamiesi dalijimo ir užkariavimo metodu (ty.
- Tegu pateiktas masyvas yra: Masyvas
suliejimo rūšiavimui - Masyvą padalykite į dvi puses.
Masyvą
padalinkite į du poskyrius Vėlgi, padalykite kiekvieną rekursiškai į dvi dalis, kol gausite atskirus elementus.
Padalinkite masyvą į mažesnius padalinius - Dabar atskirus elementus derinkite rūšiuodami. Čia užkariaukite ir sujunkite žingsnius.
Sujunkite poskyrius
Laiko kompleksiškumas
Skaldymo ir užkariavimo algoritmo sudėtingumas apskaičiuojamas naudojant pagrindinę teoremą.
T (n) = aT (n / b) + f (n), kur, n = įvesties dydis a = rekursijoje esančių subproblemų skaičius n / b = kiekvieno papunkčio dydis. Manoma, kad visi subproblemos yra vienodo dydžio. f (n) = už rekursinio skambučio atlikto darbo kainą, į kurią įeina problemos padalijimo ir sprendimų sujungimo išlaidos
Paimkime pavyzdį, kaip surasti rekursinės problemos sudėtingumą laike.
Sujungimo rūšiai lygtis gali būti parašyta taip:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Kur a = 2 (kiekvieną kartą problema padalijama į 2 papunkčius) n / b = n / 2 (kiekvienos papildomos problemos dydis yra pusė įvesties) f (n) = laikas, kurio prireikė problemai padalyti ir subproblemoms sujungti T (n / 2) = O (n log n) (Norėdami tai suprasti, skaitykite pagrindinė teorema.) Dabar T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Skaldykite ir užkariaukite dinaminį požiūrį
„Skaldyk ir užkariauk“ metodas problemą suskirsto į mažesnes dalines problemas; šios problemos toliau sprendžiamos rekursiškai. Kiekvieno subproblemos rezultatas nėra saugomas ateityje, o taikant dinamišką požiūrį, kiekvieno subproblemo rezultatas yra saugomas ateityje.
Taikykite padalijimo ir užkariavimo metodą, kai tas pats potvarkis nėra išspręstas kelis kartus. Naudokite dinaminį metodą, kai papildomo uždavinio rezultatas ateityje bus naudojamas kelis kartus.
Supraskime tai su pavyzdžiu. Tarkime, kad mes bandome rasti „Fibonacci“ seriją. Tada
Skaldykite ir užkariaukite požiūrį:
fib (n) Jei n <2, grąžinkite 1 Else, grąžinkite f (n - 1) + f (n -2)
Dinaminis požiūris:
mem = () fib (n) Jei n mem: grąžinkite mem (n) dar, jei n <2, f = 1 kitas, f = f (n - 1) + f (n -2) mem (n) = f grįžti f
Taikant dinamišką požiūrį, mem saugo kiekvieno papunkčio rezultatą.
Skaldykite ir užkariaukite algoritmo privalumai
- Dviejų matricų dauginimo, naudojant naivųjį metodą, sudėtingumas yra O (n 3 ), o naudojant padalijimo ir užkariavimo metodą (ty Strasseno matricos dauginimą) yra O (n 2,8074 ). Šis požiūris taip pat supaprastina kitas problemas, pavyzdžiui, Hanojaus bokštą.
- Šis metodas tinka daugiaprocesinėms sistemoms.
- Tai efektyviai naudoja atminties talpyklas.
Skirstykite ir užkariaukite programas
- Dvejetainė paieška
- Sujungti rūšiuoti
- Greitas rūšiavimas
- Strasseno matricos daugyba
- Karatsubos algoritmas
