Алгоритмы обработки данных

Cрок выполнения : 20.01

Вид работы : Контрольная

Дисциплины:
Математические: Логика, теория Алгоритмов и Автоматов.

Добавлен 13.01.2024 08:05:06

Уникальность:

Доработка:

Подробно: 2. Расположите следующие функции по порядку в соответствии с нотацией большого О (обоснуйте это расположение). Сгруппируйте, например, с помощью подчеркивания, функции, которые являются ? оценкой друг другу: 1) 10 n log n; 2) 2100; 3) 200logn; 4) n 2n; 5) log(n!); 6) n!; 7) nlog log n. 3. Для каждой функции f(n) = {log n, n1/2, n, n log n, n2, 2n, n!} и времени t (1 секунда, 1 час, 1 неделя, 1 год, 1 столетие) определите наибольший размер n задачи, которая может быть решена за время t, при условии, что для ее решения алгоритму необходимо f(n) микросекунд. Результат представьте в виде таблицы. 4. Покажите, что для любых действительных констант a и b, где a, b > 0, справедливо соотношение (n+a)b= ? (nb). 5. Пусть f(n) и g(n) – асимптотически положительные функции. Докажите или опровергните справедливость каждого из приведенных ниже утверждений: 1) f(n) = O (f(n)2); 2) из f(n) = O (g(n)) следует, что g(n) = ? (f(n)); 3) f(n) = ? (f(n/2)); 4) из f(n) + o(f(n))= ?(f(n)). 6. Выразите функцию f(n)=3n2/1000+10 n logn+200 n+3 в ? обозначениях. 7. С помощью метода рекурсивных деревьев, докажите, что решение рекуррентного соотношения T (n) = T (n/3) + T (2n/3) + c n ведет себя как ? (n logn), где с – константа. 8. Определите верхнюю и нижнюю асимптотические границы функции T (n) для каждого из представленных ниже рекуррентных соотношений. Считаем, что T (n) – константа при достаточно малых n. Обоснуйте свой ответ. 1) T (n) = 2 T (n/2)+ n3; 2) T (n) = 7 T (2n/5)+ n2; 3) T (n) = 2 T (n/4)+ n1/2.

Кратко: 2. Расположите следующие функции по порядку в соответствии с нотацией большого О (обоснуйте это расположение). Сгруппируйте, например, с помощью подчеркивания, функции, которые являются ? оценкой друг другу: 1) 10 n log n; 2) 2100; 3) 200logn; 4) n 2n; 5) log(n!); 6) n!; 7) nlog log n. 3. Дл...