Теория сложности в теории алгоритмов.

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

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

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

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

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

Классы сложности.

Классами сложности – множества вычислительных задач, примерно одинаковых по сложности вычисления.

1. Класс P (от англ. polynomial) – класс алгоритмов, работающих за полиноминальное время, время работы не существенно зависит от размера входных данных. Стандартные алгоритмы целочисленного сложения, перемножения матриц и др.

2. Класс NP (от англ. non-deterministic polynomial) – класс алгоритмов, время работы которых существенно зависит от размера входных данных; в то же время, если предоставить алгоритму некоторые дополнительные сведения (сертификат решения), то он сможет достаточно быстро решить задачу. Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор. Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.

3. Класс BPP (от англ. bounded-error, probabilistic, polynomial) – класс алгоритмов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа). Решение СЛАУ методом половинного деления, методом хорд и др.

Дата добавления: 2015-09-01