Analiza algoritama, rekurentne relacije

Definicija: Neka su f i g dve pozitivne funkcije od n ∈ N. Kaže se da je f(n) = O(g(n)) ako postoje pozitivne konstante c i n₀ takve da za svako n > n₀ važi f(n) ≤ c ⋅ g(n)

Neke osobine O(…):

Važi sledeće:

O(f(n)) + O(g(n)) = O(f(n) + g(n))
O(f(n)) ⋅ O(g(n)) = O(f(n) ⋅ g(n))

Ali ne važi:

O(f(n)) - O(g(n)) = O(f(n) - g(n))
O(f(n)) / O(g(n)) = O(f(n) / g(n))

Definicija: Za funkciju g(n) kaže se da je asimptotska donja granica funkcije f(n) i piše se f(n) = Ω(g(n)) ako postoje pozitivne konstante c i n₀ takve da za svako n > n₀ važi f(n) > c ⋅ g(n).

Definicija: Ako za dve funkcije f i q važi i f(n) = O(g(n)) i f(n) = Ω(g(n)), onda pišemo f(n) = Θ(g(n)).

Master teorema

     T(n) = a T(n/p) + f(n),  a ≥ 1, p > 1

n je veličina problema
a broj podproblema u rekurziji
n/p veličina svakog podproblema
f(n) složenost algoritma van rekurzivnog poziva

Slučaj 1

Ako je f(n) ∈ O(nᶜ), gde je c < logₚa, onda:

    T(n) ∈ Θ(nᶜ), gde je c = logₚa

Slučaj 2

Ako je za neko k ≥ 0

    f(n) ∈ Θ(nᶜlogᵏn), gde je c = logₚa

onda:

    T(n) ∈ Θ(nᶜ logᵏ⁺¹n)

Slučaj 3

Ako je

    f(n) ∈ Ω(nᶜ), gde je c > logₚa

    af(n/b) ≤ kf(n) za neko k < 1 i dovoljno veliko n

onda važi:

    T(n) ∈ Θ(f(n))

Zadaci

Zadatak 1

Navesti primer dve monotono rastuće funkcije f(n) i g(n), takve da nije ni f(n) = O(g(n)), ni g(n) = O(f(n)).

Rešenje: Funkcije biramo tako da jedna od njih raste za parne, a druga za neparne vrednosti broja n. Na primer:

           ⎧ n!         , n parno
    f(n) = ⎨
           ⎩ (n-1)! + 1 , n neparno

           ⎧ (n-1)! + 1 , n parno
    g(n) = ⎨
           ⎩ n!         , n neparno

Tada je:

    f(n)   ⎧ (1 + 1/(n-1)!)⁻¹ ⋅ n   , n parno
    ———— = ⎨
    g(n)   ⎩ (1 + 1/(n-1)!)   / n   , n neparno

Tako da ni f(n) / g(n), ni g(n) / f(n) nisu ograničene funkcije.

Zadatak 2

Ako elementi niza aₙ zadovoljavaju relaciju:

    aₙ₊₂ + baₙ₊₁ + caₙ = 0,  n ≥ 0

gde su b i c konstante, i važi a₀ = 0, a₁ = 1, a₂ = 4, i a₃ = 37, odrediti aₙ.

Uputstvo: Raspisati jednačinu za n = 0 i n = 1 i odatle naći a, b i c. Onda rešiti odgovarajuću rekurentnu jednačinu. Konačno rešenje: aₙ = 1 / 10 (7ⁿ - (-3)ⁿ).

Zadatak 3

Naći rekurentnu relaciju za broj nizova binarnih brojeva dužine n koji nemaju susedne nule.

Uputstvo: Za n ≥ 1, označimo sa aₙ broj takvih nizova dužine n. Označimo sa aₙ⁽⁰⁾ broj onih koji se završavaju nulom, a sa aₙ⁽¹⁾ broj onih koji se završavaju jedinicom.

Važi aₙ = aₙ⁽⁰⁾ + aₙ⁽¹⁾ i a₁ = 2.

Ukoliko se broj x dužine n - 1 završava jedinicom, možemo dodati 0 ili 1 na njegov kraj. Ukoliko se završava nulom, možemo na kraj dodati jedino jedinicu. Ova dva slučaja iscrpljuju sve mogućnosti, a disjunktni su, pa važi:

    aₙ = 2aₙ₋₁⁽¹⁾ + aₙ₋₁⁽⁰⁾

