Iteraatio vs rekursio¶

Iteratiiviset ongelmat voidaan vaihtaa rekursioon ja päinvastoin. Molempiin voidaan käyttää joko pala kerrallaan tai hajoita ja hallitse strategioita.

Tarkastele esimerkiksi alle olevia Search ja BinarySearch algoritmeja.

Search

1
2
3
4
5
6
7

  Search(Int a, Array N):
   FOR elem IN N:
     IF elem == a:
       return true
     END IF
   END LOOP
   return false

Binary search

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

  BinarySearch(A, left, right, value)
   (A in ascending order)
   if left = right then
     if A[left] = value then
         return true
     else
         return false
   else
     middle := ⌊(left+right)/2⌋
     if value ≤ A[middle] then
         return BinarySearch(A, left, middle, value)
     else
         return BinarySearch(A, middle+1, right, value)

Ensimmäinen käyttää iteraatiota, toinen rekursiota. Toinen ero näiden kahden algoritmin välillä on tehokkuus: logaritminen BinarySearch-algoritmi on asymptoottisesti tehokkaampi kuin lineaarinen Search-algoritmi. Toisaalta, Search-algoritmi ei aseta ennakkoehtoja järjestykselle, jossa alkiot ovat ennen hakua. BinarySearch-algoritmi käyttää hajoita ja hallitse -periaatetta, jonka hyödyt tulevat selvemmiksi, mitä enemmän aineistoa täytyy käydä läpi.

searchSmallestMissingIteration()¶

Toteuta algoritmi searchSmallestMissingIteration() tiedostoon wk02_decrease_or_divide/missing/missing.cc.

int searchSmallestMissingIteration(int* arr, int size) {
  // returns the first missing number, or NO_VALUE_MISSING if not found
  return NO_VALUE_MISSING;
}

Parametri arr on taulukko, jota tarkastellaan, ja size on tämän taulukon koko.

Kirjoita ratkaisusi funtiolle searchSmallestMissingIteration() C++ -kielellä käyttäen pala kerrallaan strategiaa.

searchSmallestMissing()¶

Toteuta algoritmi searchSmallestMissing() tiedostoon wk02_decrease_or_divide/missing/missing2.cc.

int searchSmallestMissing(int* A, int left, int right) {
  // returns the first missing number, or NO_VALUE_MISSING if not found
  return NO_VALUE_MISSING;
}

Parametrit:

• A taulukko, jota tarkastellaan
• left vasemmanpuoleisin taulukon indeksi, alussa 0
• right oikeanpuoleisin taulukon indeksi, alussa size-1 kun size on taulukon koko.

Kirjoita ratkaisusi funtiolle searchSmallestMissing() C++ -kielellä käyttäen hajoita ja hallitse strategiaa.

Pikajärjestäminen¶

Lomitusjärjestäminen¶