V tej vadnici boste izvedeli, kako deluje algoritem deli in osvoji. Primerjali bomo tudi pristop ločitve in osvajanja v primerjavi z drugimi pristopi za reševanje rekurzivnega problema.
Deli in vladaj je strategija reševanja velik problem, ki ga
- razbijanje problema na manjše podprobleme
- reševanje podproblemov in
- jih kombiniramo, da dobimo želeni izhod.
Za uporabo algoritma deli in vladaj se uporablja rekurzija . Spoznajte rekurzijo v različnih programskih jezikih:
- Rekurzija v Javi
- Rekurzija v Pythonu
- Rekurzija v jeziku C ++
Kako delujejo in osvajajo algoritmi?
Tu so navedeni koraki:
- Divide : dano težavo razdelite na podtežo z uporabo rekurzije.
- Conquer : Manjše podnaloge rešite rekurzivno. Če je podteza dovolj majhna, jo rešite neposredno.
- Združite: združite rešitve podproblemov, ki so del rekurzivnega procesa, da rešite dejanski problem.
Razumimo ta koncept s pomočjo primera.
Tu bomo matriko razvrstili s pristopom deli in osvoji (tj. Združi razvrščanje).
- Naj bo dana matrika:
Matrika za razvrščanje po združitvi - Niz razdelite na dve polovici.
Polje razdelite na dva
poddela Spet vsak poddel rekurzivno razdelite na dve polovici, dokler ne dobite posameznih elementov.
Niz razdelite na manjše dele - Zdaj kombinirajte posamezne elemente na razvrščen način. Tu osvojite in kombinirajte korake, ki gredo drug ob drugem.
Združite poddelke
Zapletenost časa
Zapletenost algoritma deli in vladaj izračunamo z uporabo glavnega izreka.
T (n) = aT (n / b) + f (n), kjer je n = velikost vnosa a = število podproblemov v rekurziji n / b = velikost vsakega podproblema. Vsi podproblemi naj bi imeli enako velikost. f (n) = stroški dela, opravljenega zunaj rekurzivnega klica, ki vključuje stroške delitve problema in stroške združitve rešitev
Vzemimo primer, da najdemo časovno zapletenost rekurzivnega problema.
Za združevanje lahko enačbo zapišemo kot:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Kjer je a = 2 (vsakič je problem razdeljen na 2 podproblema) n / b = n / 2 (velikost vsake podteže je polovica vnosa) f (n) = čas, potreben za razdelitev problema in združevanje podproblemov T (n / 2) = O (n log n) (Za razumevanje tega glejte glavni izrek.) Zdaj je T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs Dynamic pristop
Pristop »loči in osvoji« razdeli problem na manjše podprobleme; ti podproblemi se nadalje rešujejo rekurzivno. Rezultat vsakega podproblema se ne shrani za nadaljnjo referenco, medtem ko se pri dinamičnem pristopu rezultat vsakega podproblema shrani za prihodnjo referenco.
Uporabite pristop deli in osvoji, kadar isti podproblem ni večkrat rešen. Uporabite dinamični pristop, če bo rezultat podproblema v prihodnosti večkrat uporabljen.
Razumimo to na primeru. Recimo, da poskušamo najti Fibonaccijevo serijo. Potem,
Pristop Divide and Conquer:
fib (n) Če je n <2, vrni 1 sicer, vrni f (n - 1) + f (n -2)
Dinamičen pristop:
mem = () fib (n) Če je n v mem: vrni mem (n) else, če je n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f vrnitev f
V dinamičnem pristopu mem shrani rezultat vsakega podproblema.
Prednosti algoritma delitve in osvajanja
- Komplikacija množenja dveh matrik z naivno metodo je O (n 3 ), medtem ko je z uporabo pristopa deli in osvoji (tj. Strassenovo množenje matric) O (n 2.8074 ). Ta pristop poenostavlja tudi druge težave, na primer Hanojski stolp.
- Ta pristop je primeren za večprocesorske sisteme.
- Učinkovito uporablja pomnilniške predpomnilnike.
Razdelite in osvojite aplikacije
- Binarno iskanje
- Združi razvrsti
- Hitro razvrščanje
- Množenje matrice Strassen
- Karatsuba algoritem
