#Проектное решение

Задача называется NP-промежуточной
====
если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время
====
если она принадлежит классу NP и не является NP-полной. Для некоторых NP задач (изоморфизм графов, минимизация булевой функции, ...) не доказана (на данный момент) их принадлежность классу NP-полных.
====
если для неё существует такая NP-полная задача, которая сводиться к C за полиномиальное время (алгоритмическая сводимость по Куку).
++++
Задача C называется NP-трудной
====
если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время
====
если она принадлежит классу NP и не является NP-полной. Для некоторых NP задач (изоморфизм графов, минимизация булевой функции, ...) не доказана (на данный момент) их принадлежность классу NP-полных.
====
#если для неё существует такая NP-полная задача, которая сводиться к C за полиномиальное время (алгоритмическая сводимость по Куку).
++++
Какова вычислительная сложность алгоритма цифровой сортировки?
====
#линейная 
====
квадратичная 
====
кубическая 
++++
Эффективность алгоритма цифровой сортировки зависит
====
от типизации данных 
====
#от плотности элементов в массиве ячеек 
====
от метода формирования идентификаторов 
++++
Алгоритм сортировки, в котором сортируемые элементы делятся на конечное число отдельных блоков так, что все элементы в одном блоке всегда больше (или меньше), чем в другом, носит название
====
структурная сортировка 
====
#блочная сортировка 
====
массивная сортировка 
++++
Сколько сравнений и обращений к памяти требуется в связных списках при обращении к элементу по его номеру?
====
#n/2
====
2n 
====
logn 
++++
Cложность алгоритма сортировки односвязного списка составляет
====
O(n) 
====
O(logn)