Ограничения мощи алгоритмов. Недетерминистический алгоритм

Ограничения мощи алгоритмов

Разум различает возможное и невозможное; рассудок различает осмысленное и бессмысленное. Однако возможное может оказаться бессмысленным. Макс Борн

Ограничения мощи алгоритмов

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

Ограничения мощи алгоритмов

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

Ограничения мощи алгоритмов

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

Ограничения мощи алгоритмов

Простейший метод получения класса нижней границы основан на подсчете количества элементов входных данных, которые следует обработать. Поскольку любой алгоритм должен как минимум «прочесть» все данные, с которыми он будет работать, и «записать» все выходные данные, такой подсчет приводит к тривиальной нижней границе (trivial lower bound). Например, любой алгоритм для генерации всех перестановок n различных элементов должен принадлежать Ω(n!), поскольку размер выходных данных равен n!. Эта граница – плотная, т.к. хорошие алгоритмы для генерации перестановок затрачивают постоянное время для поиска каждой из них, за исключением первой.

Ограничения мощи алгоритмов

Аналогичным способом тривиальная граница для вычисления произведения двух матриц размером n*n оказывается равной Ω(n²), т.к. любой такой алгоритм должен обработать 2*n² элементов входных матриц и сгенерировать n² элементов произведения. Однако неизвестно, является ли эта граница плотной. Тривиальные нижние границы зачастую слишком малы, чтобы быть полезными. Например, тривиальная граница для задачи коммивояжера равна Ω(n²), поскольку на вход подается n*(n-1)/2 расстояний между городами, а на выходе получается список из n+1 городов, образующих оптимальный маршрут.

Ограничения мощи алгоритмов

Однако эта граница бесполезна, поскольку неизвестен алгоритм решения данной задачи, у которого время работы выражалось бы полиномиальной функцией любой степени. Более того, не всегда неизвестно, какая часть входных данных должна быть обработана любым алгоритмом решения рассматриваемой задачи. Например, поиск элемента с данным значением в отсортированным массиве не требует обработки всех его элементов. Другой пример, для задачи определения связности неориентированного графа, заданного его матрицей смежности, естественно ожидать, что любой такой алгоритм должен проверить существование каждого из n*(n-1)/2 потенциальных ребер.

Ограничения мощи алгоритмов