Анализ трудоёмкости алгоритмов Анализ трудоёмкости алгоритмов позволяет найти оптимальный алгоритм для решения данной задачи. трудоемкость алгоритма количество. - презентация

1

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

3 Трудоёмкость алгоритмов по-разному зависит от входных данных. только от объёма данных от значений данных от порядка поступления Для некоторых алгоритмов трудоемкость зависит только от объёма данных, для других алгоритмов от значений данных, иногда – от порядка поступления данных. многих алгоритмов может зависеть Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов. Трудоёмкость алгоритмов по-разному зависит от входных данных. только от объёма данных от значений данных от порядка поступления Для некоторых алгоритмов трудоемкость зависит только от объёма данных, для других алгоритмов от значений данных, иногда – от порядка поступления данных. многих алгоритмов может зависеть Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов. Анализ трудоёмкости алгоритмов

4 Это один из упрощенных видов анализа алгоритмов. при больших объёмах входных данных. Целью асимптотического анализа является сравнение затрат времени (и других ресурсов) различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объёмах входных данных. В асимптотическом анализе оценка функции трудоёмкости сложность алгоритма. В асимптотическом анализе оценка функции трудоёмкости называется сложность алгоритма. Она позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объёма данных. Это один из упрощенных видов анализа алгоритмов. при больших объёмах входных данных. Целью асимптотического анализа является сравнение затрат времени (и других ресурсов) различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объёмах входных данных. В асимптотическом анализе оценка функции трудоёмкости сложность алгоритма. В асимптотическом анализе оценка функции трудоёмкости называется сложность алгоритма. Она позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объёма данных. Анализ трудоёмкости алгоритмов – асимптотический анализ

5 оценкой функции сложности алгоритма f(n) В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Основной оценкой функции сложности алгоритма f(n) является оценка, где n величина объёма данных (длина входа). функция g(n) является асимптотически точной оценкой функции f(n) Говорят, что функция g(n) является асимптотически точной оценкой функции f(n) при достаточно больших n f(n) будет заключена междуи если c 1 g 1 (n) f(n) c 2 g 2 (n) Т.Е. при достаточно больших n f(n) будет заключена междуи оценкой функции сложности алгоритма f(n) В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Основной оценкой функции сложности алгоритма f(n) является оценка, где n величина объёма данных (длина входа). функция g(n) является асимптотически точной оценкой функции f(n) Говорят, что функция g(n) является асимптотически точной оценкой функции f(n) при достаточно больших n f(n) будет заключена междуи если c 1 g 1 (n) f(n) c 2 g 2 (n) Т.Е. при достаточно больших n f(n) будет заключена междуи Асимптотический анализ

6 f(n) Оценка функции f(n)

7 функция g(n) асимптотически точной оценкой функции f(n), функция f(n) не отличается от функции g(n) с точностью до постоянного множителя. Говорят ещё, что функция g(n) является асимптотически точной оценкой функции f(n), так как по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя. дает одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности.

8 f(n) Оценка О функции f(n) верхнюю асимптотическую оценку Оценка О представляет собой верхнюю асимптотическую оценку трудоемкости алгоритма. Запись функция g(n) является верхней асимптотической оценкой функции f(n)функция g(n) является верхней асимптотической оценкой функции f(n) f(n) c g(n) f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя. означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя. верхнюю асимптотическую оценку Оценка О представляет собой верхнюю асимптотическую оценку трудоемкости алгоритма. Запись функция g(n) является верхней асимптотической оценкой функции f(n)функция g(n) является верхней асимптотической оценкой функции f(n) f(n) c g(n) f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя. означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя.

9 f(n) Оценка О функции f(n)

10 класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя. Оценка задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя. не медленнее обозначает класс функций, которые растут не медленнее, чем В этот класс попадают и все степенные функции с основанием большим единицы В этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы. f(n) Оценка функции f(n)

11

12 Равенство выполняется тогда и только тогда, когда И Равенство выполняется тогда и только тогда, когда И

