Algoritmi/"Podeli, pa vladaj"

Prva među glavnim algoritamskim tehnikama koju ćemo pokriti je podeli i vladaj (divide et impera). Deo veštine pravljenja dobrog algoritma podeli i vladaj je određivanje kako zadati problem može da bude podeljen na dva ili više sličnih, ali manjih potproblema. Generalno rečeno, kada pravimo algoritam podeli i vladaj, preduzimamo sledeće korake:

Metodologija podeli i vladaj Za dati problem identifikovati mali broj značajno manjih potproblema istog tipa. Rešiti svaki potproblem rekurzijom (najmanja moguća veličina potproblema je bazni slučaj). Objedinite dobijena parcijalna rešenja u rešenje glavnog problema.

Prvi algoritam koji ćemo prikazati korišćenjem ove metodologije je sortiranje spajanjem.

Sortiranje spajanjem

Problem koji sortiranje spajanjem rešava je opšte sortiranje zadatog neuređenog vektora elemenata. Ovaj algoritam kao rezultat daje vektor sortiranih elemenata. Tačnije, za neki vektor a sa indeksom 1 do n, u slučaju da važi uslov da

za svako i, j takvo da je 1 ≤ i < j ≤ n onda a[i] ≤ a[j]

može reći da je a sortiran. Ovde je prikazan interfejs:

// sort -- враћа копију сортираног низа a
function sort(array a): array

Sledeći metodologiju podeli i vladaj, kako sortiranje a da podelimo na manje potprobleme? Pošto je a vektor od n elemenata, možda možemo započeti deljenjem vektora na dva, veličine n/2 elemenata. Ovi manji vektori će takođe biti nesortirani i ima smisla da svaki sortiramo zasebno; tako ćemo njih smatrati „sličnim“. Zanemarujući za sada bazni slučaj, na ovaj način svodimo problem na drugi: kako ćemo objediniti dva zadata sortirana vektora u jedan sortirani vektor koji sadrži sve njihove elemente:

// merge -- дато a и b (претпоставља се да су сортирани) враћа спојени низ који 
// одржава редослед
function merge(array a, array b): array

Do sada smo sledeći metodologiju došli do ovde, ali šta je sa baznim slučajem? Bazni slučaj je deo algoritma koji se odnosi na to šta se dešava kada problem ne može više da se podeli na manje potprobleme. Ovde je bazni slučaj kada vektor sadrži samo jedan element. Dole je prikazan algoritam za sortiranje vektora koji sadrži 0 ili 1 element:

// base-sort -- дат је низ од једног елемента (или празан), враћа копију 
// сортираног низа
function base-sort(array a[1..n]): array
  assert (n <= 1)
  return a.copy()
end

Sastavljajući prikazane delove koda, dobijamo do čega nas je do sada dovela metodologija:

// sort -- враћа копију сортираног низа a
function sort(array a[1..n]): array
  if n <= 1: return a.copy()
  else:
    let sub_size := n / 2
    let first_half := sort(a[1,..,sub_size])
    let second_half := sort(a[sub_size + 1,..,n])
    
    return merge(first_half, second_half)
  fi
end

I osim neimplementiranog koda za potprogram merge, ovaj algoritam sortiranja je gotov! Pre nego što pokažemo kako ovaj algoritam radi, prikazaćemo kako može da bude napisan merge:

// merge -- дато a и b (претпоставља се да су сортирани) враћа спојени низ који 
// одржава редослед
function merge(array a[1..n], array b[1..m]): array
  let result := new array[n + m]
  let i, j := 1
  
  for k := 1 to n + m:
    if i >= n: result[k] := b[j]; j += 1
    else-if j >= m: result[k] := a[i]; i += 1
    else:
      if a[i] < b[j]:
        result[k] := a[i]; i += 1
      else:
        result[k] := b[j]; j += 1
      fi
    fi
  repeat
end

Analiza

Neka je $T(n)$ broj koraka koji je potreban algoritmu za veličinu ulaza $n$. Spajanje troši linearno vreme i mi vršimo rekurziju svaki put na dva potproblema dvaput manje veličine od izvornog, tako da

$T(n)=2\cdot T\left({\frac {n}{2}}\right)+O(n).$

Prema Glavnoj teoremi vidi se da ova rekurzija ima uravnoteženo stablo, tako da je vreme izvršenja:

$T(n)=O(n\cdot \log n).$

