Вопросы

1. Какие предварительные шаги предпринимаются для оценки вычислительной сложности алгоритма?

2. На какие две группы разбиваются арифметические операции? Почему?

3. Какие наборы данных желательно найти при оценке вычислительной сложности алгоритма?

4. Что называется скоростью роста алгоритма?

5. Что такое порядок вычислительной сложности алгоритма? Как он оценивается?

6. Что представляет из себя последовательный поиск информации, двоичный поиск, выборка?

_{Литература}

1. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. – М.: Техносфера, 2004. – 368 с.

2. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Изд-во Наследие. Диалог-Сибирь, 2003. – 108 с.

3. Деммель Дж. Вычислительная линейная алгебра / Дж.Деммель; пер.с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 430 с.

4. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.

5. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.

_{Лекция 5. Сложностные классы задач}

_План

1. Класс р - задачи с полиномиальной сложностью

2. Класс np - полиномиально проверяемые задачи

1. Класс р - задачи с полиномиальной сложностью

_{В начале 1960 г., в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?}

_{Задача называется полиномиальной, т.е. относится к классу Р, если существует константа и алгоритм, решающий эту задачу за время (количество арифметических операций) , где - длина входа алгоритма (например, при решении системы линейных уравнений вход – это матрица и вектор правой части, - размерность СЛАУ). Отметим, что класс задач Р определяется через существование полиномиального по времени алгоритма ее решения, при этом неявно предполагается худший случай по времени для всех различных входов длины (например, при решении однородной квадратной СЛАУ ее матрица может оказаться невырожденной, тогда ее решение только тривиальное – нулевое, оно находится без вычислений, но в общем случае при решении прямыми методами ).}

_{Задачи класса Р – это интуитивно задачи, решаемые за реальное время. Для большинства реальных задач из класса Р константа .}

_{Рассмотрим примеры алгоритмов сортировки. Благодаря значительной экономии времени при двоичном поиске по сравнению с последовательным поиском разработчики программного обеспечения нередко предпочитают хранить информацию в отсортированном виде. Все рассматриваемые ниже алгоритмы будут сортировать список в порядке возрастания ключевого значения. Тип ключа может быть самым разным - целым, символьной строкой или еще чем-то более сложным- будем пользоваться некоторой стандартной операцией сравнения двух ключей. Для простоты предполагается, что все ключевые значения в списке попарно различны.}

_{Сортировка вставками. Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место, а не произвольно, а затем снова сортировать весь список. Сортировка вставками считает первый элемент любого списка отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. Теперь можно вставить третий элемент исходного списка в отсортированный двухэлементный список. Этот процесс повторяется до тех пор, пока все элементы исходного списка не окажутся в расширяющейся отсортированной части списка.}

_{Алгоритм, реализующий сортировку вставками:}

_{list – сортируемый массив элементов, N – количество элементов в массиве}

_{для i=2 до N}

_{newelement=list(i)}

_loc=i-1

_{делать пока (loc>=1&list(loc)>newelement)}

_{list(loc+1)=list(loc)}

_loc=loc-1

_{конец внутреннего цикла}

_{list(loc+1)= newelement}

_{конец внешнего цикла}

_{Этот алгоритм заносит новое вставляемое значение в переменную newelement, затем он освобождает место для этого нового элемента, подвигая во внутреннем цикле все большие элементы на одну позицию в массиве.}

_{Анализ наихудшего случая. Если посмотреть на внутренний цикл, то видно, что наибольшее количество операций выполняется в случае, если вновь добавляемый элемент меньше всех элементов, содержащихся в уже отсортированной части массива. В этой ситуации выполнение цикла завершается, когда значение loc=0. Поэтому наибольшее количество работы алгоритм произведет, когда всякий новый элемент добавляется в начало списка. Такое возможно только, если исходный список упорядочен по убыванию. Посмотрим, как происходит обработка такого списка. Первым вставляется второй элемент списка. Он сравнивается всего с одним элементом. Второй вставляемый элемент (третий по порядку) сравнивается с двумя предыдущими, третий – с тремя предыдущими и т.д., т.е. i-ый вставляемый элемент сравнивается с i предыдущими элементами, и этот процесс повторяется N-1 раз. Таким образом, вычислительная сложность сортировки вставками в наихудшем случае равна}

_,

_{т.е. алгоритм сортировки вставками имеет полиномиальную сложность.}

_{Пузырьковая сортировка. Основной принцип – выталкивание маленьких значений на вершину списка в то время, как большие значения опускаются вниз. У пузырьковой сортировки есть много различных вариантов.}

_{Алгоритм пузырьковой сортировки совершает несколько проходов по списку. При каждом проходе происходит сравнение соседних элементов. Если порядок соседних элементов неправильный, то они меняются местами. Каждый проход начинается с начала списка. Сперва сравниваются первый и второй элементы, затем второй и третий и т.д. При обнаружении на первом проходе наибольшего элемента, он будет переставляться со всеми последующими элементами, пока не дойдет до конца списка. Поэтому при втором проходе нет необходимости производить сравнение с последним элементом. При втором проходе второй по величине элемент списка опустится во вторую позицию с конца. При прохождении процесса на каждом проходе по крайней мере одно из следующих по величине значений встает на свое место. При этом меньшие значения тоже собираются наверху. Если при каком-то проходе не произошло ни одной перестановки элементов, то все они стоят в нужном порядке, и исполнение алгоритма можно прекратить. Стоит заметить, что при каждом проходе ближе к своему месту продвигается сразу несколько элементов, хотя гарантированно занимает свое место лишь один.}

_{Анализ наихудшего случая. Наихудший случай – упорядоченный по убыванию исходный массив. Если наибольший элемент стоит первым, то он будет переставляться со всеми остальными элементами вплоть до конца списка. Перед первым проходом второй по величине элемент занимает вторую позицию, однако в результате первого сравнения он переставляется на первое место. В начале второго прохода на первой позиции уже находится второй по величине элемент, и он переставляется со всеми остальными элементами вплоть до предпоследнего. Этот процесс повторяется для всех остальных элементов. Сколько сравнений выполняется в наихудшем случае? На первом проходе - N-1 сравнение, на втором - N-2 и т.д. Поэтому сложность в наихудшем случае дается как .}