De ce contează?
Trebuie să numeri câte cărți sunt într-un teanc uriaș și ești singur — ar dura o veșnicie. Dar ai patru prieteni. Tai teancul în două, dai fiecare jumătate unui prieten, iar el o taie iar în două și o pasează mai departe. La final fiecare numără un teanc mic, iar tu doar aduni numerele primite înapoi. Ai rezolvat o problemă mare spărgând-o în bucăți mici și lipind răspunsurile la loc. Asta e, în esență, Divide et Impera.
Intuiția
Divide et Impera („împarte și stăpânește") rezolvă o problemă mare în trei pași: o împarți în subprobleme de obicei pe jumătate, stăpânești fiecare jumătate rezolvând-o recursiv (e aceeași problemă, dar mai mică), apoi combini rezultatele într-un singur răspuns. Când o jumătate devine destul de mică (un singur element), o rezolvi pe loc — acela e cazul de bază.
Firul nostru roșu: vrem suma vectorului [3, 1, 4, 1, 5, 9]. În loc să
adunăm tot liniar, tăiem vectorul în două jumătăți, cerem suma fiecăreia (recursiv)
și le adunăm. Combinarea aici e ieftină: o singură adunare.