2.5. Понятие сложности задачи

Приобретаемый в процессе активной деятельности личный опыт формирует у человека интуитивное представление о сложности задачи, которую ему предстоит решить. Это представление имеет относительный характер, иначе говоря, сложность задачи определяется в сравнении с подобными задачами, которые приходилось решать ранее. Известно, что интуитивное представление о сложности задачи не всегда адекватно, а если поставлена существенно незнакомая проблема, то оно может оказаться совершенно ложным.

Таким образом, определение сложности задачи играет важную роль на этапе подготовки к ее решению, поскольку именно в этот промежуток времени, обычно небольшой, необходимо с максимально возможной точностью сформировать заказ на ресурсы, которые могут потребоваться в процессе решения – на время, на денежные и технические средства, на количество и квалификацию помощников.

Вообще сложностью задачи называют выраженную в виде функции от размерности входных данных верхнюю границу числа операций, необходимых для выполнения этой задачи. Если задача формализована, то ее сложность можно определить как сложность наилучшего известного алгоритма для ее решения.

Для произвольной задачи обязательно должны быть поставлены следующие вопросы:

- до какой степени можно улучшать метод ее решения;

- позволяет ли определение степени сложности каким-либо образом классифицировать задачи;

- возможно ли построить способ перехода от более трудной задачи к более простой?

По сложности процедуры решения задачи разделяют на три основных класса:

- линейной сложности, или класс L;

- полиномиальной сложности, или класс Р;

- экспоненциальной сложности, или класс Е.

Задачи класса L – наилучшие для решения, потому что имеют наименьшую сложность. Количество операций в процедуре их решения пропорционально размерности входных данных.

В этот класс попадают все арифметические операции, извлечение квадратного корня, решение систем уравнений с двумя и тремя переменными, решение квадратного и кубического уравнений. Размерность входных данных здесь практически всегда – это длина использованных в постановке задачи чисел.

К классу P относят задачи, для которых известен алгоритм со сложностью, пропорциональной nm, где n – размерность входных данных, а m – постоянная, не зависящая от n величина, характерная для определенного вида задачи.

Ниже приведен ряд задач полиномиальной сложности:

- задача сортировки;

- задача поиска эйлерова цикла на графе;

- поиск некоторого слова в тексте длиной n символов;

- поиск кратчайшего пути на графе;

- линейное программирование.

Задачи класса E представляют наибольшую сложность в решении. Для нахождения ответа на такую задачу необходимо выполнить fn операций, причем n – размерность входных данных, а f может быть константой, полиномом или сложным фукционалом.

Примеры задач экспоненциальной сложности:

- построение всех подмножеств данного множества;

- задачи распознавания правильных выражений в несложных языках.

Кроме перечисленных трех классов задач встречается еще один, специальный класс NP, класс недетерминированных полиномиальных задач. Для всех задач этого класса известны методы решения экспоненциальной сложности, но одновременно доказана их общность и имеется обоснованное предположение, что для них может быть построен более простой способ решения.

К задачам класса NP относятся, в частности:

- решение систем уравнений с целыми переменными, известная задача Диофанта, датируемая 410 г;

- построение цикла Гамильтона, то есть цикла, проходящего по одному разу через все вершины данного графа;

- составление расписаний и раскрасок;

- ряд задач оптимизации;

- ряд задач диагностики.

Пример 2.15

Рассмотрим известную задачу сортировки. Задача ставится следующим образом: дан набор объектов, различающихся по какому-либо параметру, причем этот параметр может быть выражен числом. Необходимо расставить объекты в порядке возрастания или убывания численного значения параметра.

Для решения этой задачи обычно применяется известный алгоритм пузырьковой сортировки. Вот как он выглядит для сортировки по убыванию набора из n объектов. Берут первый объект из набора и последовательно сравнивают его с остальными, выбираемыми из этого набора. Если при очередном сравнении первый объект оказывается меньше выбранного, то первый объект кладут на место выбранного и продолжают поиск, но уже для выбранного объекта. Таким образом, после выполнения первой процедуры из n-1 сравнений выбранным оказывается объект с наибольшим значением параметра, его помещают на первое место. Затем берут второй объект и повторяют процедуру поиска наибольшего среди оставшихся, выполняя n-2 сравнений. Процедура будет завершена после выполнения (n-1)+(n-2)+(n-3)+...+(n-(n-1))=n(n-1)/2 сравнений. Для того чтобы рассортировать 10 объектов, требуется 45 операций сравнения. Соответственно, сложность этого алгоритма оценивается как n(n-1)/2, где n – количество объектов в сортируемом наборе.

Существует алгоритм, требующий меньшего числа сравнений. Принцип его заключается в том, что необходимо последовательно сравнить соседние пары объектов, затем сравнить соседние пары наибольших значений предыдущих сравнений и так далее, получая пирамиду, сходящуюся к максимальному числу. Такой алгоритм имеет сложность , однако реализовать его непросто.

Если сравнить зависимости n(n-1)/2 и , можно заметить, что последняя растет медленнее, но при малых n превышает первую. Для числа объектов меньше семи пузырьковая сортировка работает быстрее.

Оптимальный алгоритм сортировки выглядит следующим образом. Разделить сортируемый набор на шесть групп или менее. Если в каждой группе получилось значительно больше шести объектов, повторить разбиение групп. Внутри каждой группы выполнить пузырьковую сортировку. Дальнейший поиск наибольшего выполнять только внутри “среза”, объединяющего объекты с наибольшими параметрами из каждой группы. Пояснение приведено на рис. 2.10.

Такой алгоритм может быть реализован без значительных проблем, однако только в том случае, если приблизительно известно число элементов в наибольшем из обрабатываемых множеств. Если количество элементов в обрабатываемом множестве неизвестно, то может понадобиться двукратное и более повторение описанной процедуры для того, чтобы в сортируемой группе не было больше шести элементов. Это требование принципиально усложняет алгоритм, однако его можно не выполнять, ограничившись схемой рис. 2.10 для множества любого размера. При этом скорость алгоритма не будет наилучшей, но сортировка выполнится быстрее пузырьковой.

Рассмотрим множество из тридцати элементов. Пузырьковый алгоритм потребует выполнить 30×29/2=435 операций сравнения. Выполняя усовершенствованный метод, придется выполнить пять сортировок в группах из шести элементов и затем, в худшем случае, для выбора каждого из первых двадцати пяти – по четыре сравнения, а для оставшихся пяти еще четыре, три, два и одно. Итого: 5×6×5/2+25×4+4+3+2+1=185, то есть решение будет получено более чем в два раза быстрее. На больших группах экономия времени будет еще значительнее.

Рис. 2.10. Оптимальная процедура сортировки большого набора