пользователей: 21251
предметов: 10459
вопросов: 177801
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Классификация задач по степени сложности

Сложность задачи определяется через сложность наилучшего алгоритма, известного для ее решения.

Быстрыми алгоритмами являются линейные, которые обладают сложностью порядка n, и называются алгоритмами порядка 0(n), где n – размерность входного данного.

К линейным алгоритмам относятся:

алгоритм нахождения суммы для типичных чисел, состоящих из n1 и n2 цифр. Его сложность 0(n1)+n2.

Есть более быстрые алгоритмы, чем линейные. Например, алгоритм двоичного поиска в линейном упорядоченном массиве, его сложность 0(log2n), где n – длинна упорядоченного массива.

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

Полиномиальные алгоритмы – алгоритмы, принадлежащие классу Р, эти алгоритмы имеют полиномиальную временную сложность и в общем виде их сложность записывается 0(nк), где к из Z, k>0.

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

Отметим, что экспоненциальным алгоритмом при небольших значениях n может быть более быстрым, чем полиномиальным, однако различие между двумя этими типами задач очень велико и всегда проявляется при больших значениях n.

Класс Р: Задачу называем «хорошей» если для нее существует полиномиальный алгоритм (Рассоривать множество из n чисел(сложность 0(n2)), нахождение вершин, связанных цепочкой дуг(0(n+m)) и т.п.)

Класс Е:

Задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы полного графа.

Ни Р  ни Е:

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


20.06.2014; 21:38
хиты: 324
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь