Algoritmi - poređenja složenosti

Poređenja algoritama koji rešavaju isti problem

U nastavku priče o algoritmima bavićemo se konstrukcijom algoritma koji rade sa nizovima. Kako će naglasak biti na idejama za konstrukciju algoritama, onda je razumno ignorisati konkretne tipove podataka (celi broj, niska,...), pa ćemo za ovu priliku smatrati da   element   je podatak kome tip nije preciziran.

Posledica takovog shvatanja je da npr. proces sortiranja u kome su jedine operacije uređivanje i kopiranje će biti opisan istim algoritmom i za niz celih brojeva i za niz imena, jer razlike postoje samo u realizaciji, ali ideje na kojima se zasniva algoritam su iste. Ako se radi o sortiranju elemenata nekog skupa (uređivanje po veličini), svojstva koja se podrazumevaju su:

• elementi se mogu upoređivati na jednakost

• elementi su iz potpuno uređenog skupa

• elementi se mogu kopirati

Niz

• čine ga elementi istog tipa

• veličina niza je broj elemenata u njemu i veličina niza je fiksirana (tj. mora biti unapred poznata, jer se unapred mora znati i veličina dodeljene memorije)

• ako niz ima   n   elemenata, onda je prvi element a[0], a poslednji element niza a[n-1].

• ako je prvi element niza na lokaciji   p,   onda je   k-ti   element na lokaciji:

  p+(k-1)*br_bajtova_za _1_element  

  Na višem programskom jeziku o poziciji elementa se ne razmišlja, jer taj posao obavlja kompajler

• Prednost: jednako vreme pristupa elementima

• Nedostaci: elementi su istog tipa, veličina je fiksirana

P1. Za zadate cele brojeve a₁, a₂,...,a_n pronaći maksimalnu vrednost sume ∑ _k=i..j  a_k, gde 1<=i<=n, 1<=j<=n i u slučaju nepraznog podniza i <= j

Smatrati da maksimalna vrednost sume elemenata podniza niza a je nula, ako su svi članovi podniza negativni.

Test-primer:

Pre algoritma, razmotrimo gore navedenu napomenu, odnosno mogućnost pojave praznog podniza.

U slučaju da su na ulazu svi brojevi negativni, izlaz će biti 0 (po formulaciji problema). Iako bi izlaz mogao biti negativni broj najmanje aposolutne vrednosti. Razlog leži u situaciji pojave praznog podniza (sa 0 elemenata), koji jeste podniz i čija suma jeste 0. Kako je prazni podniz niz sa uzastopnim članovima, jasno je da je njegova suma kandidat za rešenje , pa tako uvek postoji podniz uzastopnih elemenata čija suma je 0.

Problem br. 12 je interesantan za diskusiju, jer postoji mnogo algoritama koji rešavaju formulisani problem, ali perfomanse tih algoritama drastično variraju.

Slede četiri algoritma koji rešavaju problem 12

• brute force algoritam reda O(n³)

• poboljšani algoritam reda O(n²)

• divide-and-conquer algoritam reda O(n log n)

• algoritam red O(n)

Algoritam grube sile (a,n)

1. Na vreme izvršavanja algoritma dominatno utiče unutrašnji for ciklus (14,15).
   Postoje 4 naredbe:

   1. inicijalizacija k=i

   2. test k <= j

   3. sabiranje u 15

   4. inkrementacija k++

   
   Broj ponavljanja fragmenta 15 dominira među ova četiri izraza. Zašto?
   Dakle, potrebno je izračunati ukupan broj izvršavanja fragmenta 15 u čitavom algoritmu.
        Broj ponavljanja fragmenta 15 jednak je broju uređenih trojki (i,j,k) za koje važi 1 <= i <= k <= j <= n, jer indeks i prolazi čitav niz, dok j prolazi vrednosti od indeksa i do indeksa poslednjeg člana niza, a k ima vrednosti izmeđi [i, j].
   Ukupan broj tih trojki je n(n+1)(n+2)/6 tj. O(n³). Zašto?

