Zadanie z połowieniem tablicy - metoda dokładna

Zadanie

Dany jest program Zadanie zawierający metodę wylicz.

public class Zadanie
{
  public static void main(String[] args)
  {
    int[] t = {1,2,3};
    
    System.out.println("wynik = " + wylicz(t,0,t.length-1));
  }
  
  static int wylicz(int[] tab, int l, int p)
  {
    if (l == p) return tab[l];
    
    int s = (l + p) / 2;
    
    int w1 = wylicz(tab,l,s);
    int w2 = wylicz(tab,s+1,p);
    
    if (w1 < w2)
      return w1;
    else
      return w2;
  }
}
  1. jaki wynik wypisze powyższy program
  2. sformułuj i rozwiąż równanie rekurencyjne opisujące złożoność czasową metody wylicz oraz podaj rząd tej złożoności
  3. sformułuj i rozwiąż równanie rekurencyjne opisujące złożoność pamięciową metody wylicz oraz podaj rząd tej złożoności

Ad. a

       0  1  2
t --> [1][2][3] 

t.length = 3

Analizujemy wywołanie wylicz(t,0,2).

• wylicz1(t,0,2) = 1
  0 == 2 false
  s = (0 + 2) / 2 = 1
  w1 = wylicz2(t,0,1) = 1
  w2 = wylicz5(t,2,2) = 3
  return min(w1,w2) = 1

• wylicz2(t,0,1) = 1
  0 == 1 false
  s = (0 + 1) / 2 = 0
  w1 = wylicz3(t,0,0) = 1
  w2 = wylicz4(t,1,1) = 2
  return min(w1,w2) = 1

• wylicz3(t,0,0) = 1
  0 == 0 true
  return t[0] = 1

• wylicz4(t,1,1) = 2
  1 == 1 true
  return t[1] = 2

• wylicz5(t,2,2) = 3
  2 == 2 true
  return t[2] = 3

Graf wywołań rekurencyjnych

                    wylicz1(t,0,2)
                         / \
                        /   \
          wylicz2(t,0,1)     wylicz5(t,2,2)
               / \
              /   \
wylicz3(t,0,0)     wylicz4(t,1,1)

Odp:

Program wypisze: wynik = 1

Ad. b

f(n) - złożoność obliczeniowa wywołania wylicz(t,l,p), gdzie:

       n = p - l + 1
       0 <= l <= p < t.length

Rozpatrujemy dwa przypadki: 

1. l = p

   • wylicz(t,0,0)

     f(1) = 3 + 1 = 4

2. l < p

   • wylicz(t,0,1)

     f(2) = 3 + 1 + 1 + (1 + f(1)) + (1 + f(1)) + 1 = 8 + f(1) + f(1)

   • wylicz(t,0,2)

     f(3) = 3 + 1 + 1 + (1 + f(2)) + (1 + f(1)) + 1 = 8 + f(2) + f(1)
   
   ...

   • wylicz(t,l,p)

     f(n) = 3 + 1 + 1 + [1 + f((n+1)/2)] + [1 + f(n/2)] + 1 = 8 + f((n+1)/2) + f(n/2) (*)

Równanie rekurencyjne

       4                       ; n = 1
f(n) =
       8 + f((n+1)/2) + f(n/2) ; n > 1

Uzasadnienie dla (*)

s - l + 1 = (l + p)/2 - l + 1 = (l + p)/2 - 2(l - 1)/2 = * = (l + p - 2l + 2)/2 = (p - l + 1 + 1)/2 = (n + 1)/2

* korzystamy z tw. 1

p - (s + 1) + 1 = p - s = 2p/2 - (l + p)/2 = ** = (2p - l - p + 1)/2 = (p - l + 1)/2 = n/2

** korzystamy z tw. 2

Twierdzenia

1. a/2 - 2b/2 = (a - 2b)/2

2. 2a/2 - b/2 = (2a - b + 1)/2

Dowód 1.

a/2 - 2b/2 = (a - 2b) / 2

Z: a = 2k

   a/2 - 2b/2 = 2k/2 - 2b/2 = k - b
   (a - 2b)/2 = (2k - 2b)/2 = 2(k - b)/2 = k - b

Z: a = 2k + 1

   a/2 - 2b/2 = (2k + 1)/2 - 2b/2 = k - b
   (a - 2b)/2 = (2k + 1 - 2b)/2 = (2(k - b) + 1)/2 = k - b

Dowód 2.