Do ovoga se može doći i intuitivno, zapitajući se koliko puta treba n podeliti sa 2, pre nego što dužina vektora za sortranje postane jednaka 1? Naravno, zašto m puta? 2^m = n , što je ekvivalentno log 2^m = log n, i dalje m x log₂2 = log ₂ n, i pošto je log₂ 2 = 1, sledi da je m = log₂n.

Pošto je m broj polovljenja vektora pre nego što se on podeli na pod-vektore koji sadrže 1 element, biće potrebno m nivoa spajanja nekog pod-vektora sa susedom, gde će sumarna dužina pod-vektora biti n na svakom nivou. Trebaće da se izvrši tačno n/2 poređenja za spajanje na svakom nivou sa m ( log₂n ) nivoa tako da važi da je: O(n/2 x log n ) <=> O ( n log n).

Iterativna verzija

Prikazani algoritam sortiranja spajanjem može da se pretvori u iterativni, iterativnim spajanjem svakog sledećeg para, zatim grupa od četiri itd. Iterativni algoritam je u praksi brži pošto nema dopunske „troškove“ velikog broja poziva funkcija. Ipak, pošto je stablo poziva rekurzivne verzije algoritma logaritamske dubine, on u toku izvršenja ne zauzima mnogo prostora na steku. Za sortiranje čak 4 giga elemenata, potrebno je samo 32 zapisa za pozive na steku, što je veoma skroman zahtev. Ako uzmemo da je jedan zapis veličine čak 256 bajta, trebaće nam samo 8 kilobajta prostora na steku. Iterativna verzija seortiranja spajanjem predstavlja manju modifikaciju rekurzivne verzije, a možemo da iskoristimo i postojeću funkciju merge. Algoritam radi tako što spaja male, sortirane delove izvornog vektora, i od njih pravi veće sortirane delove. Da bi ovo postigli, iteriramo kroz vektor sa sukcesivno sve većim „koracima“.

// sort -- враћа сортирану копију низа a
function sort_iterative(array a[1..n]): array
   let result := a.copy()
   for power := 0 to log2(n-1)
     let unit := 2^power
     for i := 1 to n by unit*2
       if i+unit-1 < n: 
         let a1[1..unit] := result[i..i+unit-1]
         let a2[1..unit] := result[i+unit..min(i+unit*2-1, n)]
         result[i..i+unit*2-1] := merge(a1,a2)
       fi
     repeat
   repeat
   
   return result
end

Ovo radi zato što je svaka podlista dužine 1 nekog vektora, po definiciji sortirana. Svaka iteracija kroz vektor (koristeći brojač i) duplira veličinu sortiranih podlista spajanjem susednih podlista u veće verzije. Trenutna veličina sortiranih podlista algoritma predstavlja promenjljiva unit.

prostorna neefikasnost

Jednostavno, sortiranje spajanjem zahteva prostor od 2 x n: n da zapamti 2 dva manja sortirana vektora i n da upiše konačni rezultat spajanja. Ali ovo sortiranje je i danje odgovarajuće za grupisanja spajanja.

Binarno pretraživanje

