Анализ трудоёмкости алгоритмов

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

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

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

Классы сложности алгоритма:

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

 

Лекция

Виды алгоритмов

Комбинаторные алгоритмы

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

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

Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

Перестановкой из n элементов (например чисел 1, 2, …, n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.

Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.

Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

Общие комбинаторные алгоритмы

Генераторы псевдослучайных чисел:

Алгоритм Робинсона — Шенстеда — генерация перестановок из пар таблиц Юнга

Алгоритмы на графах

Тео́ рия гра́ фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V, E), где V есть подмножество любого счётного множества, а E — подмножество V× V.

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Алгоритмы поиска

Алгоритмы на строках

Алгоритмы сортировки

Например, «Сортировка пузырьком»

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n-1], A[n]

t: = истина

цикл пока t:

t: = ложь

цикл для j = 1, 2, ..., n − 1:

если A[j] > A[j+1], то:

обменять местами элементы A[j] и A[j+1]

t: = истина

Алгоритмы слияния

Алгоритмы сжатия данных

Алгоритмы сжатия без потерь

Семейство алгоритмов словарного сжатия Лемпеля — Зива

Deflate — это алгоритм сжатия без потерь, который использует комбинацию алгоритма LZ77 и алгоритма Хаффмана. Изначально он был описан Филом Кацом для 2-й версии своей утилиты для создания архивов PKZIP, который впоследствии был определён в RFC 1951 (http: //tools.ietf.org/html/rfc1951).

Алгоритмы сжатия с потерями

Вычислительная геометрия

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: