Алгоритмы полиномиальной сложности (класс Р)

Большинство алгоритмов имеют полиномиальный порядок сложности. Иногда время работы оказывается линейным, как при последовательном поиске: при удлинении списка данных вдвое алгоритм работает вдвое дольше. В алгоритмах последовательного поиска нас интересует процесс просмотра списка в поисках некоторого элемента, называемого целевым. При последовательном поиске предполагается, что список не отсортирован. Например, ключевое значение может быть номером сотрудника, фамилией, или любым другим уникальным идентификатором. Алгоритм последовательного поиска последовательно просматривает по одному элементу списка, начиная с первого, до тех пор пока не найдет нужный элемент. Очевидно, что чем дальше в списке находится конкретное значение ключа, тем больше времени уйдет на его поиск.

Очень часто встречаются алгоритмы сложности – такую сложность имеют некоторые алгоритмы сортировки: если длину входного списка удвоить, то время работы алгоритма возрастет в 4 раза. Все восемь существующих алгоритмов сортировки демонстрируют широкий спектр возможных вариантов поведения. Первая из них, сортировка вставками, сортирует список, вставляя очередной элемент в нужное место уже отсортированного списка. Пузырьковая сортировка сравнивает элементы попарно, переставляя между собой элементы тех пар, порядок в которых нарушен. Сортировка Шелла представляет собой многопроходную сортировку, при которой список разбивается на подсписки, каждый из которых сортируется отдельно, причем на каждом проходе число подсписков уменьшается, а их длина растет.

Рассмотрим наиболее типичный вариант сортировки – пузырьковую сортировку. Алгоритм пузырьковой сортировки совершает несколько проходов по списку. При каждом проходе происходит сравнение соседних элементов. Если порядок соседних элементов неправильный, они меняются местами. Каждый проход начинается с начала списка. Сперва сравниваются 1 и 2 элементы, затем 2 и 3, потом 3 и 4 и т.д. Элементы с неправильным порядком в паре переставляются. При обнаружении на первом проходе наибольшего элемента списка он будет переставляться со всеми последующими пока не дойдет до конца списка. Поэтому при втором проходе нет необходимости производить сравнение с последним элементом. При втором проходе второй по величине элемент списка опустится во вторую позицию с конца и т.д. Стоит заметить, что при каждом проходе ближе к своему месту продвигается сразу несколько элементов, хотя гарантировано занимает окончательное положение лишь один.

Сколько сравнений выполняется в наихудшем случае. На первом проходе будет выполнено сравнений соседних значений, на втором сравнений. Дальнейшее исследование показывает, что при каждом очередном проходе число сравнений уменьшается на 1. Поэтому сложность в наихудшем случае дается формулой

Сложность стандартного алгоритма матричного умножения равна и при увеличении размеров матриц вдвое такой алгоритм работает в 8 раз дольше.

Матрица – математический объект, эквивалентный двумерному массиву. Если число столбцов в первой матрице совпадает с числом строк во второй, то эти две матрицы можно перемножить:

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

Сводя три результата воедино, имеем следующую таблицу:

	Умножение	Сложение
Стандартный алгоритм
Алгоритм Виноградова
Алгоритм Штрассена

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