Kada je neki vektor sortiran, korišćenjem binarnog pretraživanja brzo možemo da lociramo njegove elemente. Binarno pretraživanje je drugačije od ostalih algoritama tipa podeli i vladaj, u tome što se uglavnom zasniva na podeli (nije potrebno ništa pobediti). Koncept na kome se bazira binarno pretraživanje, biće koristan za razumevanje algoritama particionisanja i brzog sortiranja prikazanih u poglavlju o randomizaciji. Nalaženje stavke u već sortiranom vektoru je slično pronalaženju imena u telefonskom imeniku; možete početi otvarajući knjigu na sredini. Ako je ime koje tražite na otvorenoj stranici, zaustavljate se. Ako ste otišli predaleko, možete započeti isti proces sa prvom polovinom knjige. Ako se ime koje tražite pojavljuje kasnije u knjizi, počinjete proces sa drugom polovinom knjige. Isti proces ponavljate sužavajući svaki put prostor pretraživanja za pola, dok ne nađete ono što tražite (ili dok ne nađete gde bi ono što tražite trebalo da se nalazi da postoji. Sledeći algoritam precizno opisuje pomenuti postupak:

// binary-search -- враћа индекс вредности у датом низу или
// -1 ако вредност не може бити пронађена. Претпоставља се да је низ сортиран у растућем поретку
function binary-search(value, array A[1..n]): integer
  return search-inner(value, A, 1, n + 1)
end

// search-inner -- тражи делове низа; крај је један поред
// lпоследњег елемента 
function search-inner(value, array A, start, end): integer
  if start == end: 
     return -1                   // није пронађен
  fi

  let length := end - start
  if length == 1:
    if value == A[start]:
      return start
    else:
      return -1 
    fi
  fi
  
  let mid := start + (length / 2)
  if value == A[mid]:
    return mid
  else-if value > A[mid]:
    return search-inner(value, A, mid + 1, end)
  else:
    return search-inner(value, A, start, mid)
  fi
end

Primetite da se svi rekurzivni pozivi pojavljuju na kraju funkcije (terminalna, krajnja rekurzija), tako da je algoritam iterativan. Možemo eksplicitno da uklonimo ove pozive, ako programski jezik to već ne uradi za nas pretvarajući vrednosti argumenata prosleđenih rekurzivnim pozivima u dodeljivanje vrednosti, i zatim ponovo skočimo na početak tela funkcije:

// binary-search -- враћа индекс вредности у датом низу, или
// -1 ако вредност не може бити пронађена. Претпоставља се да је низ сортиран у растућем поретку
function binary-search(value, array A[1,..n]): integer
  let start := 1
  let end := n + 1
  
  loop:
    if start == end: return -1 fi                 // није пронађен
  
    let length := end - start
    if length == 1:
      if value == A[start]: return start
      else: return -1 fi
    fi
  
    let mid := start + (length / 2)
    if value == A[mid]:
      return mid
    else-if value > A[mid]:
      start := mid + 1
    else:
      end := mid
    fi
  repeat
end

Iako imamo jedan iterativni algoritam, lakše je promišljati o rekurzivnoj verziji. Ako je broj koraka algoritma $T(n)$, onda imamo sledeću rekurentnost (ponavljanje) koju definiše $T(n)$:

$T(n)=1\cdot T\left({\frac {n}{2}}\right)+O(1).$

Veličina svakog rekurzivnog poziva zavisi od polovine veličine ulaza ($n$), a postoji i konstantna količina vremena koja se troši van rekurzije (na primer za izračunavanje length i mid će se utrošiti ista količina vremena, bez obzira na to koliko elemenata vektor sadrži). Prema Glavnoj teoremi ova rekurentnost ima vrednosti, što predstavlja uravnoteženo stablo, pa je

$T(n)=\Theta (n^{k}\cdot \log n)=\Theta (\log n).$

Tako dolaazimo do toga da ovaj algoritam koristi logaritamsko vreme. Tipično, čak i kada je n velik, bezbedno je da se dopusti da stek raste za aktivacionih zapisa za rekurzivne pozive.

Poteškoće u inicijalno ispravnim implementacijama binarnog pretraživanja

Članak na Vikipediji o binarnom pretraživanju pominje poteškoće prilikom pisanja ispravnog koda za ovaj algoritam. Na primer, implementacija preopterećene Java funkcije Arrays.binarySearch(..) vrši iterativno binarno pretraživanje koje ne radi kada kod celobrojne promenjljive (large integer) dolazi do prekoračenja u jednostavnom izrazu za izračunavanje mid, mid = ( end + start) / 2, t.j. kada je end + start > max_positive_integer. Stoga je gornji algoritam ispravniji kada koristi da je length = end - start i doda polovina length na start. Java algoritam za binarno pretraživanje vraća rezultat koji je koristan za nalaženje pozicije najbližeg ključa koji je veći od ključa po kom se pretražuje, t.j. pozicije na koji ključ pretraživanja može da se umetne. To jest, vraća se (keypos+1) ako ključ pretraživanja nije pronađen, ali je potrebna pozicija za umetanje ključa pretraživanja (insertion_point = -return_value – 1). Gledajući granične vrednosti, pozicija umetanja može da se nalazi odmah na početku liste (ip = 0, return value = -1) do pozicije odmah iza poslednjeg elementa (ip = length(A), return value = - length(A) - 1). Pokušajte da implementirate funkcionalnost gornjeg iterativnog algoritma za binarno pretraživanje kao vežbu koja će biti korisna za bolje razumevanje izloženog.

Školsko množenje

Kako da predstavimo veliki ceo broj sastavljen iz više reči? Možemo da imamo binarni prikaz koristeći vektor reči (ili dodeljeni blok memorije) koje predstavljaju bitove velikog celog broja. Pretpostavimo da imamo dva cela broja, i i želimo da ih pomnožimo. Radi jednostavnosti, usvojićemo da su i i dužine bitova (ako je neki od njih kraći, uvek možemo da ga popunimo nulama na početku). Osnovni način da se pomnože celi brojevi je da se koristi školski algoritam monženja. Ovo je još jednostavnije u binarnom sistemu jer množimo samo sa 1 ili 0:

         x6 x5 x4 x3 x2 x1 x0
      &пута;  y6 y5 y4 y3 y2 y1 y0
      -----------------------
         x6 x5 x4 x3 x2 x1 x0 (када y0 је 1; 0 иначе)
      x6 x5 x4 x3 x2 x1 x0  0 (када y1 је 1; 0 иначе)
   x6 x5 x4 x3 x2 x1 x0  0  0 (када y2 је 1; 0 иначе)
x6 x5 x4 x3 x2 x1 x0  0  0  0 (када y3 је 1; 0 иначе)
  ... итд.

Ovako bi izgledalo opisano množenje kao algoritam:

// multiply -- враћа производ два бинарна цела броја, који су дужине n
function multiply(bitarray x[1,..n], bitarray y[1,..n]): bitarray
  bitarray p = 0
  for i:=1 to n:
    if y[i] == 1:
      p := add(p, x)
    fi
    x := pad(x, 0)         // додаје се још једна нула на крај броја x
  repeat
  return p
end

Podrutina add sabira dva binarna cela broja i vraća rezultata, a podrutina pad postavlja dopunsku cifru na kraj broja (dodavanje nule je isto što i šiftovanje broja ulevo za jedno mesto, što je istovetno njegovom množenju sa dva). Ovde prolazimo petlju n puta i u najgorem slučaju isto toliko puta pozivamo add. Brojevi koji se prosleđuju podrutini add biće, najviše, dužine $2n$. Dalje, možemo da očekujemo da podrutina add može da se izvrši u linearnom vremenu. Sledi, da ako se napravi n poziva podrutine $O(n)$, ceo algoritam će utrošiti $O(n^{2})$ vremena.

Množenje podeli i vladaj

Kao što možete da primetite, ovo nije kraj priče. Prikazali smo „očigledan“ algoritam množenja. Pogledajmo da li nam strategija podeli i vladaj pruža nešto više. Jedan pravac koji želimo da ispitamo je da pokušamo je da podelimo ceo broj na dva dela. Na primer ceo broj x može da se podeli na dva dela $x_{h}$ i $x_{l}$, koji predstavljaju polovine višeg i nižeg reda $x$. Na primer ako if $x$ ima n bitova, imamo

$x=x_{h}\cdot 2^{n/2}+x_{l}$

Isto možemo da uradimo i za:

$y=y_{h}\cdot 2^{n/2}+y_{l}$

Ali iz ove podele, nije jasno kako da pomnožimo delove na način koji omogućava da se dobijeni parcijalni rezultati objedine u konačan rezultat rešenja problema. Napišimo prvo da bi $x\times y$ trebalo da bude:

$x\times y=x_{h}\times y_{h}\cdot (2^{n/2})^{2}+(x_{h}\times y_{l}+x_{l}\times y_{h})\cdot (2^{n/2})+x_{l}\times y_{l}$

Ovo potiče od prostog množenja novih hi/lo reprezentacija za $x$ i $y$ . Množenje manjih delova označeno je simbolom "$\times$". Primetimo da je množenje sa $2^{n/2}$ i $(2^{n/2})^{2}=2^{n}$ i da zahteva pravo množenje: umesto toga možemo samo da broj popunimo desno sa odgovarajućim brojem nula. Ovo dovodi do sledećeg algoritma podeli i vladaj:

// multiply -- враћа производ два бинарна цела броја, који су дужине n
function multiply(bitarray x[1,..n], bitarray y[1,..n]): bitarray
  if n == 1: return x[1] * y[1] fi          // помножити поједине цифре: O(1)
  
  let xh := x[n/2 + 1, .., n]               // сечење низа, O(n)
  let xl := x[0, .., n / 2]                 // сечење низа, O(n)
  let yh := y[n/2 + 1, .., n]               // сечење низа, O(n)
  let yl := y[0, .., n / 2]                 // сечење низа, O(n)
  
  let a := multiply(xh, yh)                 // рекурзивни позив; T(n/2)
  let b := multiply(xh, yl)                 // рекурзивни позив; T(n/2)
  let c := multiply(xl, yh)                 // рекурзивни позив; T(n/2)
  let d := multiply(xl, yl)                 // рекурзивни позив; T(n/2)
  
  b := add(b, c)                            // регуларно додавање; O(n)
  a := shift(a, n)                          // подлога нула; O(n)
  b := shift(b, n/2)                        // подлога нула; O(n)
  return add(a, b, d)                       // регуларно додавање; O(n)
end

Koristićemo Glavnu teoremu za analizu vremena izvršenja algoritma. Pod pretpostavkom da je vreme izvršenja algoritma $T(n)$, komentari pokazuju koliko vremena troši svaki od koraka. Pošto imamo četiri rekurzivna poziva, svaki sa ulazom veličine $n/2$, imamo:

$T(n)=4T(n/2)+O(n)$

gde su $a=4,b=2,k=1$ i znajući da je $4>2^{1}$ dobijamo da se algoritam nalazi u stablu razgranatom pri dnu. Za ovaj slučaj Glavna teorema daje:

$T(n)=O(n^{\log _{2}4})=O(n^{2}).$

Dakle, posle svog uloženog truda, još uvek nismo bolji od školskog algoritma! Na sreću, brojevi i polinomijali predstavljaju skup podataka o kome imamo dopunske informacije. U stvari možemo smanjiti vreme izvršenja primenom nekih matematičkih trikova. Prvo zamenimo $2^{n/2}$ promenjljivom z:

$x\times y=x_{h}*y_{h}z^{2}+(x_{h}*y_{l}+x_{l}*y_{h})z+x_{l}*y_{l}$

Dobijamo kvadratnu jednačinu za koju znamo da su potrebna samo tri koeficijenta ili tačke na grafu da bi se ona jednoznačno opisala. Ipak, u gornjem algoritmu koristili smo ukupno četiri množenja. Hajde da pokušamo da preoblikujemo $x$ i $y$ u linearne funkcije:

$P_{x}(z)=x_{h}\cdot z+x_{l}$

$P_{y}(z)=y_{h}\cdot z+y_{l}$

Sada, za $x\times y$ treba samo da izračunamo $(P_{x}\cdot P_{y})(2^{n/2})$. Procenićemo $P_{x}(z)$ i $P_{y}(z)$ na tri tačke. Tri pogodne tačke za evaluaciju funkcije biće na $(P_{x}\cdot P_{y})(1),(P_{x}\cdot P_{y})(0),(P_{x}\cdot P_{y})(-1)$.

Konverzija osnove broja

Uz binarni sistem brojeva, računarske nauke koriste i brojeve sa osnovom 8 (oktalni sistem) i 16 (heksadecimalni sistem). Veoma je lako konvertovati brojeve iz jednog u drugi sistem. Brojevi apisani oktalno i heksadecimalno su značajno kraći u prikazu od binarnih brojeva. Da bi prikazali prvih 8 brojeva u binarnom sistemu potrebna su nam 3 bita. Tako imamo 0=000, 1=001, 2=010, 3=011, 4=100, 5=101, 6=110, 7=111. Uzmimo M=(2065)8. Da bi dobili binarni prikaz, zamenićemo svaku od četiri cifare sa odgovarajućom trojkom bitova: 010 000 110 101. Po uklanjanju vodećih nula, binarna predstava je direktna: M=(10000110101)₂. (Konverzija brojeva heksadecimalnog sistema je slična, osim što se koristi prikaz od 4 bita za brojeve manje od 16.) Ova činjenica sledi iz opšteg algoritma za konverziju i zapažanja da je 8=$2^{3}$ (i naravno 16=$2^{4}$ ). Izgleda da je najkraći način za konverziju brojeva u binarni sistem, da se prvo izvrši konverzija u oktalni ili heksadecimalni sistem. Pogledajmo sada kako se opšti algoritam za konverziju programski implementira. Radi reference, predstavljanje broja u sistemu sa osnovom (bazom) N može da se sastoji samo od cifara manjih od N. Tačnije, ako:

$(1)M=a_{k}N^{k}+a_{k-1}N^{k-1}+...+a_{1}N^{1}+a_{0}$

gde je $0<=a_{i}<N$ imamo predstavljanje broja M u sistemu sa osnovom N i zapisujemo:

$M=(a_{k}a_{k-1}...a_{0})N$

Ako prepišemo (1) kao:

$(2)M=a_{0}+N*(a_{1}+N*(a_{2}+N*...))$

algoritam za dobijanje koeficijenata postaje očigledniji. Na primer, $a_{0}=M\ modulo\ n$ i $a_{1}=(M/N)\ modulo\ n$ i tako dalje.

Rekurzivna implementacija

Prikažimo algoritam mnemonički: (rezultat je niz simbola, u koji jednu po jednu dodajemo izračunate cifre).

result = "" 
if M < N, result = 'M' + result. Stop. 
S = M mod N, result = 'S' + result
M = M/N 
goto 2 

A few words of explanation.

Nakoliko reči objašnjenja. "" je prazan niz. Možda se setite da je to nulti element pri konkatenaciji nizova. Ovde ćemo proveriti da li procedura konverzije terminira. Ona se zaustavlja kada je M manje od N i u tom slučaju je M cifra (ili neki izabrani simbol za N>10) i nema potrebe za dopunskim akcijama. Samo je dodajte ispred ostalih cifara koje ste ranije dobili. Znak '+' označava konkatenaciju. Ako M nije manje od N, prvo ćemo izdvojiti ostatak deljenja sa N, dodati dobijenu cifru rezultatu, kao što je prethodno opisano, i dodeliti novu vrednost M jednaku M/N. Ceo proces treba da se ponovi počev od koraka 2. Treba nam funkcija Conversion koja ima dva argumenta M i N i koja vraća prikaz broja M u sistemu sa osnovom N. Ova funkcija može da izgleda otprilike ovako:

1 String Conversion(int M, int N) // враћа стринг, осим два цела броја
2 {  
3     if (M < N) // see if it's time to return 
4         return new String(""+M); // ""+M прави стринг као низ цифара
5     else // још увек није време за то
6         return Conversion(M/N, N) +
           new String(""+(M mod N)); // наставити
7 }  

Ovo je praktično radna verzija Java funkcije i skoro isto bi izgledala u C++, a za realizaciju u jeziku C su potrebne manje modifikacije. Kao što se vidi u nekom trenutku funkcija poziva samu sebe sa drugačijim prvim argumentom. Može da se kaže da je funkcija definisana u odnosu na samu sebe. Takve funkcije se zovu rekurzivne. (Najpoznatija rekurzivna funkcija je faktorijal: n!=n*(n-1)!.) Funkcija poziva samu sebe i primenjuje se sa svojim argumentima i zatim se (prirodno) primenjuje sa svojim novim argumentima i onda ... i tako dalje. Možemo da budemo sigurni da će se proces na kraju zaustaviti zato što niz argumenata (prvi argument) opada. Tako će, pre ili kasnije, prvi argument postati manji od drugog i proces će korak po korak izlaziti iz rekurzije.

Iterativna implementacija

Ne dozvoljavaju svi jezici rekurzivne pozive funkcija. Rekurzivne funkcije mogu da budu nepoželjne u slučaju da se očekuje prekid procesa iz bilo kog razloga. Na primer, kod problema Hanojske kule, korisnik može da poželi da prekine demonstraciju zato što hoće da proveri svoje razumevanje rešenja. Postoje komplikacije uslovljene načinom na koji računari izvršavaju programe, koje se javljaju kada je potrebno da se iskoči iz više nivoa rekurzivnih poziva odjednom. Primetimo ipak da dobijeni niz koji proizvodi algoritam konverzije ima pogrešan redosled: sve cifre se prvo računaju i onda upisuju u niz tako što je poslednja cifra prva. Rekurzivna implementacija sa ovim lako izlazi na kraj. Sa svakim pozivom funkcije Conversion, računar pravi novo okruženje u kojem se pamte vrednosti koje se predaju M i N i novoizračunato S. Po okončanju poziva funkcije, t.j. po povratku iz funkcije, nalazimo da je okruženje isto kao što je bilo i pre poziva. Rekurzivne funkcije implicitno pamte sekvence obrade. Eliminisanje rekurzivnih poziva podrazumeva da moramo izračunate cifre da sačuvamo eksplicitno i da ih kasnije vratimo obrnutim redom. U računarskoj nauci se ovaj mehanizam naziva LIFO (Last In First Out) – poslednji koji je ušao, prvi izlazi. Ovaj mehanizam se najbolje implementira pomoću strukture podataka tipa stek. Stek ima samo dve operacije: push (stavi na stek) and pop (izvadi sa steka). Intuitivno, stek se može vizualizovati kako gomila objekata koji su složeni jedan preko drugog. Ako je potreban neki određeni objekat moraju se prvo ukloniti svi objekti iznad njega. Očigledno je da je jedini objekat koji može odmah da se izvadi, onaj koji je na gomilu poslednji stavljen. Iterativna implementacija funkcije Conversion mogla bi da izgleda kao što je prikazano niže.

 1 String Conversion(int M, int N) // враћа стринг, осим два цела броја 
 2 {  
 3     Stack stack = new Stack(); // креира стек
 4     while (M >= N) // јасно се види петља која се понавља
 5     {  
 6         stack.push(M mod N); // ускладишти цифру
 7         M = M/N; // find new M 
 8     }  
 9     // сада треба скупити све цифре заједно  
10     String str = new String(""+M); // креирати стринг са једном цифром M 
11     while (stack.NotEmpty())  
12         str = str+stack.pop() // узети са стека следећу цифру 
13     return str;  
14 }

Najbliži par tačaka

Ako želite da iz nekog skupa tačaka u ravni nađete par tačaka koje su najbliže, treba da uporedite svaku tačku sa svakom drugom u vremenu $O(n^{2})$, ili da upotrebite algoritam podeli i pobedi.

Uvod

Pristup „grubom silom“ problemu najbližeg para (t.j. provera svakog mogućeg para tačaka) koristi kvadratno vreme. Želeli bi sada da predstavimo brži „podeli i vladaj“ algoritam za rešavanje problema najbližeg para. Za zadati skup tačaka u ravni S, naš pristup će biti podelimo skup na dva približno jednaka dela (S1 i S2) za koje već imamo rešenje i onda da spojimo polovine u linearnom vremenu da bi dobili jedan O(nlogn) algoritam. Međutim, stvarno rešenje je daleko od očiglednog. Moguće je da traženi par ima jednu tačku u S1, a drugu u S2. Ne prisiljava li nas ovo da ponovo proverimo sve moguće parove tačaka? Pristup podeli i vladaj, koji je ovde prikazan, predstavlja direktnu generalizaciju jednodimenzijalnog algoritma koji je opisan u prethodnom primenom odeljku.

Najbliži par u ravni

U redu, generalizovaćemo naš jednodimenzionalni 1-D algoritam koliko god je moguće direktnije (pogledaj sliku 3.2). Dati skup tačaka S u ravni delimo na dva skupa S1 i S2 vertikalnom linijom l takvom da su tačke iz S1 levo od l, a one iz S2 desno od l. Sada rekurzivno rešavamo problem nad ova dva skupa i dobijamo minimalna rastojanja d1 (za S1) i d2 (za S2). Dopustićemo da je d njihov minimum. Sada, isto kao i u slučaju 1-D, ako se najbliži par celog skupa sastoji iz po jedne tačke iz svakog podskupa, onda ove dve tačke moraju da budu u okviru d od l. Ova zona je predstavljena sa dve trake P1 i P2 sa obe strane od l. Do sada smo bili potpuno u korak sa slučajem 1-D. Sada, međutim, dopunska dimenzija prouzrokuje probleme. Želimo da utvrdimo da li je neka tačka, recimo iz P1, udaljena manje od d od druge tačke iz P2. Međutim u ravni mi nemamo luksuz koji smo imali na liniji, kada smo videli da samo jedna tačka u svakom skupu može da bude u okviru d od srednje linije. U stvari, u dve dimenzije, sve tačke mogu da budu u traci! Ovo je katastrofalno, zato što ćemo morati da upoređujemo n2 parova tačaka da bi spojili skup, i stoga nam naš algoritam podeli i vladaj neće pružiti veću efikasnost. Srećom, sada možemo da napravimo još jednu spasonosnu opservaciju. Za svaku pojedinu tačku p u jednoj traci, samo tačke iz druge trake koje odgovaraju sledećim ograničenjima moraju da se provere:

• one tačke u okviru d od p u pravcu druge trake
• one u okviru d od p u pravcu pozitivne i negativne y ose.

Jednostavno zato što tačke van ovog graničnog okvira ne mogu biti manje d udaljene od p (vidi sliku 3.3). Tako se dešava, da zato što je svaka tačka u graničnom okviru najmanje udaljena za d, u okviru može da bude samo šest tačaka. Sada nema potrebe da se proverava svih n2 tačaka. Sve što treba da uradimo je da sortiramo tačke iz trake po njihovim y koordinatama i da redom skeniramo tačke proveravajući svaku tačku u odnosu na maksimum 6 susednih. Ovo znači da je najviše 6*n poređenja potrebno da bi se proverili parove kandidate. Međutim, pošto smo sortirali tačke iz trake po njihovim y koordinatama, proces spajanja naša dva skupa nije linearan, već uzima O(nlogn) vremena. Stoga naš kompletan algoritam još uvek nije O(nlogn), ali je ipak poboljšanje u odnosu na kvadratne performanse pristupa grubom silom (kao što ćemo videti u sledećem odeljku). U odeljku 3.4, pokazaćemo kako da se ovaj algoritam napravi da bude još efikasniji, potkrepljivanjem našeg rekurzivnog podrešenja.

Kratak pregled i analiza 2-D algoritama

Ovde ćemo korak po korak, predstaviti kratak pregled algoritma prikazanog u prethodnom odeljku, a zatim i analizu njegovih performansi. Algoritam je jednostavno napisan u obliku liste, zato što smatram da je pseudo-kod opterećujući i nepotreban za razumevanje algoritma. Primetite da smo pre-sortirali tačke po njihovim x koordinatama i sačuvali posebnu strukturu koja sadrži tačke sortirane po vrednostima y (za korak 4), koje za sebe uzimaju O(nlogn) vremena. ClosestPair (najbliži par) skupa tačaka:

1. Podelite skup na dva jednaka dela linijom l i rekurzivno izračunajte minimalnu razdaljinu u svakom delu.
2. Neka je d minimum dva minimalna rastojanja.
3. Eliminišite tačke koje leže dalje od d u odnosu na l.
4. Razmotrite preostale tačke u odnosu na njihove y koordinate.
5. Skenirajte ostale tačke uređene po y i izračunajte rastojanje svake tačke u odnosu na susedne koje su udaljene ne više od d (zato nam je potrebno da budu pre-sortirane po y). Primetite da nema više od takvih tačaka (vidi prethodni odeljak).
6. Ako je bilo koje od ovih rastojanja manje od d, ažurirajte vrednost d.

Analiza:

• Efikasnost algoritma ćemo označiti sa T(n)
• Korak 1 uzima 2T(n/2) (primenjujemo algoritam na obe polovine)
• Korak 3 uzima O(n) vremena
• Korak 5 uzima O(n) vremena (kao što smo videli u predhodnom odeljku)

tako da je,

$T(n)=2T(n/2)+O(n)$

što prema Glavnoj teoremi, rezultira sa:

$T(n)\in O(nlogn)$ Stoga nad spajanjem pod-rešenja dominira sortiranje u koraku 4 i stoga i zato uzima O(nlogn) vremena. Kod algoritma podeli i vladaj, ovo mora da se ponovi jedanput za svaki nivo rekurzije i stoga ceo algoritam ClosestPair troši O(logn*nlogn) = O(nlog2n) vremena.

Usavršavanje algoritma

Možemo malo da poboljšamo algoritam smanjenjem vremna potrebnog za sortiranje po y koordinati u koraku 4. To se radi tako što se traži da rekurzivno rešenje u koraku 1 vraća tačke sortirane po njihovim y koordinatama. To će dati dve sortirane liste tačaka koje samo treba spojiti (linearna vremenska funkcija) u koraku 4 da bi se dobila kompletna sortirana lista. Stoga revidirani algorita ukučuje sledeće izmene: Korak 1: Step 1: Podeli skup na ..., i rekurzivno izračunaj razdaljinu u svakom od delova, vraćajući tačke u skupu sortirane y koordinati. Korak 4: Spojiti dve sortirane liste u vremenu O(n). Kao što se vidi procesom spajanja sada dominiraju koraci linearnog vremena čime se dobija O(nlogn) algoritam za nalaženje najbližeg para iz skupa tačaka u ravni.

Problem Hanojskih kula

Postoji n diskova različite veličine i tri klina. Diskovi su postavljeni na levi klin redosledom koji je određen njihovom veličinom. Najmanji je na vrhu, dok je najveći na dnu. Cilj igre je da se svi diskovi premeste sa levog klina.

Pravila

1) U savom koraku može da se premesti samo jedan disk 2) Samo disk koji je na vrhu može da se premešta. 3) Svaki disk može da se postavi samo na veći disk.

Rešenje

Intuitivna ideja Da bi premestili najveći disk sa levog klina na srednji, prvo treba premestiti manje diskove na desni klin. Pošto je najveći disk premešten, manji diskovi mogu da se premeste sa desnog na srednji klin.

Rekurentnost

Pretpostavimo da je n broj diskova. Da bi premestili n diskova sa klina a na klin b potrebno je: 1) za n>1 treba premstiti n-1 diskova sa klina a na klin c 2) premestiti n-i disk sa klina a na klin b 3) za n>1 premestiti n-1 diskova sa klina c na klin a

Pseudokod

void hanoi(n,src,dst){
  if (n>1)
    hanoi(n-1,src,pegs-{src,dst});
  print "move n-th disc from src to dst";
  if (n>1)
    hanoi(n-1,pegs-{src,dst},dst);
}

Analiza

Analiza je trivijalna. $T(n)=2T(n-1)+O(1)=O(2^{n})$

---