2. Može li se ukloniti petlja 14 i time poboljšati algoritam?
   Može, jer a[i] + a[i+1] +...+ a[j ]= (a[i] + a[i+1] +...+ a[j-1] ) + a[j] = A[j-1] + a[j], tj. odbaciće se redundantnost ako se na već izračunatu sumu A[j-1] doda a[j]. Zato algoritam kvadratne složenosti glasi:

Algoritam MaxSumTest2 (a,n)

1  input: a, n
2  output: maxSum
3  /* seqStart ,  seqEnd reprezentuju trenutnu sekvencu kandidata    */
4      
5      {  
6          maxSum = 0;
7          seqStart = 0;
8          seqEnd = -1;
9  
10  
11  
12          for( i = 0; i < n; i++ )
13          {
14              tekSum = 0;
15              for( j = i; j < n; j++ )
16              {
17                  tekSum += a[ j ];
18  
19                  if( tekSum > maxSum )
20                  {
21                      maxSum = tekSum;
22                      seqStart = i;
23                      seqEnd   = j;
24                  }
25              }
26          }
27  
28  
29      }
30  

1. U ovom algoritmu spoljašnji for ciklus se prolazi n puta, unutar kog je ugnježden for ciklus koji se prolazi potencijalno n puta unutar kog su 1-koraġne naredbe dodele, sabiranja i poređenja, te oba for ciklusa imaju potencijalno n*n iteracija sa 1-koraġnim operacijam =>: vremenska složenost je O(n²).

2. Može li se ukloniti petlja 15 i time poboljšati algoritam?

