Ćwiczenia 4 - Złożoność algorytmów

1. Minimum liczb a; b ∈ R
   

   MIN(a, b)
   	if a < b
   		return a
   	else
   		return b
   

2. Znajdź element tablicy T

   T.length ∈ N
   T[i] ∈ R
   x ∈ R
   ZNAJDZ-ELEMENT(T, x)
   	i = 1
   	while A[i] ≠ x AND i ≠ n
   		i = i + 1
   	if A[i] ≠ x
   		write "nie znaleziono"
   	else
   		write i
   

3. Znajdź element tablicy uporządkowanej T

   T.length ∈ N
   T[i] ∈ R
   x ∈ R
   ZNAJDZ-ELEMENT(T, x)
   	l = 1
   	p = n
   	repeat
   		s = (l + p) DIV 2
   		if x > A[s]
   			l = s + 1
   		else
   			p = s - 1
   	until T[s] = x OR l > p
   	if T[s] = x
   		write s
   	else
   		write "nie znaleziono"
   T[n] = T[n/2] + 1
   a = 1
   b = 2
   f(n) = 1
   
   

4. Potęga iteracyjnie a^n

   a ∈ R
   n ∈ N
   POTEGA(a, n)
   	pot = 1
   	for i = 1 to n
   		pot = pot * a
   	return pot
   

5. Potęga binarnie a^n

   a ∈ R
   n ∈ N
   POTEGA(a, n)
   	i = n
   	pot = 1
   	pod = a
   	while i ≠ 0
   		if i MOD 2 ≠ 0
   			pot = pot * pod
   		pod = pod * pod
   		i = i DIV 2
   	return pot
   

6. Potęga rekurencyjnie a^n

   a ∈ R
   n ∈ N
   POTEGA(a, n)
   	if n = 0
   		return 1
   	else
   		return n * POTEGA(n - 1)
   

Notacje asymptotyczna

Twierdzenie o rekurencji uniwersalnej

Przykłady: