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;
}
}
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
wylicz1(t,0,2)
/ \
/ \
wylicz2(t,0,1) wylicz5(t,2,2)
/ \
/ \
wylicz3(t,0,0) wylicz4(t,1,1)
Program wypisze: wynik = 1
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) (*)
4 ; n = 1
f(n) =
8 + f((n+1)/2) + f(n/2) ; n > 1
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
1. a/2 - 2b/2 = (a - 2b)/2 2. 2a/2 - b/2 = (2a - b + 1)/2
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
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
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.
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
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)
f(n) = 12n - 8 = Θ(n) "f jest dokładnie rzędu n"
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...
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) (*)
3 ; n = 1
g(n) =
6 + f((n+1)/2) + f(n/2) ; n > 1
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
1. a/2 - 2b/2 = (a - 2b)/2 2. 2a/2 - b/2 = (2a - b + 1)/2
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
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
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
g(n) = 9n - 6 = Θ(n) "g jest dokładnie rzędu n"