3. Može, jer i algoritam broj 2 ima tzv. iscrpno pretraživanje svih mogućih rešenja, tj. isprobavanje svih mogućih podnizova,
   a razlika algoritma 2 i algoritma 1 je što se kod algoritma 2 provera svakog uzastopnog podniza obavi za O(1) vreme, a kod algoritma 1 za O(n) vreme.
   Međutim broj mogućih podnizova je O(n²), te poboljšanje algoritam se može postići samo ako se nađe način da se neki podnizovi eliminišu kako kandidati i da se ne vrši izračunavanje njihovih suma i poređenje sa tekućim maksimumom. Ali, to je tema algoritma 4.

    

   Algoritam MaxSumTest3 (a,n)

   /* algoritam tipa "zavadi, pa vladaj" reda O(n log n) */

   /*
        - Rekurzivni algoritam.
        - Nalazi maximum sume u podnizu  a[levo..desno].
        - Ne radi se odrzavanje trenutne sekvence-kandidata za resenje
        */
   1  input: a, n
   2  output: maxSum
   3   {
   4           maxSum =   n > 0 ? maxSumRec( a, 0, n - 1 ) : 0;
   5   }
   6  int maxSumRec (a, left, right)
   7  input: a, left, right
   8  output: max
         {
   9          maxLeftBorderSum = 0, maxRightBorderSum = 0;
   10          leftBorderSum = 0, rightBorderSum = 0;
   11          center = ( left + right ) / 2;
   12  
   13          if( left == right )  /* bazni slucaj */
   14              return a[ left ] > 0 ? a[ left ] : 0;
   15  
   16          /*rekurzivni pozivi po podnizovima*/
   17          maxLeftSum  = maxSumRec( a, left, center );
   18          maxRightSum = maxSumRec( a, center + 1, right );
   19  
   20          for( i = center; i >= left; i-- )
   21          {
   22              leftBorderSum += a[ i ];
   23              if( leftBorderSum > maxLeftBorderSum )
   24                  maxLeftBorderSum = leftBorderSum;
   25          }
   26  
   27          for( i = center + 1; i <= right; i++ )
   28          {
   29              rightBorderSum += a[ i ];
   30              if( rightBorderSum > maxRightBorderSum )
   31                  maxRightBorderSum = rightBorderSum;
   32          }
   33  
   34          max= max3( maxLeftSum, maxRightSum,
   35                       maxLeftBorderSum + maxRightBorderSum );
   36   }
   36           
   37      /*       maximum tri broja        */
   38      Algoritam  max3( a, b, c )
   39      input: a,b,c
   40      output: max 3 broja
   41       {
   42          return a > b ? a > c ? a : c : b > c ? b : c;
   43      }
   44  

    

   1. U ovom algoritmu se koristi tehnika ZAVADI PA VLADAJ (divide-and-conquer). Taj metod dekompozicije obuhvata podelu ulaza na manje podskupove, njihovu obradu rekurzivnim pozivom procedure (ZAVADI), i objedinjavanje dobijenih rešenja (PA VLADAJ). Najčešće se problem deli u potprobleme jednake veličine, tradicionalno se onaj fragment algoritma koji ima bar dva rekurzivna poziva naziva ZAVADI-PA-VLADAJ algoritam. Naravno, podproblemi (tj podskupovi ulaza) se ne smeju preklapati, da bi se izbeglo prekomerni pozivi i zračunavanja kakva npr. postoje u algoritmu koji rekurzijom izračunava Fibonačijeve brojeve.
      Ova tehnika se koristi kod problema nalaženja konture skupa pravougaonika ili sortiranja učešljavanjem ili quick sort-a.

   2. Podniz maksimalne sume može:

      • kompletno pripadati levoj polovini niza ili

      • kompletno pripadati desnoj polovini niza ili

      • početi u levoj polovini niza, a završiti u desnoj polovini niza

      Zato je ideja sledeća

      • rekurzivno izračunati maksimalnu sumu podniza koji kompletno pripada levoj polovini niza (koraci 17)

      • rekurzivno izračunati maksimalnu sumu podniza koji kompletno pripada desnoj polovini niza (koraci 18)

      • u dva uzastopna ciklusa izračunati maksimalnu sumu podniza koji počinje u levoj polovini niza, a zavr5iti u desnoj polovini niza (koraci 20-32)

      • naći maksimum među te tri sume (koraci 34-35)

      • Kako rekurzija zahteva i specificiranje baznog slučaja, tj. izlaz je kada ulaz problema se sastoji samo od jednog elementa. U linijama 13-14 obezbeđen je izlaz iz rekurzije, jer kada left==right, onda rezultat je ili nula ili vrednost jedinog, nenegativnog elementa.
        U linijam 17 i 18 izvode se rekurzivni pozivi, i ti pozivi se uvek obavljaju nad potproblemima manje dimenzije od polaznog, tj. tim pozivima se napreduje ka baznom slučaju, tj. izlazu iz rekurzije.

   3. Složenost algoritma je O(n   log n). Zašto?
      Označimo sa T(n) broj potrebnih vremenskih jedinica za rešavanje problema maksimalne sume podniza u nizu dimenzije n.

      Tada je

      • T(1)=1 (linije 13-14)

      • T(n)= 2 T(n/2) + O(n) ( 2 rekurzije u linijama 17-18, plus linije 20-32 za const*N operacija račinaju maksimalnu sumu) )

Ova difrencna jednačina može da se reši tehnikom teleskopskih suma, ali i pozivom na Teoremu 2.1 iz knjige profesora Živkovića.

Teorema 2.1. Asimpototsko ponašanje niza T(n), rešenja difrencne jednačine

T(n) = a T(n/b) + c n ^k, a, b, c, k >=0, b !=0 i zadato je T(1)

dato je sa:

• T(n)= O (n ^{log b a} ) za a > b ^k

• T(n)= O (n ^k log n ) za a = b ^k

• T(n)= O (n ^k ) za a < b ^k


Kako je u algoritmu 3: a=2, b=2, a=b (tj. k=1), onda je T(n) = O (n log n)

 

1. Vratimo se algoritmu 2 i njegovoj modifikaciji, tj. može li se ukloniti petlja 15 i time poboljšati algoritam?

