Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Можно показать, что это нижняя граница
3 n2 –100 n+6 ¹ V(n3 )при С = 1.
Неравенство 3 n2 –100 n+6 ³ n3 не выполняется.
3 n2 –100 n+6= V(n)
C1 = , n> n0 .
https://pandia.ru/text/78/183/images/image007_89.gif "width="305"height="247 src=">
f1 (Н)=100 н2
f2 (Н)=5 n3
n0 =20 –критическая точка.
Другая причина предпочтения алгоритмов меньшей сложности заключается в том, что чем ниже порядок сложности, тем больше проблема. N практически разрешима.
0 "style =" margin-left: 5.4pt; собрать границу: собрать; предел: нет ">
н!
Пример 6:
Краткое содержание
Следует помнить, что большой порядок возрастания сложности алгоритмов, как правило, имеет меньшую константу. C1 характеризуется постоянным увеличением сложности по сравнению с C2.
В этом случае алгоритм быстро возрастающей сложности ( n® 0 ) может быть предпочтительнее для решения задач малого масштаба.
Задача в P называется NP-трудной, если ее решение имеет полиномиальный DA (PDA), из которого можно получить решение всех задач, входящих в NP, то есть такая задача является NP-трудной, если она является хотя бы любой задачей в НП так сложно, как
NP-сложная задача, связанная с NP, называется NP-полной задачей, таких задач не меньше, чем любой NP-задачи. Более того, наличие КПК для NP-трудной или NP-полной задачи означает, что классы P и NP совместимы, то есть все задачи класса 3 могут быть решены быстрым алгоритмом.
Для доказательства того, что задача является NP-трудной, необходимо показать, что если для задачи существует КПК, то с его помощью можно получить решение другой КПК задач, входящих в NP.
Чтобы определить, является ли задача NP-полной, нужно доказать, что она принадлежит NP.
Идея использования алгоритма решения одной задачи для получения алгоритма решения другой — один из важнейших алгоритмов в теории алгоритмов.
Определение 1: Задача R1 трансформируется в задачу R2, если любой частный случай задачи R1 можно преобразовать в какой-то частный случай задачи R2 за полиномиальное время. Тогда решение R1 может быть получено из решения частного случая задачи R2 за полиномиальное время.