Algoritmul divide et impera

Nu pot decât mă amuz de fiecare dată când citesc pe internet ceva despre programare. Mai ales cursurile unor facultăți. Totul e atât de matematic, conțin variabile și presupuneri abstracte și seci. Propuneri de genul: să ne imaginăm problema P_b de complexitate c².

What?!

Algoritmul divite et impera nu este ceva complicat și toată explicația sa este conținută în denumire: împarte și cucerește. Sau altfel spus împarte și simplifică.

În „probleme pe calculator”, algoritmul acesta funcționează foarte bine pe vectori/șiruri. Pentru că partea de a împărți munca este foarte ușor de făcut când ai un vector. Adică de ce să afli cea mai mică valoarea dintre 4 numere când poți să o afli dintre 2.

Ia uite un exemplu: care e valoarea cea mai mica dintre 8, 12, 16 și 2. Păi e 2. Se vede clar.

Dacă mergem pe gândirea clasică, programatică (bleah, ce cuvinte), atunci luăm valorile pe rând și o reținem pe cea mai mică, la fiecare pas. Îl luăm pe 8 și fiindcăm suntem la început, îl reținem. Apoi luăm al doilea element și îl comparăm cu cel mai mic. Opt e mai mic decât 12 așa că mergem mai departe cu 8.

În gândirea divide et impera mergem diferit. Zicem: Avem 4 elemente? Cam mult. Hai să împărțim munca. Iau eu două și tu iei două și vedem care e mai mic.

Eu iau 8 și 12, tu iei 16 și 2. Și e foarte ușor să tăiem un vector în două. Stau și mă gândesc și ajung la concluzia că 8 e mai mic decât 12. Tu te gândești și zici: Paf, 2 e mai mic decât 16 cât e ziua de lungă. După muncă, ne întâlnim cu rezultatele, le punem pe masă: eu am 8, tu ai 2-ul. Tu ai valoarea cea mai mică: problemă rezolvată.

Pare mai simplu cu divide et impera. Jumătate de muncă per cap, fiecare lucrează în paralel, rezultatul vine mai repede.

Ce caracteristici are acest divide et impera?

1. În primul rând trebuie să știm formula cea mai simplă pentru problema dată. Cel mai mic (sau mai mare) număr se poate afla dintre două valori. Așa că ținem minte că atunci când șirul nostru are două valori pur și simplu facem verificarea. (Dacă avem o valoare, nici nu mai comparăm, el este cel mai mic/mai mare)
2. Orice vector mai mare de două valori va fi împărțit în două bucăți.

Acuma, cum facem rost de mai multe capete? Adică ce se întâmplă dacă avem 8 valori? Eu iau 4 și tu 4, eu după ce le împart la 2, cui ii dau să compare cele două valori extra?

Și aici limbajele de programare ne sar în ajutor și ne prezintă idea de recursivitate. Sau altfel spus când definim o funcție, ea poate, în corpul definiției sale să se cheme pe sine. Ceva de genul f(x) = x + 1. Pentru x = 1, f(x) va fi 2. Dar pentru f(f(1)) ? Păi îi f(2) care va fi 3. Ei uite că exact genul ăsta de șiretlic îl putem folosi când scriem programe.

Ok, ok, deci am o funcție care găsește maximul unui vector, care împarte vectorul în jumătăți până vectorul are lungimea 2 și atunci ne dă rezultatul, dar de câte ori poate funcția asta care mi-o tot învârți în jurul nasului să se apeleze pe sine?

Aici realitatea ne lovește din plin. Memoria RAM a calculatorului nu este infinită, de fiecare dacă când un program cheamă o funcție, de fiecare dată când o funcție este chemată dintr-altă funcție, puțin din memoria totală este ocupată. Și la un moment dat programul nu va mai putea chema nici o funcție pentru că nu mai are memorie disponibilă.

Putem avea un șir de 128 de elemente. El se va împărți în două apeluri de 64 elemente, acesta se va împărți în 4 apeluri de 32 de elemente, apoi în 8 de 16 elemente, 16 de 8, 32 de 4 și în final 64 de apeluri de funcții de 2 elemente fiecare. Uau! 64 de apeluri.

Dar dacă avem un șir de 16 milioane de elemente?

Algoritmul divide et impera este foarte bun, atâta timp cât nu este folosit fără cap. La fel cu numărul de persoane care trăiesc pe planetă și care pot să compare două numere, și calculatorul are o limită de câte apeluri pot fi făcute de un program. În final tot atâtea comparații se fac, ca să afli maximul tot va trebui să parcurgi vectorul întreg. Nu este o scurtătură în sensul de a face mai puține operații, însă atunci când ai la dispoziție mai multe procesoare, chiar dacă numai două, începe să prezinte unele avantaje: poate înjumătăți timpul necesar aflării rezultatului.