До указанного срока статья не должна редактироваться другими участниками проекта сайт . По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание }}.
См. также методические указания по использованию Ресурса сайт в учебном процессе.
Теория сложности вычислений - раздел теории вычислений, изучающий объем работы, требуемой для решения вычислительной проблемы.
Задача рассматривается как сложная, если решение проблемы требует большого количества ресурсов, независимо от алгоритма, используемого для ее решения. Теория формализует это интуитивное понятие, вводя математические модели вычислений для изучения этих проблем и количественной оценки объема ресурсов, необходимых для их решения, такие как время и используемая память. Возможны и другие меры сложности, такие как: количество сообщений (коммуникационная сложность), число элементов в схеме из функциональных элементов (схемная сложность) и количество процессоров. В частности, теории сложности вычислений определяет практические ограничения на то, что компьютеры могут и что не могут делать.
Тесно связаны с теорий сложности вычислений анализ алгоритмов и теория вычислимости. Основное различие между теорией сложности вычислений и анализом алгоритмов является то, что последняя посвящена анализу объема ресурсов, необходимых определенному алгоритму, чтобы решить проблему, в то время как первая задает вопрос более общего характера о всех возможных алгоритмах, которые могут быть использованы чтобы решить ту же проблему. Более точно, теория сложности вычислений пытается классифицировать проблемы, которые могут или не могут быть решены надлежащим количеством ограниченных ресурсов. В свою очередь, введение ограничений на имеющиеся ресурсы - это то, что отличает теорию сложности вычислений от теории вычислимости: последняя спрашивает какие проблемы могут быть решены в принципе алгоритмически, не ограничивая вычислительные ресурсы.
Вычислительные проблемы
Экземпляры задач
Вычислительные проблемы(задачи) можно рассматривать как бесконечный набор пар: (экземпляр задачи, решение для данного экземпляра). Входной строкой для вычислительной проблемы является строка, описывающая экземпляр задачи. Выходная строка для вычислительной проблемы - описание решения для экземпляра задачи, описанного входной строкой. Например, проблема распознавания простоты числа: экземпляр задачи - число, для которого следует определить простое оно или нет, решение - строка «да», если это число простое и «нет» в противном случае. Теория сложности вычислений рассматривает только массовые задачи, т.е. требование о бесконечности набора экземпляров задач обязательно.
Представление задачи
При рассмотрении вычислительных задач описанием экземпляра задачи является строка над алфавитом. Как правило, алфавит берется бинарным(т. е. множество {0,1}). Различные математические объекты должны быть соответствующим образом закодированы. Так, например, целые числа могут быть представлены в двоичной системе счисления, и графы могут быть закодированы непосредственно через их матрицы смежности или через их кодирование списков смежности в двоичной системе.
Задачи распознавания
Задачи распознавания является одним из центральных объектов исследования в теории сложности вычислений. Задача распознавания является особым типом вычислительных проблемы, ответом на которую является либо "да" или "нет"(1 или 0). Задачу распознавания можно сформулировать в виде задачи принадлежности входной строки к некоторому подмножеству (языку) множества всех входных строк. Входная строка проблемы принадлежит соответствующему языку тогда и только тогда, когда ответом на эту строку является «да». Таким образом задача распознавания - это задача распознавания принадлежности входной строку к некоторому языку.
Пример задачи распознавания. Входная строка: описание произвольного графа. Проблема состоит в решении вопроса связен ли данный граф или нет. Язык связных графов - это множество описаний всех связных графов. Для получения точного определения этого языка, нужно решить, как графы кодируются как бинарных строки.
Задачи поиска
Задачей поиска является вычислительная задача, где выходное значение является более сложным, чем в задаче распознавания (то есть, это не просто «да» или «нет»).
Примером задачи поиска является задача коммивояжера. Задача коммивояжёра (коммивояжёр - бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз - в таком случае выбор осуществляется среди гамильтоновых циклов. Входная строка: описание взвешенного (т.е. с числовыми пометками на ребрах) графа. Выходная строка - описание оптимального маршрута коммивояжёра.
Существует парная зависимость между задачами распознавания и задачами поиска. Задачу поиска можно сформулировать в качестве задачи распознавания. Например, для задачи поиска «умножение двух чисел», соответствующая парная задача распознавания может быть представлена как множество троек (A, B, C) таких, что отношения A × B = C выполнено.
Измерение сложности
Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения, объём необходимой памяти и т.д.) в зависимости от размера входа и выхода.
Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных. Например, количество операций алгоритма сортировки вставками значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать подобных трудностей, рассматривают понятие временной сложности алгоритма в худшем случае.
Временная сложность алгоритма (в худшем случае) - это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных.
Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).
По аналогии с временной сложностью, определяют пространственную сложность алгоритма, только здесь говорят не о количестве элементарных операций, а об объёме используемой памяти.
Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что во-первых, точное значение временной сложности зависит от определения элементарных операций (например, сложность можно измерять в количестве арифметических операций или операций на машине Тьюринга), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.
Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера.
Сложность определяется исходя из вычислительной модели, в которой проводят вычисления.
Вычислительные модели
Существует множество различных моделей вычислений: машина Поста, машина Минского, лямбда-исчисление, частично рекурсивные функции, нормальные алгоритмы Маркова, машины с произольным доступом к памяти (RAM машины) и др. Упомянем лишь наиболее популярную вычислительную модель - машину Тьюринга.
Машина Тьюринга
Маши́на Тью́ринга (МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча - Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара (ленточный символ - состояние), для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
Модель машины Тьюринга допускает различные расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями; машины, использующие источник случайности.
Машина Тьюринга является одной из основных моделей вычисления в теории сложности.
Классы сложности
Классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Существуют классы сложности языков и функциональные классы сложности. Класс сложности языков - это множество предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Понятие функционального класса сложности аналогично, за исключением того, что это не множество предикатов, а множество функций. В теории сложности, по умолчанию, класс сложности - это класс сложности языков. Типичное определение класса сложности выглядит так:
Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O(f(n)) ресурса, где n - длина слова x.
В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы). Языки, распознаваемые предикатами из некоторого класса (то есть множества слов, на которых предикат возвращает 1), также называются принадлежащими тому же классу.
Кроме того, многие классы могут также быть описаны в терминах математической логики или теории игр.
Классы принято обозначать прописными буквами. Дополнение к классу C (то есть класс языков, дополнения которых принадлежат C) обозначается co-C.
Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами для данного класса.
Класс P
Класс P (от англ. polynomial) - множество задач распознавания, которые могут быть решены на детерминированной машине Тьюринга за полиномиальное от длины входа время. Аналогично, для задач поиска определяется класс FP (от англ. functional polynomial).
Более формально, рассмотрим детерминированные машины Тьюринга, которые вычисляют ответ по данному на входную ленту слову из входного алфавита . Временем работы машины Тьюринга при фиксированном входном слове x называется количество рабочих тактов машины Тьюринга от начала до остановки машины. Сложностью функции , вычисляемой некоторой машиной Тьюринга, называется функция , зависящая от длины входного слова и равная максимуму времени работы машины по всем входным словам фиксированной длины:
.Если для функции f существует машина Тьюринга M такая, что для некоторого числа c и достаточно больших n , то говорят, что она принадлежит классу FP, или полиномиальна по времени.
Класс P является одним из фундаментальных в теории сложности вычислений.
Класс NP
Классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания, время решения которых существенно зависит от размера входных данных; в то же время, существует алгоритм, который, получив наряду с описанием входных значений, некоторые дополнительные сведения (свидетеля решения), может достаточно быстро (за время, не превосходящее полинома от размера данных) решить задачу.
Более формально, язык L называется принадлежащим классу NP, если существуют двуместный предикат R(x, y) из класса P (т.е. вычислимый за полиномиальное время) и многочлен p такие, что для всякого слова x длины n условие «x принадлежит L» равносильно условию «найдётся y длины меньше p(n) такой, что верно R(x, y)». Слово y называется свидетелем принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L. Всякую задачу, принадлежащую NP, можно решить за экспоненциальное время перебором всех возможных свидетелей длины меньше p(n).
Пример задачи из NP: задача распознавания «Существование целочисленного решения системы линейных неравенств». Свидетель - решение системы неравенств. За полиномиальное время легко проверить, что решение-свидетель подходит.
Класс NP включает в себя класс P.
Открытые проблемы
В теории сложности вычислений существует множество нерешенных проблем, в основном они касаются вопросов разделения или вложенности тех или иных классов сложности. Одним из таких вопросов является проблема равенства классов P и NP.
Проблема равенства классов P и NP
В конечном счете проблема равенства классов P и NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время)?
Из определения классов P и NP сразу вытекает следствие: . Однако до сих пор ничего не известно о строгости этого включения, т.е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные NP-задачи (так называемые NP-полные задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо.
Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. В настоящее время большинство математиков считают, что эти классы не равны. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.
Литература
- Гери М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи. Издательство Мир в 1982 году. - 420 с. Монография американских ученых посвящена решению сложных (в том числе и NP-трудных) комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории автоматов с примерами.
- Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, Клифорд Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. - М.: «Вильямс», 2005. -
Постоянное время
Говорят, что алгоритм является алгоритмом постоянного времени (записывается как время O(1) ), если значение T (n ) ограничено значением, не зависящим от размера входа. Например, получение одного элемента в массиве занимает постоянное время, поскольку выполняется единственная команда для его обнаружения. Однако нахождение минимального значения в несортированном массиве не является операцией с постоянным временем, поскольку мы должны просмотреть каждый элемент массива. Таким образом, эта операция занимает линейное время, O(n). Если число элементов известно заранее и не меняется, о таком алгоритме можно говорить как об алгоритме постоянного времени.
Несмотря на название "постоянное время", время работы не обязательно должно быть независимым от размеров задачи, но верхняя граница времени работы не должна зависеть. Например, задача "обменять значения a и b , если необходимо, чтобы в результате получили a ≤b ", считается задачей постоянного времени, хотя время работы алгоритма может зависеть от того, выполняется ли уже неравенство a ≤ b или нет. Однако существует некая константа t , для которой время выполнения задачи всегда не превосходит t .
Ниже приведены некоторые примеры кода, работающие за постоянное время:
Int index = 5; int item = list; if (условие верно) then else выполнить некоторые операции с постоянным временем работы for i = 1 to 100 for j = 1 to 200 выполнить некоторые операции с постоянным временем работы
Если T (n ) равен O(некоторое постоянное значение ), это эквивалентно T (n ) равно O(1).
Логарифмическое время
логарифмическое время , если T (n ) = O(log n ) . Поскольку в компьютерах принята двоичная система счисления , в качестве базы логарифма используется 2 (то есть, log 2 n ). Однако при замене базы логарифмы log a n и log b n отличаются лишь на постоянный множитель, который в записи O-большое отбрасывается. Таким образом, O(log n ) является стандартной записью для алгоритмов логарифмического времени независимо от базы логарифма.
Алгоритмы, работающие за логарифмическое время, обычно встречаются при операциях с двоичными деревьями или при использовании двоичного поиска .
O(log n) алгоритмы считаются высокоэффективными, поскольку время выполнения операции в пересчёте на один элемент уменьшается с увеличением числа элементов.
Очень простой пример такого алгоритма - деление строки пополам, вторая половина опять делится пополам, и так далее. Это занимает время O(log n) (где n - длина строки, мы здесь полагаем, что console.log и str.substring занимают постоянное время). Это означает, что для увеличения числа печатей необходимо удвоить длину строки.
// Функция для рекурсивной печати правой половины строки var right = function (str ) { var length = str . length ; // вспомогательная функция var help = function (index ) { // Рекурсия: печатаем правую половину if (index < length ) { // Печатаем символы от index до конца строки console . log (str . substring (index , length )); // рекурсивный вызов: вызываем вспомогательную функцию с правой частью help (Math . ceil ((length + index ) / 2 )); } } help (0 ); }
Полилогарифмическое время
Говорят, что алгоритм выполняется за полилогарифмическое время , если T (n ) = O((log n ) k ), для некоторого k . Например, задача о порядке перемножения матриц может быть решена за полилогарифмическое время на параллельной РАМ-машине .
Сублинейное время
Говорят, что алгоритм выполняется за сублинейное время , если T (n ) = o(n ). В частности, сюда включаются алгоритмы с временной сложностью, перечисленные выше, как и другие, например, поиск Гровера со сложностью O(n ½).
Типичные алгоритмы, которые, являясь точными, всё же работают за сублинейное время, используют распараллеливание процессов (как это делают алгоритм NC 1 вычисления определителя матрицы), неклассические вычисления (как в поиске Гровера) или имеют гарантированное предположение о струтуре входа (как работающие за логарифмическое время, алгоритмы двоичного поиска и многие алгоритмы обработки деревьев). Однако формальные конструкции , такие как множество всех строк, имеющие бит 1 в позиции, определяемой первыми log(n) битами строки, могут зависеть от каждого бита входа, но, всё же, оставаться сублинейными по времени.
Термин алгоритм с сублинейным временем работы обычно используется для алгоритмов, которые, в отличие от приведённых выше примеров, работают на обычных последовательных моделях машин и не предполагают априорных знаний о структуре входа . Однако для них допускается применение вероятностных методов и даже более того, алгоритмы должны быть вероятностными для большинства тривиальных задач.
Поскольку такой алгоритм обязан давать ответ без полного чтения входных данных, он в очень сильной степени зависит от способов доступа, разрешённых во входном потоке. Обычно для потока, представляющего собой битовую строку b 1 ,...,b k , предполагается, что алгоритм может за время O(1) запросить значение b i для любого i .
Алгоритмы сублинейного времени, как правило, вероятностны и дают лишь аппроксимированное решение. Алгоритмы сублинейного времени выполнения возникают естественным образом при исследовании проверки свойств .
Линейное время
линейное время , или O(n ) , если его сложность равна O(n ). Неформально, это означает, что для достаточно большого размера входных данных время работы увеличивается линейно от размера входа. Например, процедура, суммирующая все элементы списка, требует время, пропорциональное длине списка. Это описание не вполне точно, поскольку время работы может существенно отличаться от точной пропорциональности, особенно для малых значений n .
Линейное время часто рассматривается как желательный атрибут алгоритма . Было проведено много исследований для создания алгоритмов с (почти) линейным временем работы или лучшим. Эти исследования включали как программные, так и аппаратные подходы. В случае аппаратного исполнения некоторые алгоритмы, которые, с математической точки зрения, никогда не могут достичь линейного времени исполнения в стандартных моделях вычислений , могут работать за линейное время. Существуют некоторые аппаратные технологии, которые используют параллельность для достижения такой цели. Примером служит ассоциативная память . Эта концепция линейного времени используется в алгоритмах сравнения строк, таких как алгоритм Бойера - Мура и алгоритм Укконена .
Квазилинейное время
Говорят, что алгоритм работает за квазилинейное время, если T (n ) = O(n log k n ) для некоторой константы k . Линейно-логарифмическое время является частным случаем с k = 1 . При использовании обозначения слабое-O эти алгоритмы являются Õ(n ). Алгоритмы квазилинейного времени являются также o(n 1+ε) для любого ε > 0 и работают быстрее любого полинома от n
Алгоритмы, работающие за квазилинейное время, вдобавок к линейно-логарифмическим алгоритмам, упомянутым выше, включают:
- Сортировка слиянием на месте , O(n log 2 n )
- Быстрая сортировка , O(n log n ), в вероятностной версии имеет линейно-логарифмическое время выполнения в худшем случае. Невероятностная версия имеет линейно-логарифмическое время работы только для измерения сложности в среднем.
- Пирамидальная сортировка , O(n log n ), сортировка слиянием , introsort , бинарная сортировка с помощью дерева, плавная сортировка , пасьянсная сортировка , и т.д. в худшем случае
- Быстрые преобразования Фурье , O(n log n )
- Вычисление матриц Монжа , O(n log n )
Линейно-логарифмическое время
Линейно-логарифмическое является частным случаем квазилинейного времени с показателем k = 1 на логарифмическом члене.
Линейно-логарифмическая функция - это функция вида n log n (т.е. произведение линейного и логарифмического членов). Говорят, что алгоритм работает за линейно-логарифмическое время , если T (n ) = O(n log n ) . Таким образом, линейно-логарифмический элемент растёт быстрее, чем линейный член, но медленнее, чем любой многочлен от n со степенью, строго большей 1.
Во многих случаях время работы n log n является просто результатом выполнения операции Θ(log n ) n раз. Например, сортировка с помощью двоичного дерева создаёт двоичное дерево путём вставки каждого элемента в массив размером n один за другим. Поскольку операция вставки в сбалансированное бинарное дерево поиска занимает время O(log n ), общее время выполнения алгоритма будет линейно-логарифмическим.
Сортировки сравнением требуют по меньшей мере линейно-логарифмического числа сравнений для наихудшего случая, поскольку log(n !) = Θ(n log n ) по формуле Стирлинга . То же время выполнения зачастую возникает из рекуррентного уравнения T (n ) = 2 T (n /2) + O(n ).
Подквадратичное время
Некоторые примеры алгоритмов полиномиального времени:
Строго и слабо полиномиальное время
В некоторых контекстах, особенно в оптимизации , различают алгоритмы со строгим полиномиальным временем и слабо полиномиальным временем . Эти две концепции относятся только ко входным данным, состоящим из целых чисел.
Строго полиномиальное время определяется в арифметической модели вычислений. В этой модели базовые арифметические операции (сложение, вычитание, умножение, деление и сравнение) берутся за единицы выполнения, независимо от длины операндов. Алгоритм работает в строго полиномиальное время, если
- число операций в арифметической модели вычислений ограничено многочленом от числа целых во входном потоке, и
- память, используемая алгоритмом, ограничена многочленом от размеров входа.
Любой алгоритм с этими двумя свойствами можно привести к алгоритму полиномиального времени путём замены арифметических операций на соответствующие алгоритмы выполнения арифметических операций на машине Тьюринга . Если второе из вышеприведённых требований не выполняется, это больше не будет верно. Если задано целое число (которое занимает память, пропорциональную n в машине Тьюринга), можно вычислить с помощью n операций, используя повторное возведение в степень . Однако память, используемая для представления 2 2 n {\displaystyle 2^{2^{n}}} , пропорциональна 2 n {\displaystyle 2^{n}} , и она скорее экспоненционально, чем полиномиально, зависит от памяти, используемой для входа. Отсюда - невозможно выполнить эти вычисления за полиномиальное время на машине Тьюринга, но можно выполнить за полиномиальное число арифметических операций.
Обратно - существуют алгоритмы, которые работают за число шагов машины Тьюринга, ограниченных полиномиальной длиной бинарно закодированного входа, но не работают за число арифметических операций, ограниченное многочленом от количества чисел на входе. Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел является одним из примеров. Для двух целых чисел a {\displaystyle a} и b {\displaystyle b} время работы алгоритма ограничено O ((log a + log b) 2) {\displaystyle O((\log \ a+\log \ b)^{2})} шагам машины Тьюринга. Это число является многочленом от размера бинарного представления чисел a {\displaystyle a} и b {\displaystyle b} , что грубо можно представить как log a + log b {\displaystyle \log \ a+\log \ b} . В то же самое время число арифметических операций нельзя ограничить числом целых во входе (что в данном случае является константой - имеется только два числа во входе). Ввиду этого замечания алгоритм не работает в строго полиномиальное время. Реальное время работы алгоритма зависит от величин a {\displaystyle a} и b {\displaystyle b} , а не только от числа целых чисел во входе.
Если алгоритм работает за полиномиальное время, но не за строго полиномиальное время, говорят, что он работает за слабо полиномиальное время . Хорошо известным примером задачи, для которой известен слабо полиномиальный алгоритм, но не известен строго полиномиальный алгоритм, является линейное программирование . Слабо полиномиальное время не следует путать с псевдополиномиальным временем .
Классы сложности
Концепция полиномиального времени приводит к нескольким классам сложности в теории сложности вычислений. Некоторые важные классы, определяемые с помощью полиномиального времени, приведены ниже.
- : Класс сложности задач разрешимости , которые могут быть решены в детерминированной машине Тьюринга за полиномиальное время.
- : Класс сложности задач разрешимости, которые могут быть решены в недетерминированной машине Тьюринга за полиномиальное время.
- ZPP : Класс сложности задач разрешимости, которые могут быть решены с нулевой ошибкой в вероятностной машине Тьюринга за полиномиальное время.
- : Класс сложности задач разрешимости, которые могут быть решены с односторонними ошибками в вероятностной машине Тьюринга за полиномиальное время.
- BPP вероятностной машине Тьюринга за полиномиальное время.
- BQP : Класс сложности задач разрешимости, которые могут быть решены с двусторонними ошибками в квантовой машине Тьюринга за полиномиальное время.
P является наименьшим классом временной сложности на детерминированной машине, которая является устойчивой в терминах изменения модели машины. (Например, переход от одноленточной машины Тьюринга к мультиленточной может привести к квадратичному ускорению, но любой алгоритм, работающий за полиномиальное время на одной модели, будет работать за полиномиальное время на другой.)
Суперполиномиальное время
Говорят, что алгоритм работает за суперполиномиальное время , если T (n ) не ограничен сверху полиномом. Это время равно ω(n c ) для всех констант c , где n - входной параметр, обычно - число бит входа.
Например, алгоритм, осуществляющий 2 n шагов, для входа размера n требует суперполиномиального времени (конкретнее, экспоненциального времени).
Ясно, что алгоритм, использующий экспоненциальные ресурсы, суперполиномиален, но некоторые алгоритмы очень слабо суперполиномиальны. Например, тест простоты Адлемана - Померанса - Румели * работает за время n O(log log n ) на n -битном входе. Это растёт быстрее, чем любой полином, для достаточно большого n , но размер входа должен стать очень большим, чтобы он не доминировался полиномом малой степени.
Алгоритм, требующий суперполиномиального времени, лежит вне класса сложности . Тезис Кобэма утверждает, что эти алгоритмы непрактичны, и во многих случаях это так. Поскольку задача равенства классов P и NP не решена, никаких алгоритмов для решения NP-полных задач за полиномиальное время в настоящее время не известно.
Квазиполиномиальное время
Алгоритмы квазиполиномиального времени - это алгоритмы, работающие медленнее, чем за полиномиальное время, но не столь медленно, как алгоритмы экспоненциального времени. Время работы в худшем случае для квазиполиномиального алгоритма равно c . Хорошо известный классический алгоритм разложения целого числа на множители, , не является квазиполиномиальным, поскольку время работы нельзя представить как 2 O ((log n) c) {\displaystyle 2^{O((\log n)^{c})}} для некоторого фиксированного c . Если константа "c" в определении алгоритма квазиполиномиального времени равна 1, мы получаем алгоритм полиномиального времени, а если она меньше 1, мы получаем алгоритм сублинейного времени.
Алгоритмы квазиполиномиального времени обычно возникают при сведении NP-трудной задачи к другой задаче. Например, можно взять NP-трудную задачу, скажем, 3SAT , и свести её к другой задаче B, но размер задачи станет равным 2 O ((log n) c) {\displaystyle 2^{O((\log n)^{c})}} . В этом случае сведение не доказывает, что задача B NP-трудна, такое сведение лишь показывает, что не существует полиномиального алгоритма для B, если только не существует квазиполиномиального алгоритма для 3SAT (а тогда и для всех -задач). Подобным образом - существуют некоторые задачи, для которых мы знаем алгоритмы с квазиполиномиальным временем, но для которых алгоритмы с полиномиальным временем неизвестны. Такие задачи появляются в аппроксимационых алгоритмах. Знаменитый пример - ориентированная задача Штайнера , для которой существует аппроксимационный квазиполиномиальный алгоритм с аппроксимационным коэффициентом O (log 3 n) {\displaystyle O(\log ^{3}n)} (где n - число вершин), но существование алгоритма с полиномиальным временем является открытой проблемой.
Класс сложности QP состоит из всех задач, имеющих алгоритмы квазиполиномиального времени. Его можно определить в терминах DTIME следующим образом
QP = ⋃ c ∈ N DTIME (2 (log n) c) {\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})}Связь с NP-полными задачами
В теории сложности нерешённая проблема равенства классов P и NP спрашивает, не имеют ли все задачи из класса NP алгоритмы решения за полиномиальное время. Все хорошо известные алгоритмы для NP-полных задач, наподобие 3SAT, имеют экспоненциальное время. Более того, существует гипотеза, что для многих естественных NP-полных задач не существует алгоритмов с субэкспоненциальным временем выполнения. Здесь "субэкспоненциальное время " взято в смысле второго определения, приведённого ниже. (С другой стороны, многие задачи из теории графов, представленные естественным путём матрицами смежности, разрешимы за субэкспоненциальное время просто потому, что размер входа равен квадрату числа вершин.) Эта гипотеза (для задачи k-SAT) известна как гипотеза экспоненциального времени . Поскольку она предполагает, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени, некоторые результаты неаппроксимируемости в области аппроксимационных алгоритмов исходят из того, что NP-полные задачи не имеют алгоритмов квазиполиномиального времени. Например, смотрите известные результаты по неаппроксимируемости задачи о покрытии множества .
Субэкспоненциальное время
Термин субэкспоненциальное время используется, чтобы выразить, что время выполнения некоторого алгоритма может расти быстрее любого полиномиального, но остаётся существенно меньше, чем экспоненциальное. В этом смысле задачи, имеющие алгоритмы субэкспоненциального времени, являются более податливыми, чем алгоритмы только с экспотенциальным временем. Точное определение "субэкспоненциальный" пока не является общепринятым , и мы приводим ниже два наиболее распространённых определения.
Первое определение
Говорят, что задача решается за субэкспоненциальное время, если она решается алгоритмом, логарифм времени работы которого растёт меньше, чем любой заданный многочлен. Более точно - задача имеет субэкспоненциальное время, если для любого ε > 0 существует алгоритм, который решает задачу за время O(2 n ε). Множество все таких задач составляет класс сложности SUBEXP , который в терминах DTIME можно выразить как .
SUBEXP = ⋂ ε > 0 DTIME (2 n ε) {\displaystyle {\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)}Заметим, что здесь ε не является частью входных данных и для каждого ε может существовать свой собственный алгоритм решения задачи.
Второе определение
Некоторые авторы определяют субэкспоненциальное время как время работы 2 o(n ) . Это определение допускает большее время работы, чем первое определение. Примером такого алгоритма субэкспоненциального времени служит хорошо известный классический алгоритм разложения целых чисел на множители, общий метод решета числового поля , который работает за время около 2 O ~ (n 1 / 3) {\displaystyle 2^{{\tilde {O}}(n^{1/3})}} , где длина входа равна n . Другим примером служит хорошо известный алгоритм для задачи изоморфизма графов , время работы которого равно 2 O ((n log n)) {\displaystyle 2^{O({\sqrt {(}}n\log n))}} .
Заметим, что есть разница, является ли алгоритм субэкспоненциальным по числу вершин или числу рёбер. В параметризованной сложности эта разница присутствует явно путём указания пары , задачи разрешимости и параметра k . SUBEPT является классом всех параметризованных задач, которые работают за субэкспоненциальное время по k и за полиномиальное по n :
SUBEPT = DTIME (2 o (k) ⋅ poly (n)) . {\displaystyle {\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).}Точнее, SUBEPT является классом всех параметризованных задач (L , k) {\displaystyle (L,k)} , для которых существует вычислимая функция f: N → N {\displaystyle f:\mathbb {N} \to \mathbb {N} } с f ∈ o (k) {\displaystyle f\in o(k)} и алгоритм, который решает L за время 2 f (k) ⋅ poly (n) {\displaystyle 2^{f(k)}\cdot {\text{poly}}(n)} .
Для оценки эффективности алгоритма наиболее важными показателями являются:
Время выполнения алгоритма,
- требуемый объем оперативной памяти.
В наши дни, в силу полувека технического прогресса, первый показатель (время выполнения) зачастую значительно важнее, чем второй, поэтому далее подробно остановимся только на нем.
Упрощения для оценки времени выполнения алгоритмов
В работах Д.Кнута был предложен следующий подход для анализа времени выполнения алгоритмов: общее время складывается из величин стоимость * частота для каждой базовой операции. В число базовых операций могут входить сложение, умножение, деление, получение элемента по индексу из массива, сравнение целых чисел и т.д. Нетрудно заметить, что в этом случае вычисление оценки времени выполнения алгоритма довольно-таки утомительно. Поэтому А.Тьюринг сказал, что удобно пользоваться даже грубыми приближениями оценок времени выполнения алгоритмов: можно присвоить веса различным операциям в зависимости от их частоты появления во время работы алгоритма и учитывать только те операции, которым соответствуют наибольшие веса. Например, при перемножении матриц следует учитывать только такие операции, как умножение и запись чисел, т.к. это самые частые операции. Рассмотрение только наиболее часто встречающихся операций - первое упрощение , предложенное для приблизительного расчета времени выполнения алгоритмов.
Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число N характеризует размер входных данных),
\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),
вместо \(1/6N^3\) пишут "этот алгоритм имеет сложность \(O(N^3)\), вместо \(3N^4\) пишут "этот алгоритм имеет сложность \(O(N^4)\)".
Определение O-большого
Говорят, что \(f\) является "O большим" от \(g\) при \(x \to x_0\), если существует такая константа \(C>0\), что для всех \(x\) из окрестности точки \(x_0\) имеет место неравенство \(|f(x)| \leq C|g(x)|\). Ниже приведена иллюстрация определения (ось \(x\) - размер входных данных, ось \(y\) - время выполнения алгоритма). Мы видим, что начиная с некоторой точки при стремлении размера входных данных к \(\propto\) \(f(n)\) растет медленнее, чем \(g(n)\) и вообще \(g(n)\) как бы ограничивает ее сверху.
Примеры. \(1 = O(N), N = O(N^2).\)
Наряду с оценками вида \(O(N)\) используется оценка \(\Omega(N)\) (омега большое). Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция \(f(N)=\Omega(N^2)\). Это значит, что даже в самом удачном случае будет произведено не менее \(N^2\) действий. В то время как оценка \(O(N^3)\) гарантирует, что в худшем случае будет не более чем порядка \(N^3\) действий. Также используется оценка \(\Theta(N)\) (тэта), которая является верхней и нижней асимптотической оценкой, когда \(O(N)\) и \(\Omega(N)\) совпадают. Итак, \(O(N)\) - приближенная оценка алгоритма на худших входных данных, \(\Omega(N)\) - на лучших входных данных, \(\Theta(N)\) - сокращенная запись одинаковых \(O(N)\) и \(\Omega(N)\).
Оценки времени выполнения для разных алгоритмов
Обозначим T(N) - время выполнения алгоритма. Пусть исследуемый алгоритм имеет вид:
1. набор инструкций, включающих только базовые операции:
Statement 1;
...
statement k;
Тогда T(N) = T(statement 1) + ... + T(statement k).
Т.к. каждая инструкция включает только базовые операции, то время выполнения этого куска кода не зависит от размера входных данных (не растет с ростом размера входных данных), т.е. является константой. Этот алгоритм имеет сложность O(1).
2. if-else инструкции
If (condition) {
sequence of statements 1
}
else {
sequence of statements 2
}
Здесь выполнится либо sequence of statements 1, либо sequence of statements 2, поэтому, т.к. мы хотим получить оценку времени выполнения в наихудшем случае, T(N) = max(T(sequence of statements 1), T(sequence of statements 2)). Например, если время выполнения sequence of statements 1 будет O(N), а sequence of statements - O(1), то T(N) = O(N).
For (i = 0; i < N; i++) {
sequence of statements
}
Т.к. цикл выполнится N раз, то sequence of statements тоже выполнится N раз. Если T(sequence of statements) = O(1), то T(N) = O(N)*O(1) = O(N).
4. Вложенные циклы.
For (i = 0; i < N; i++) {
for (j = 0; j < M; j ++){
...
}
}
Внешний цикл выполняется N раз. Каждый раз, когда выполняется внешний цикл, выполняется внутренний цикл M Теперь рассмотрим такой код: For (i = 0; i < N; i++) { Посмотрим на изменение количества итераций внутреннего цикла в зависимости от итерации внешнего цикла. I цикл j (кол-во раз выполнения) Тогда sequence of statements выполнится N + N-1 + ... + 1 раз. Для быстрого подсчета подобных сумм пригодятся формулы из матанализа, в данном случае формула
А вот и другие наиболее часто нужные формулы, полезные для подобных случаев: 4. Когда утверждение включает вызов метода, то оценка времени выполнения утверждения рассчитывается с учетом оценки времени выполнения метода. Например: for (j = 0; j < N; j ++){ 5. Двоичный(бинарный) поиск. Int l = 0; Двоичный поиск позволяет найти индекс числа k в отсортированном массиве, если этого числа в нем нет, то возвращается -1. Сначала мы сравниваем k с числом, находящимся в середине массива. Если k меньше этого числа, то дальше мы должны искать его в левой половине массива, если больше - то в правой половине. Далее k сравнивается с числом, находящимся в середине выбранной на предыдущем шаге половины массива и т.д. С каждой итерацией пространство поиска сужается вдвое. Возникает вопрос: сколько итераций необходимо будет проделать в наихудшем случае (т.е. когда в массиве так и не будет найдено число, равное k и не останется данных для сравнения). Мы видим, что после 1 итерации останется \(N/2\) данных для поиска индекса \(k\), после 2 итерации останется \(N/4\) данных, после 3 итерации - \(N/8\) и т.д. Мы узнаем количество итераций в наихудшем случае, если решим уравнение \(\frac{N}{2^x}=1\). Это уравнение равносильно уравнению \(2^x=N\), отсюда \(x=log_{2}(N)\) или \(x=lg(N)\) (см. определение логарифма). Поэтому оценка сложности алгоритма бинарного поиска - \(O(logN)\). Хорошая новость заключается в том, что для характеризации времени выполнения большинства алгоритмов достаточно всего нескольких функций: \(1, logN, N, NlogN, N^2, N^3, 2^N\). На графике проиллюстрированы различные скорости роста времени выполнения алгоритма в зависимости от размера входных данных: Из этого графика, в частности, видно, что если время выполнения алгоритма "логарифмическое", т.е. алгоритм имеет сложность \(O(logN)\), то это очень круто, т.к. время его выполнения очень медленно растет с увеличением размера входных данных, если время выполнения линейно зависит от размера входных данных, то это тоже неплохо, а вот алгоритмы с экспоненциальным временем работы (\(O(2^N)\)) лучше не использовать совсем или использовать только на данных очень малого размера. классы P и NP
Вещественная неотрицательная функция \(f(m)\), определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином \(P(m)\) с вещественными коэффициентами такой, что \(f(m) \leq P(m)\) для всех \(m \in N^+\). Задачи, для которых существуют алгоритмы с "полиномиальным" временем работы принадлежат классу P (эти задачи в основном решаются быстро и без каких-либо проблем). Формальное определение.
Язык L принадлежит классу P, тогда и только тогда, когда существует детерминированная машина Тьюринга M, такая, что: При любых входных данных M заканчивает свою работу за полиномиальное время, Задачи класса NP
- задачи, удовлетворяющие условию: если имеется ответ (возможное решение), то его легко верифицировать - проверить, является оно решением или нет. Рассмотрим пример задачи из класса NP. Пусть дано множество целых чисел, например, {-7,-3, -2, 5, 8}. Требуется узнать, есть ли среди этих чисел 3 числа, которые в сумме дают 0. В данном случае ответ "да" (например, такой тройкой являются числа {-3,-2,5}. При возрастании размера множеств целых чисел количество подмножеств, состоящих из 3 элементов, экспоненциально возрастает. Между тем, если нам дают одно такое подмножество (его еще называют сертификатом), то мы легко можем проверить, равна ли 0 сумма его элементов. Формальное определение:
Язык L принадлежит классу NP, тогда и только тогда, когда существуют такие полиномы \(p\) и \(q\) и детерминированная машина Тьюринга M, такие, что: Для любых \(x,y\) машина M на входных данных \((x,y)\) выполняется за время \(p(|x|)\), Полиномиальная сводимость
или сводимость по Карпу. Функция \(f_1\) сводится к функции \(f_2\), если существует функция \(f \in P\), такая, что для любого \(x\) \(f_{1}(x)=f_{2}(f(x))\). Задача T называется NP-трудной
, если для нее существует такая NP-полная задача, которая сводится к T за полиномиальное время. Здесь имеется в виду сводимость по Куку. Сведение задачи \(R_1\) к \(R_2\) по Куку - это полиномиальный по времени алгоритм, решающий задачу \(R_1\) при условии, что функция, находящая решение задачи \(R_2\), ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг. Вот возможные соотношения между вышеупомянутыми классами задач (ученые до сих пор не уверены, совпадает ли P и NP). Функция сложности
0(1). В алгоритмах константной сложности большинство операций в программе выполняются один или несколько раз. Любой алгоритм, всегда требующий (независимо от размера данных) одного и того же времени, имеет константную сложность. Функция сложности 0(N).
Время работы программы обычно линейно, когда каждый элемент входных данных требуется обработать лишь линейное число раз. Эта функция сложности характеризует простой цикл. Функция сложности 0(N 2), 0(N
3), 0(№) -
полиномиальная функция сложности: число операций растет пропорционально квадрату N.
В общем случае может быть О(Л^) в зависимости от сложности задачи. Эта функция сложности характеризует сложный цикл. Функция сложности
O(Log 2 (A0), 0(N
log 2 (A0). Такое время работают алгоритмы, которые делят большую проблему на множество небольших, а затем, решив их, объединяют решения. Функция сложности 0(e N).
Алгоритмы с экспоненциальной сложностью чаще всего возникают в результате подхода, именуемого методом грубой силы. Функция сложности 0(М) -
число операций растет пропорционально факториалу N.
Программист должен уметь проводить анализ алгоритмов и определять их сложность. Временная сложность алгоритма может быть подсчитана исходя из анализа его управляющих структур. Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Если нет рекурсии и циклов, все управляющие структуры могут быть сведены к структурам константной сложности. Следовательно, и весь алгоритм также характеризуется константной сложностью. Определение сложности алгоритма, в основном, сводится к анализу циклов и рекурсивных вызовов. Например, рассмотрим алгоритм обработки элементов массива. For /": = 1 to N
do Begin Сложность этого алгоритма О
(А), так как тело цикла выполняется А раз, и сложность тела цикла равна 0(1). Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. For /: = 1 to N
do For j: =
1 to N
do Begin Сложность этой программы 0(N 2).
Пример 1.
Оценим сложность программы, вводящей с клавиатуры массив и находящей в нем наибольший элемент. Алгоритм состоит из следующих шагов: Сложим число операций А + (А - 1) + 1 = 2А, т.е. существует такая константа, что при любом А число операций не превышает СА. Следовательно, сложность алгоритма равна 0(A). Пример 2.
Оценим сложность программы, вводящей с клавиатуры массив и находящей в нем элемент с заданным свойством (например, равный определенному значению). Алгоритм состоит из следующих шагов: В лучшем случае указанный алгоритм потребует А + 2 операции (ввод всего массива, единственное сравнение, вывод), в худшем (когда такого элемента нет, 2А + 1 операцию). Если А будет большим числом, к примеру порядка 10 6 , то единицей можно пренебречь. Следовательно, сложность алгоритма равна 0(N).
Пример 3.
Определим функцию сложности алгоритма шифрования слова длиной L
методом подстановки. Пусть существует таблица, в которой для каждого символа алфавита записан символ, на который его надо заменить. Обозначим число букв алфавита S.
Алгоритм состоит из следующих шагов: Общее число операций 1 + (S +)L.
В случае достаточно больших S
и L
единицами можно пренебречь, и получится, что функция сложности приведенного алгоритма есть O(S L).
Пример 4.
Определим функцию сложности алгоритма перевода натурального числа 1
V в двоичную систему счисления (без операций ввода и вывода данных). Алгоритм состоит из следующих шагов: Общее число операций не превышает 1 + log 2 A. Поэтому описанный алгоритм имеет сложность 0(og 2 N).
Нам уже известно, что правильность - далеко не единственное качество,
которым должна обладать хорошая программа
. Одним из важнейших является
эффективность, характеризующая прежде всего время выполнения
программы
для различных входных данных (параметра ). Нахождение точной зависимости для конкретной программы
- задача
достаточно сложная. По
этой причине обычно ограничиваются асимптотическими оценками
этой функции, то есть описанием ее примерного
поведения при больших значениях параметра . Иногда для
асимптотических
оценок используют традиционное отношение
(читается "О
большое") между
двумя функциями В качестве первого примера вернемся к только что рассмотренным программам
нахождения факториала числа.
Легко видеть, что количество операций, которые должны быть
выполнены для нахождения факториала ! числа в
первом приближении
прямо пропорционально этому числу, ибо количество повторений цикла
(итераций)
в данной программе равно . В подобной ситуации принято говорить,
что
программа
(или алгоритм
) имеет линейную сложность
(сложность или ). Можно ли вычислить факториал
быстрее? Оказывается, да. Можно написать такую
программу, которая будет давать правильный результат для тех же значений ,
для которых это делают все приведенные выше программы, не используя при этом ни
итерации, ни рекурсии. Ее сложность будет , что
фактически означает
организацию вычислений по
некоторой формуле без применения циклов и рекурсивных
вызовов! Не менее интересен и пример вычисления -го числа Фибоначчи
. В
процессе
ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной
и равна . Подобные программы
практически
не применимы на практике. В этом очень легко убедиться, попробовав вычислить
с ее помощью 40-е число Фибоначчи
. По
этой причине вполне актуальна
следующая задача. Задача 5.4
линейную сложность
. Вот решение этой задачи, в котором переменные j
и k
содержат
значения двух последовательных чисел Фибоначчи. Текст программы
public class FibIv1 {
public static void main(String args) throws Exception {
int n = Xterm.inputInt("Введите n -> < 0) {
Xterm.print(" не определено\n");
} else if (n < 2) {
Xterm.println(" = " + n);
} else {
long i = 0;
long j = 1;
long k;
int m = n;
while (--m > 0) {
k = j;
j += i;
i = k;
}
Xterm.println(" = " + j);
}
}
} Следующий вопрос вполне естественен - а можно
ли находить числа Фибоначчи
еще быстрее? После изучения определенных разделов математики совсем просто вывести
следующую формулу для -ого числа Фибоначчи
,
которую
легко проверить для небольших значений : Может показаться, что основываясь на ней, легко написать
программу со сложностью , не использующую итерации или
рекурсии. Текст программы
public class FibIv2 {
public static void main(String args) throws Exception {
int n = Xterm.inputInt("Введите n -> ");
double f = (1.0 + Math.sqrt(5.)) / 2.0;
int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5);
Xterm.println("f(" + n + ") = " + j);
}
} На самом деле эта программа
использует вызов функции
возведения в степень
{ Math.pow(f,n)
}, которая не может быть реализована быстрее, чем
за логарифмическое время (). Про алгоритмы, в которых
количество
операций примерно пропорционально (в информатике принято
не указывать
основание
двоичного логарифма) говорят, что они имеет логарифмическую
сложность
(). Для вычисления -го числа Фибоначчи
существует такой алгоритм
,
программную
реализацию которого мы приведем без дополнительных комментариев, - иначе
нужно объяснять слишком много ( связь
чисел Фибоначчи со степенями некоторой
матрицы порядка два, использование классов для работы с матрицами, алгоритм
быстрого возведения матрицы в степень). Задача 5.5
. Напишите программу, печатающую -ое число Фибоначчи
, которая имела бы
логарифмическую сложность
. Текст программы
public class FibIv3 {
public static void main(String args) throws Exception {
int n = Xterm.inputInt("Введите n -> ");
Xterm.print("f(" + n + ")");
if (n < 0) {
Xterm.println(" не определено");
} else if (n < 2) {
Xterm.println(" = " + n);
} else {
Matrix b = new Matrix(1, 0, 0, 1);
Matrix c = new Matrix(1, 1, 1, 0);
while (n>0) {
if ((n&1) == 0) {
n >>>= 1; c.square();
} else {
n -= 1; b.mul(c);
}
}
Xterm.println(" = " + b.fib());
}
}
}
class Matrix {
private long a, b, c, d;
public Matrix(long a, long b, long c, long d) {
this.a = a; this.b = b; this.c = c; this.d = d;
}
public void mul(Matrix m) {
long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d;
long c1 = c*m.a+d*m.c; long d1 = c*m.b+d*m.d;
a = a1; b = b1; c = c1; d = d1;
}
public void square() {
mul(this);
}
public long fib() {
return b;
}
} Если попробовать посчитать десятимиллионное число Фибоначчи
с помощью этой
и предыдущей программ, то разница во времени счета будет вполне очевидной.
К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности
диапазона чисел типа long
. В заключение приведем сравнительную таблицу времен выполнения алгоритмов
с различной сложностью и объясним, почему с увеличением быстродействия
компьютеров важность использования быстрых алгоритмов значительно
возрастает. Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности , , и
соответственно. Предположим, что второй из этих
алгоритмов требует для своего выполнения на некотором компьютере при значении
параметра ровно одну минуту времени. Тогда времена
выполнения всех
этих четырех алгоритмов на том же компьютере при различных значениях параметра
будут примерно такими, как в 10 300000
лет
Когда начинающие программисты тестируют свои программы, то значения
параметров,
от которых они зависят, обычно невелики. Поэтому даже если при написании
программы был применен неэффективный алгоритм
, это может остаться незамеченным.
Однако, если подобную программу попытаться применить в реальных условиях,
то ее практическая непригодность проявится незамедлительно. С увеличением быстродействия компьютеров возрастают и значения параметров,
для которых работа того или иного алгоритма завершается за приемлемое время.
Таким образом, увеличивается среднее значение
величины , и,
следовательно,
возрастает величина отношения времен выполнения быстрого и медленного
алгоритмов. Чем быстрее компьютер, тем больше относительный
проигрыш при использовании плохого алгоритма
!
for (j = i + 1; j < N; j ++){
sequence of statements
}
}
0 N
1 N-1
2 N-2
...
N-1 1
Т.е. этот алгоритм будет иметь сложность \(O(N^2)\).
Если время выполнения метода \(g(N)=O(N)\), то \(T(N) = O(N)*O(N) = O(N^2)\).
int u = A.length - 1
int m;
while (l <= u) {
m = l + (u - 1)/2
if A[m] < k {
l = m +1;
}
else if A[m] == k {
return m;
}
else{
u = m - 1;
}
}
return -1;
- для всех \(x \in L\) M выдает результат 1,
- для всех \(x\), не принадлежащих \(L\), M выдает результат 0.
- для любого \(x \in L\) существует строка \(y\) длины \(q(|x|)\), такая что \(M(x,y)=1\),
- для любого \(x\) не из \(L\) и всех строк длины \(q(|x|)\) \(M(x,y)=0\).
Задача T называется NP-полной
, если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время. Пожалуй, наиболее известным примером NP-полной задачи является задача SAT(от слова satisfiability). Пусть дана формула, содержащая булевы переменные, операторы "И", "ИЛИ", "НЕ" и скобки. Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь
и истина
так, чтобы формула приняла значение "истина
".
,
определение
которого можно найти в любом учебнике по
математическому анализу,
хотя чаще применяют отношение эквивалентности
(читается
"тэта
большое").
Его формальное определение
есть, например, в книге , хотя нам
пока достаточно будет понимания данного вопроса в общих чертах.