2a/2 - b/2 = (2a - b + 1)/2

Z: b = 2k

   2a/2 - b/2 = 2a/2 - 2k/2 = a - k
   (2a - b + 1)/2 = (2a - 2k + 1)/2 = (2(a - k) + 1)/2 = a - k
   
Z: b = 2k + 1

   2a/2 - b/2 = 2a/2 - (2k + 1)/2 = a - k
   (2a - b + 1)/2 = (2a - (2k + 1) + 1)/2 = (2a - 2k - 1 + 1)/2 = 2(a - k)/2 = a - k

Rozwiązanie równania

       4                       ; n = 1
f(n) =
       8 + f((n+1)/2) + f(n/2) ; n > 1

Sposób I

f(1) = 4
f(2) = 8 + f(1) + f(1) = 8 + 4 + 4
f(3) = 8 + f(2) + f(1) = 8 + (8 + 4 + 4) + 4
f(4) = 8 + f(2) + f(2) = 8 + 8 + 4 + 4 + 8 + 4 + 4
f(5) = 8 + f(3) + f(2) = 8 + 8 + 8 + 4 + 4 + 4 + 8 + 4 + 4
...
f(2k+1) = 8 + f(k+1) + f(k)
f(2k)   = 8 + f(k) + f(k)
...
f(n) = 8(n - 1) + 4n = 12n - 8

Sposób II

Zakładamy: n = 2k, gdzie k ∈ N \ {0}.

(n + 1)/2 = (2k + 1)/2 = 2k-1 = n/2

Zatem równanie rekurencyjne przyjmuje postać:

       4           ; n = 1
f(n) =
       8 + 2f(n/2) ; n > 1 ∧ n = 2k

Wyznaczamy rozwiązanie, które można znaleźć na poprzedniej stronie i otrzymujemy:

f(n) = 12n - 8

Wykazujemy indukcyjnie, że funkcja f(n) spełnia również pierwotne równanie rekurencyjne.

Dowód indukcyjny

1. f(1) = 4
   f(1) = 12*1 - 8 = 4
   
2. Z: f(n) = 12n - 8
   T: f(n+1) = 12(n + 1) - 8
   
Dowód:

   f(n+1) = 8 + f((n+2)/2) + f((n+1)/2) = 8 + 12((n+2)/2) - 8 + 12((n+1)/2) - 8 = 12((n+2)/2) + 12((n+1)/2) - 8 = *

Z1: n + 1 = 2k

        * =  12((2k+1)/2) + 12((2k)/2) - 8 = 12k + 12k - 8 = 12*2k - 8 = 12(n + 1) - 8

Z2: n + 1 = 2k + 1

        * =  12((2k+2)/2) + 12((2k+1)/2) - 8 = 12(k+1) + 12k - 8 = 12(2k+1) - 8 = 12(n + 1) - 8

Dowód funkcyjny

1. f(1) = 4
   f(1) = 12*1 - 8 = 4
   
2. Wykażemy, że rozwiązanie f(n) = 12n - 8 spełnia równanie funkcyjne f(n) = 8 + f((n+1)/2) + f(n/2)

Z1: n = 2k

   8 + f((2k+1)/2) + f(2k/2) = 8 + f(k) + f(k) = 8 + 12k - 8 + 12k - 8 = 12*2k - 8 = 12n - 8 = f(n)

Z2: n = 2k + 1

   8 + f((2k+2)/2) + f((2k+1)/) = 8 + f(k+1) + f(k) = 8 + 12k + 12 - 8 + 12k - 8 = 12(2k+1) - 8 = 12n - 8 = f(n)

Odp:

f(n) =  12n - 8 = Θ(n) "f jest dokładnie rzędu n"

Zadanie - test rozwiązania

Poniższy program pozwala zweryfikować poprawność rozwiązania. 

/* ZadanieTest.java */

public class ZadanieTest
{
  public static void main(String[] args)
  {
    int n = 256;
    
    int[] t = new int[n];
    
    for (int p = 0; p < t.length; p++) wylicz(t,0,p);
    
    if (rowne) System.out.println("z(n) = f(n) = r(n) dla n = 1.." + n);
  }
 
  private static boolean rowne = true;
  
  static int wylicz(int[] tab, int l, int p)
  {
    wy(tab,l,p);
    
    if (zCzasowa != f(p - l + 1)) rowne = false;
    if (zCzasowa != r(p - l + 1)) rowne = false;
    
    zCzasowa = 0;

    if (l == p) return tab[l];
    
    int s = (l + p) / 2;
    
    int w1 = wylicz(tab,l,s);
    int w2 = wylicz(tab,s+1,p);
    
    if (w1 < w2)
      return w1;
    else
      return w2;
  }
  
