Dany jest program Zadanie zawierający metodę wylicz.
public class Zadanie
{
public static void main(String[] args)
{
int[] t = {1,2,3,4};
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 3
t --> [1][2][3][4]
t.length = 4
Analizujemy wywołanie wylicz(t,0,3).
• wylicz1(t,0,3) = 1 0 == 3 false s = (0 + 3) / 2 = 1 w1 = wylicz2(t,0,1) = 1 w2 = wylicz5(t,2,3) = 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,3) = 3 2 == 3 false s = (2 + 3) / 2 = 2 w1 = wylicz6(t,2,2) = 3 w2 = wylicz7(t,3,3) = 4 return min(w1,w2) = 3
• wylicz6(t,2,2) = 3 2 == 2 true return t[2] = 3
• wylicz7(t,3,3) = 4 3 == 3 true return t[3] = 4
wylicz1(t,0,3) n = 4
/ \
/ \
wylicz2(t,0,1) wylicz5(t,2,3) n = 2
/\ /\
/ \ / \
wylicz3(t,0,0) wylicz4(t,1,1) wylicz6(t,2,2) wylicz7(t,3,3) n = 1
Program wypisze: wynik = 1
f(n) - złożoność obliczeniowa wywołania wylicz(t,l,p), gdzie:
n = p - l + 1
n = 2k, k ∈ N ∪ {0}
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,3)
f(4) = 3 + 1 + 1 + (1 + f(2)) + (1 + f(2)) + 1 = 8 + f(2) + f(2)
...
• wylicz(t,l,p)
f(n) = 3 + 1 + 1 + [1 + f(n/2)] + [1 + f(n/2)] + 1 = 8 + f(n/2) + f(n/2) (*)
4 ; n = 1
f(n) =
8 + 2f(n/2) ; n > 1 ∧ n = 2k
s - l + 1 = (l + p)/2 - 2(l - 1)/2 = * = (l + p - 2l + 2)/2 = (p - l + 1 + 1)/2 = (n + 1)/2 = (2k + 1)/2 = 2k-1 = n/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 + 2f(n/2) ; n > 1 ∧ n = 2k
f(n) = 8 + 2f(n/2) = 8 + 2(8 + 2f(n/4)) =
8 + 2*8 + 4f(n/4) = 8 + 2*8 + 4(8 + 2f(n/8)) =
8 + 2*8 + 4*8 + 8f(n/8) = 8 + 2*8 + 4*8 + 8(8 + 2f(n/16)) =
8 + 2*8 + 4*8 + 8*8 + 16f(n/16) = *
Z: n/2k = 1 => n = 2k
* = 8(1 + 2 + 4 + 8 + ... + 2k-1) + 2kf(n/2k) = **
Sm = a1*(1 - qm)/(1 - q) - wzór na sumę wyrazów ciągu geometrycznego
m - liczba wyrazów ciągu geometrycznego, które sumujemy
a1 = 1 Sk = 1*(1 - 2k)/(1 - 2) = 2k - 1
q = 2
m = k
** = 8(2k - 1) + 2kf(n/2k) = 8(n - 1) + n*f(1) = 8n - 8 + 4n = 12n - 8
f(n) = 12n - 8 = Θ(n) "f jest dokładnie rzędu n"
g(n) - złożoność pamięciowa wywołania wylicz(t,l,p), gdzie:
n = p - l + 1
n = 2k, k ∈ N ∪ {0}
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(4) = 3 + 1 + (1 + g(2)) + (1 + g(2)) = 6 + g(2) + g(2)
...
• wylicz(t,l,p)
g(n) = 3 + 1 + [1 + g(n/2)] + [1 + g(n/2)] = 6 + g(n/2) + g(n/2) (*)
3 ; n = 1
g(n) =
6 + 2f(n/2) ; n > 1 ∧ n = 2k
s - l + 1 = (l + p)/2 - 2(l - 1)/2 = * = (l + p - 2l + 2)/2 = (p - l + 1 + 1)/2 = (n + 1)/2 = (2k + 1)/2 = 2k-1 = n/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 + 2g(n/2) ; n > 1 ∧ n = 2k
g(1) = 3 g(2) = 6 + 2g(1) = 6 + 2*3 g(4) = 6 + 2g(2) = 6 + 2(6 + 2*3) = 6 + 2*6 + 2*2*3 g(8) = 6 + 2g(4) = 6 + 2(6 + 2*6 + 2*2*3) = 6 + 2*6 + 2*2*6 + 2*2*2*3 g(16) = 6 + 2g(8) = 6 + 2(6 + 2*6 + 2*2*6 + 2*2*2*3) = 6 + 2*6 + 2*2*6 + 2*2*2*6 + 2*2*2*2*3 ... g(2k) = 6(1 + 2 + 4 + 8 + ... + 2k-1) + 3*2k = 6(2k - 1) + 3*2k = 6*2k - 6 + 3*2k = 9*2k - 6 = 9n - 6 ... g(n) = 9n - 6
g(n) = 9n - 6 = Θ(n) "g jest dokładnie rzędu n"