2. Može, jer i algoritam broj 2 ima tzv. iscrpno pretraživanje svih mogućih rešenja, tj. isprobavanje svih mogućih podnizova,
   a razlika algoritma 2 i algoritma 1 je što se kod algoritma 2 provera svakog uzastopnog podniza obavi za O(1) vreme, a kod algoritma 1 za O(n) vreme.
   Međutim broj mogućih podnizova je O(n²), te poboljšanje algoritam se može postići samo ako se nađe način da se neki podnizovi eliminišu kako kandidati i da se ne vrši izračunavanje njihovih suma i poređenje sa tekućim maksimumom. To je tema algoritma 4.

   Ideja algoritma 4

   
   OZNAKE: Neka A[i,j] je podniza: a[i], a[i+1],...,a[j], neka S[i,j] = a[i]+a[i+1] +...+ a[j]
   Stav 1     Neka A[i,j] je ma koja sekvenca za koju je S[i,j] < 0. Ako je q > j, onda A[i,q] nije podniz maksimalne sume.
   DOKAZ: Jasno je da: S[i,q]=S[i,j] + S[j+1, q]. Kako je S[i,j] < 0, onda je S[i,q] < S[j+1, q] => A[i,q] ne može biti podniz maksimalne sume.
   
   Stav 2     Za ma koje i, neka A[i,j] je prvi podniz za koji je S[i,j] < 0. Tada za neko p takvo da i <= p <= j, p <= q važi da: ili A[p,q] nije podniz maksimalne sume ili ima sumu jednaku sa do tada pronađenim maksimuom.
   DOKAZ:

   • Ako p==i, onda važi stav 1, tj. A[p,q] nije podniz maksimalne sume.

   • Inače, S[i,q]=S[i,p-1]+S[p,q]
     Kako j je najmanji indeks za koji S[i,j] <0, onda je S[i, p-1] > = 0, pa je S[i,q] > S[p,q]
     Ako je q > j (videti SLIKA 1), onda po stavu 1 sledi A[i,q] nije podniz maksimalne sume, te to nije ni A[p,q]. Inače (videti SLIKA 2), podniz A[p,q] ima sumu jednaku bar već pronađenom podnizu A[i,q].

   KOJI JE SMISAO UPOTREBE STAVA 1 i STAVA 2 u KONSTRUKCIJI ALGORITMA 4?
   Po stavu 1 se u algoritmu 2 može izaći iz unutrašnje petlje ako je tekSum < 0 i to se koristi u liniji 21 u algoritmu 4, dok stav 2 nam govori da u liniji 23 se može preći sa indeksa i na j+1. U algoritmu 4, skaniranje podnizova se obavlja uvećanjem indeksa j, tako da jedini for ciklus iterira najviše n puta, a telo for ciklusa ima 1-koračne naredbe dodele, sabiranja uz dva poređenja, te složenost je O(n).

    

SLIKA 1

i	j	j+1		q
S[i,q]
> = 0	< = S[i,q]
p-1	p

SLIKA 2

i			q	j
S[i,q]
> = 0	< = S[i,q]
p-1	p

Algoritam MaxSumTest4 (a,n)

/* algoritam  reda O(n) */
     seqStart,  seqEnd reprezentuju trenutnu sekvencu kandidata
     */
1  input: a, n
2  output: maxSum
3      
4      {
5           maxSum = 0;
6           tekSum = 0;
7            seqStart = 0;
8           seqEnd = -1;
9   
10  
11          for( i = 0, j = 0; j < n; j++ )
12          {
13              thisSum += a[ j ];
14  
15              if( thisSum > maxSum )
16              {
17                  maxSum = thisSum;
18                  seqStart = i;
19                  seqEnd   = j;
20              }
21              else if( thisSum < 0 )
22              {
23                  i = j + 1;
24                  thisSum = 0;
25              }
26          }
27  
28  
29      }

P2. Porazmisliti o varijanti ovog zadatka sa proizvodom umesto sume.

Jelena Grmuša

Primene računara

---