13 Классификация задач по классам сложности Классификация задач по классам сложности – (P-сложные, NP-сложные, экспоненциально сложные и др.).P-сложныеNP-сложные P п (машины Тьюринга); К классу P относятся задачи, которые могут быть решены за время, п полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (машины Тьюринга); NP п недетерминированной вычислительной машины, а к классу NP задачи, которые могут быть решены за пполиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими.

14 История вопроса В начале 1960-х годов о границах практической применимости алгоритмов смысле ограничений на ее размерность Какие задачи за реальное время В начале 1960-х годов в связи с началом широкого использования вычислительной техники для решения практических задач возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), в которых были введены классы сложности задач. В начале 1960-х годов о границах практической применимости алгоритмов смысле ограничений на ее размерность Какие задачи за реальное время В начале 1960-х годов в связи с началом широкого использования вычислительной техники для решения практических задач возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), в которых были введены классы сложности задач.

15 Класс P (задачи с пполиномиальной сложностью) пполиномиальной (относится к классу P) Задача называется пполиномиальной (относится к классу P), если константа k алгоритм F a O k существуют константа k и алгоритм, решающий задачу с F a ( n ) = O ( n k ), где n - длина входа алгоритма. пполиномиальной (относится к классу P) Задача называется пполиномиальной (относится к классу P), если константа k алгоритм F a O k существуют константа k и алгоритм, решающий задачу с F a ( n ) = O ( n k ), где n - длина входа алгоритма.

16 интуитивно задачи, решаемые за реальное время. Задачи класса P – это интуитивно задачи, решаемые за реальное время. преимущества алгоритмов из этого класса: Отметим следующие преимущества алгоритмов из этого класса: k < 6 1. для большинства задач из класса P константа k < 6 ; 2. класс P инвариантен по модели вычислений (для широкого класса моделей); 3. класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином). задачи класса P «практически разрешимой» задачи. Таким образом, задачи класса P - уточнение определения «практически разрешимой» задачи. интуитивно задачи, решаемые за реальное время. Задачи класса P – это интуитивно задачи, решаемые за реальное время. преимущества алгоритмов из этого класса: Отметим следующие преимущества алгоритмов из этого класса: k < 6 1. для большинства задач из класса P константа k < 6 ; 2. класс P инвариантен по модели вычислений (для широкого класса моделей); 3. класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином). задачи класса P «практически разрешимой» задачи. Таким образом, задачи класса P - уточнение определения «практически разрешимой» задачи.

17 Класс NP (пполиномиально проверяемые задачи) Представим себе, что алгоритм получил решение задачи. Соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность? задачу о сумме: Рассмотрим задачу о сумме: Можно ли V Можно ли представить число V в виде суммы каких- либо элементов массива А? nчисел А = (a1,…an) число V Дано n чисел – А = (a1,…an) и число V. X=(x1,…,xn)x i є{0,1} axV Найти X=(x1,…,xn), x i є{0,1}, чтобы a i x i = V. Представим себе, что алгоритм получил решение задачи. Соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность? задачу о сумме: Рассмотрим задачу о сумме: Можно ли V Можно ли представить число V в виде суммы каких- либо элементов массива А? nчисел А = (a1,…an) число V Дано n чисел – А = (a1,…an) и число V. X=(x1,…,xn)x i є{0,1} axV Найти X=(x1,…,xn), x i є{0,1}, чтобы a i x i = V.

18 Если какой-то алгоритм выдает результат – массив X, то проверка правильности этого результата может быть выполнена с пполиномиальной сложностью: a i x i = V не более Q (n) операций. проверка a i x i = V требует не более Q (n) операций. Содержательно задача относится к классу NP, если ее решение некоторым алгоритмом может быть быстро (пполиномиально) проверено. Класс NP (пполиномиально проверяемые задачи)

19 Другое определение класса NP: к классу NP относятся задачи, решение которых с помощью дополнительной информации пполиномиальной длины, данной нам свыше, мы можем проверить за пполиномиальное время. задача о коммивояжёре. В частности, к классу NP относятся все задачи, решение которых можно проверить за пполиномиальное время. Класс P содержится в классе NP. Классическим примером NP-задачи является задача о коммивояжёре. Класс NP (пполиномиально проверяемые задачи)

20 Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть пполиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи. На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пустое. Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть пполиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи. На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пустое.