Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов

• Название: Методические указания по проведению практических работ по дисциплине Теория алгоритмов
• Анкор: Класс
• Дата: 14.11.2019
• Размер: 3.39 Mb.
• Имя файла: МУПР ОП.08 Теория алгоритмов.doc
• Тип: Методические указания; #95109
• страница: 28 из 29

Задание 2. Решить данное рекуррентное соотношение и определить эффективность алгоритма, описанного функцией T(n). Задание выполните по вариантам.

Для своего варианта – столбец A, выбрать рекуррентное уравнение и значение T(1).

Таблица 1. Задание на лабораторную работу №8

A	Уравнение	T(1)	A	Уравнение	T(1)
1	T(n)=3T(n/2)+n	2	18	T(n)=3T(n-1)+	9
2	T(n)=2T(n-1)+2	2	19	T(n)=3T(n/2)+n	9
3	T(n)=T(n/2)+	5	20	T(n)=3T(n-1)+9	1
4	T(n)=2T(n/2)+n	2	21	T(n)=2T(n/2)+	2
5	T(n)=T(n/2)+logn	1	22	T(n)=2T(n/2)+n	1
6	T(n)=9T(n/2)+	9	23	T(n)=T(n/2)+3logn	3
7	T(n)=2T(n/2)+5	3	24	T(n)=8T(n/2)+	2
8	T(n)=3T(n/2)+n	3	25	T(n)=T(n/2)+9	3
9	T(n)=16T(n-1)+4	3	26	T(n)=3T(n/2)+n	4
10	T(n)=T(n-1)+3n	3	27	T(n)=2T(n-1)+9	1
11	T(n)=2T(n/2)+n	8	28	T(n)=2T(n-1)+3n	6
12	T(n)=4T(n/2)+2	8	29	T(n)=2T(n/2)+n	4
13	T(n)=3T(n/2)+	3	30	T(n)=(T(n-1))2	4
14	T(n)=2T(n/2)+	4	31	T(n)=T(n/2)+2	1
15	T(n)=2T(n/2)+logn	2	32	T(n)=2T(n/2)+	16
16	T(n)=(T(n-1))2	4	33	T(n)=T(n/2)+2logn	2
17	T(n)=4T(n/2)+4	4	34	T(n)=2T(n-1)+2	2

Продолжение таблицы 1

A	Уравнение	T(1)	A	Уравнение	T(1)
35	T(n)=(T(n-1))2	9	43	T(n)=3T(n/2)+3	3
36	T(n)=T(n-1)+3n3	3	44	T(n)=3T(n/2)+n	8
37	T(n)=3T(n/2)+n	1	45	T(n)=3T(n-1)+2	10
38	T(n)=4T(n-1)+2	8	46	T(n)=2T(n-1)+2n	2
39	T(n)=2T(n/2)+3n3	1	47	T(n)=2T(n/2)+n	3
40	T(n)=2T(n/2)+n	64	48	T(n)=9T(n/2)+1	3
41	T(n)=9T(n/2)+logn	3	49	T(n)=T(n/2)+5 n3	5
42	T(n)=4T(n/2)+ n2	4	50	T(n)=6T(n/2)+ n2	8

Итог работы: решение задачи, защита