powrót

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

  1. Potęga iteracyjnie a^n:
    a ∈ R
n ∈ N
POTEGA(a, n)
	pot = 1
	for i = 1 to n
		pot = pot * a
	return pot
  2. 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
  3. Potęga rekurencyjnie a^n:
    a ∈ R
n ∈ N
POTEGA(a, n)
	if n = 0
		return 1
	else
		return a * POTEGA(a, n - 1)

Szacowanie funkcji

  1. f(n) = 13n2 + 4n - 73
  2. f(n) = (n2 + 1)(2n4 + 3n - 8)
  3. f(n) = (n3 + 3n - 1)4
  4. f(n) = sqrt(n + 1)
  5. f(n) = (n2 - 1)7
  6. f(n) = sqrt(n2 - 1)
  7. f(n) = sqrt(n2 + n)
  8. f(n) = (n2 + n + 1)(n3 + 5)
  9. f(n) = 3n
  10. f(n) = 2n + 1
  11. f(n) = 22n
  12. f(n) = (n + 1)2
  13. f(n) = (200n)2

Notacje asymptotyczne

Twierdzenie o rekurencji uniwersalnej

Przykłady:

  1. T(n)=9T(n/3)+n
  2. T(n)=T(2n/3)+1
  3. T(n)=3T(n/4)+nlgn
  4. T(n)=2T(n/2)+nlgn
  5. T(n)=4T(n/2)+n
  6. T(n)=T(n-1)+1
  7. T(n)=4T(n/2)+n2
  8. T(n)=4T(n/2)+n3
  9. T(n)=2T(n/2)+n2
  10. T(n)=T(9n/10)+n
  11. T(n)=16T(n/4)+n2
  12. T(n)=7T(n/3)+n2
  13. T(n)=2T(n/4)+√n
  14. T(n)=T(n-1)+n
  15. T(n)=9T(n/3)+n3
  16. T(n)=T(n/3)+1
  17. T(n)=16T(n/4)+nlgn
  18. T(n)=2T(n/2)+5n-15
  19. T(n)=2T(n/3)+nlgn