Ako posmatramo proizvoljni niz y uračunat u aₙ₋₂, tada je y1 uračunat u aₙ₋₁⁽¹⁾, a važi i obratno -- ako je broj z1 uračunat u aₙ₋₁⁽¹⁾, onda je z uračunato u aₙ₋₂, to jest:

    aₙ₋₂ = aₙ₋₁⁽¹⁾

Odatle sledi:

    aₙ = 2aₙ₋₁⁽¹⁾ + aₙ₋₁⁽⁰⁾
       = aₙ₋₁⁽¹⁾ + (aₙ₋₁⁽¹⁾ + aₙ₋₁⁽⁰⁾)
       = aₙ₋₁⁽¹⁾ + aₙ₋₁
       = aₙ₋₂ + aₙ₋₁

Početne vrednosti, a₁ = 2 i a₂ = 3.

Zadatak 4

Rešiti rekurentnu jednačinu:

    (aₙ₊₂)² - 5(aₙ₊₁)² + 4(aₙ)² = 0,   n ≥ 2

gde su a₀ = 4 i a₁ = 13.

Uputstvo: Uvesti smenu bₙ = aₙ².

Zadatak 5

Rešiti rekurentnu jednačinu:

           n-1
    T(n) =  Σ  T(i) + 1,    n ≥ 2
           i=1

ako je T(1) = 1.

Uputstvo: Oduzeti T(n - 1) od T(n).

Zadatak 6

Rešiti rekurentnu jednačinu:

    T(n) = 2T(n/2) + 6n - 1,    n ≥ 2

ako je T(1) = 1.

Uputstvo: ukoliko je potrebno samo asimptotsko ponašanje, možemo iskoristiti master teoremu. Inače moramo da raspišemo sumu, uočimo pravilnost i dokažemo formulu. Konačno rešenje: T(n) = 6n · log(n) + 1

Zadatak 7

Rešiti rekurentnu jednačinu:

    T(n) = 3T(n − 1) + 4n − 2, n ≥ 2

gde je T(1) = 2.

Uputstvo: oduzeti od T(n) vrednost T(n − 1).

Zadatak 8

Problem Pₙ sa parametrom n ∈ N rešava se primenom algoritama A i B. Algoritam A rešava Pₙ za n > 1 primenom algoritma B na Pₙ₋₁, pri čemu se na svodjenje problema troši n vremenskih jedinica. Algoritam B rešava Pₙ za n > 1 primenom algoritma A na Pₙ₋₁, pri čemu se na svodjenje problema troši n vremenskih jedinica. Problem P₁ algoritam A rešava direktno za jednu vremensku jedinicu, a algoritam B za dve vremenske jedinice.

Izračunati vreme izvršavanja algoritma A pri rešavanju problema Pₙ.

Rešenje: Neka je aₙ vreme potrebno algoritmu A da reši problem Pₙ, a bₙ vreme potrebno algoritmu B da reši problem Pₙ.

Važi:

    aₙ = bₙ₋₁ + n, a₁ = 1
    bₙ = aₙ₋₁ + n, b₁ = 2

Odavde se dobija:

    bₙ₋₁ = aₙ₋₂ + (n - 1)

odnosno:

    aₙ = aₙ₋₂ + (n - 1) + n = aₙ₋₂ + 2n - 1

Razlikujemo dva slučaja - kada je indeks paran i kada je neparan:

    a₂ₙ₊₁ = a₂ₙ₋₁ + 2(2n + 1) - 1
          = a₂ₙ₋₃ + (4n + 1) + (4n - 3) = …
          = a₁ + (4n + 1) + (4n - 3) + … + 5
               n
          = a₁ Σ (4i + 1),   i = 1 .. n
              i=1
          = 1 + 3n + 2n²
          = O(n²)

      a₂ₙ = …
                n-2
          = a₂ + Σ (4i + 7)
                i=0
          = 2n² + n + 1
          = O(n²)

Zadatak 9:

Dokazati da važi: n²/2 - 3n = Θ(n²)

Zadatak 10:

Dokazati da važi: n2ⁿ = O(3ⁿ)

Zadatak 11:

Rešiti rekurentnu jednačinu:

    T(n) = 2T(n − 1) + 3n + 1, n ≥ 2

gde je T(1) = 5.

Zadatak 12:

Rešiti rekurentnu jednačinu:

    T(n) = T(n − 3) + 5n − 9, n ≥ 4

gde je T(1) = 1, T(2) = 6 i T(3) = 13.