  private static int zCzasowa;
  
  static int wy(int[] tab, int l, int p)
  {
    zCzasowa = zCzasowa + 4;
    
    if (l == p) return tab[l];
    
    int s = (l + p) / 2;
    
    int w1 = wy(tab,l,s);
    int w2 = wy(tab,s+1,p);
    
    zCzasowa = zCzasowa + 4;
    
    if (w1 < w2)
      return w1;
    else
      return w2;
  }
  
  static int f(int n)
  {
    return 12*n - 8;
  }
  
  static int r(int n)
  {
    if (n == 1)
    {
      return 4;
    }
    else
    {
      return 8 + r((n + 1) / 2) + r(n/2);
    }
  }
}

z(n) = f(n) = r(n) dla n = 1..256
Press any key to continue...

Ad. c

g(n) - złożoność pamięciowa wywołania wylicz(t,l,p), gdzie:

       n = p - l + 1
       0 <= l <= p < t.length

Rozpatrujemy dwa przypadki: 

1. l = p

   • wylicz(t,0,0)

     g(1) = 3

2. l < p

   • wylicz(t,0,1)

     g(2) = 3 + 1 + (1 + g(1)) + (1 + g(1)) = 6 + g(1) + g(1)

   • wylicz(t,0,2)

     g(3) = 3 + 1 + (1 + g(2)) + (1 + g(1)) = 6 + g(2) + g(1)
   
   ...

   • wylicz(t,l,p)

     g(n) = 3 + 1 + [1 + g((n+1)/2)] + [1 + g(n/2)] = 6 + g((n+1)/2) + g(n/2) (*)

Równanie rekurencyjne

       3                       ; n = 1
g(n) =
       6 + f((n+1)/2) + f(n/2) ; n > 1

Uzasadnienie dla (*)

s - l + 1 = (l + p)/2 - l + 1 = (l + p)/2 - 2(l - 1)/2 = * = (l + p - 2l + 2)/2 = (p - l + 1 + 1)/2 = (n + 1)/2

* korzystamy z tw. 1

p - (s + 1) + 1 = p - s = 2p/2 - (l + p)/2 = ** = (2p - l - p + 1)/2 = (p - l + 1)/2 = n/2

** korzystamy z tw. 2

Twierdzenia

1. a/2 - 2b/2 = (a - 2b)/2

2. 2a/2 - b/2 = (2a - b + 1)/2

Dowód 1.

a/2 - 2b/2 = (a - 2b) / 2

Z: a = 2k

   a/2 - 2b/2 = 2k/2 - 2b/2 = k - b
   (a - 2b)/2 = (2k - 2b)/2 = 2(k - b)/2 = k - b

Z: a = 2k + 1

   a/2 - 2b/2 = (2k + 1)/2 - 2b/2 = k - b
   (a - 2b)/2 = (2k + 1 - 2b)/2 = (2(k - b) + 1)/2 = k - b

Dowód 2.

2a/2 - b/2 = (2a - b + 1)/2

Z: b = 2k

   2a/2 - b/2 = 2a/2 - 2k/2 = a - k
   (2a - b + 1)/2 = (2a - 2k + 1)/2 = (2(a - k) + 1)/2 = a - k
   
Z: b = 2k + 1

   2a/2 - b/2 = 2a/2 - (2k + 1)/2 = a - k
   (2a - b + 1)/2 = (2a - (2k + 1) + 1)/2 = (2a - 2k - 1 + 1)/2 = 2(a - k)/2 = a - k

Rozwiązanie równania

       3                       ; n = 1
g(n) =
       6 + g((n+1)/2) + g(n/2) ; n > 1

g(1) = 3
g(2) = 6 + g(1) + g(1) = 6 + 3 + 3
g(3) = 6 + g(2) + g(1) = 6 + 6 + 3 + 3 + 3
g(4) = 6 + g(2) + g(2) = 6 + 6 + 3 + 3 + 6 + 3 + 3
...
g(2k+1) = 6 + g(k+1) + g(k)
g(2k)   = 6 + g(k) + g(k)
...
g(n) = 6(n - 1) + 3n = 9n - 6

Odp:

g(n) =  9n - 6 = Θ(n) "g jest dokładnie rzędu n"

Strona główna