Задания для самостоятельной работы

№ варианта	Фамилия	№ варианта	Фамилия
1.	Фарафонов	2.	Отрубенко
3.	Дмитриева	4.	Осинный
5.	Давлетшин	6.	Любицкий
7.	Ильницкая	8.	Силаков
9.	Шакирова	10.	Стариков
11.	Харченко

1. Проверить утверждения с помощью определения.

№ варианта	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.	11.
№ задания	a,b,c,p	d,e,f,q	g,h,i,r	j,k, l,s	t,m,n,o	a,d,g,p	b,f,h,q	k,n,e,r	c,f,g,s	i,l, n,t	a,h,o,p

a) 17 = O( 1 );

b) N(N — 1)/2 = O(N²);

c) 2^{2 N} = O( 2 ^N);

d) logN = O(N);

e) N logN = O(N ² );

f) N ln N = O(N ^3/2 );

g) 3N³ + 2N² = O(N²);

h) N logN + 5 = O(N);

i) 2 ^N + N ³ = O( 2 ^N);

j) f(N) = O(f(N));

k) f(N) = O(f(N)²);

l) (N + 1) log N = O(N);

m) ;

n) ;

o)

p) N³ + 2N² = Ω(N²);

q)

r) N log N = Ω(N²);

s) 3N² + 2N — 5 = Ω(N);

t) N + log N = Ω(log N).

 

2. Пусть время работы алгоритма Т(N) = O(f(N)). Если X элементов обрабатываются за Y мсек., то во сколько раз следует ожидать увеличения времени выполнения при обработке Z элементов?

№ варианта	f(N)	X	Y	Z	№ варианта	f(N)	X	Y	Z
1.	N2				2.	N3
3.	N				4.	2N
5.	N3				6.	logN
7.	2N				8.
9.	logN				10.	logN
11.					12.	N3

 

3. Найти наиболее точную оценку для рекуррентных отношений.

№ варианта	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.	11.
№ задания	a,b,c,p	d,e,f,q	g,h,i,p	j,k, l,q	p,m,n,o	a,d,g,q	b,f,h,p	k,n,e,q	c,f,g,p	i,l, n,q	a,h,o,p

 

a) T(N) = 3 T(N /2 ) + N, T(1) = 1;

b) T(N) = 3 T(N /2 ) + N ², T(1) = 1;

c) T(N) = 8 T(N /2 ) + N ³, T(1) = 1;

d) T(N) = 2 T(N /2 ) + N logN, T(1) = 1;

e) T(N) = 9T(N/2) + N³, T(1) = 1;

f) Т(1) = 1, Т(N) = 2T(N/2) + 1, при N > 1;

g) T(N) = 3T(N/2) + N², T(1) = 1;

h) T(N) = 3T(N/2) + N logN, Т(N) — константа при N ≤ 8;

i) T(N) = 16T(N/4) + N², если Т(N) — константа при N ≤ 2;

j) T(N) = 9T(N/2) + N², T(1) = 1;

k) T(N) = 7T(N/2) + N², если Т(N) — константа при N ≤ 2;

l) T(N) = 2T(N/4) + N^1/2, если Т(N) — константа при N ≤ 2;

m) T(N) = 2T(N/4) + , T(1) = 1;

n) T(N) = 2T(N/2) + N logN, если Т(N) — константа при N ≤ 2;

o) T(N) = T(9N/10) + N; если Т(N) - константа при N ≤ 2;

p) T(N) = 2 T(N — 1) + 1, T(1) = 2;

q) T(N) = 2T(N — 1) + N, T(1) = 2.

---

Дата добавления: 2015-12-17; просмотров: 11; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!