Классификация задач по временной сложности.

Date: 2015-10-07; view: 462.

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

По временной сложности все задачи классифицируются следующим образом:

1 класс. Задачи класса Р – это задачи, для которых известен алгоритм и временная сложность оценивается полиномиальной функцией f(N) = a _k*N + a _k-1*N ² +…+a ₀*N ^k+1. Алгоритмы таких задач называют также “хорошими” алгоритмами. Этих алгоритмов мало, они образуют небольшой по мощности класс. Легко реализуются. Функция временной сложности для таких алгоритмов имеет вид O(N^k).

2 класс. Задачи класса Е – это задачи, для которых алгоритм известен, но сложность таких алгоритмов O(f ^N), где f – константа. Задачи такого класса – это задачи построения всех подмножеств некоторого множества, задачи построения всех полных подграфов графа. При небольших N экспоненциальный алгоритм может работать быстрее полиномиального.

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

N
1000N2	4 мкс	10 мкс	25 мкс	100 мкс	400 мкс	2.5 мс	10 мс	1 с
100N3	1 мкс	3 мкс	18.5 мкс	100 мкс	800 мкс	13 мс	100 мс	100 с
2N	4 мс	8 мс	30 мс	1 мкс	1 мс	10 сут.	Миллиарды лет
	16 мс	250 мс	30 с	Миллиарды лет