пользователей: 24762
предметов: 11099
вопросов: 196102
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


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

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

Быстрыми алгоритмами являются линейные, которые обладают сложностью порядка 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
хиты: 434
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2017. All Rights Reserved. помощь