Вычислительная сложность

Поделись знанием:
Перейти к: навигация, поиск

Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжёра длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжера).

В частности, теория сложности вычислений определяет NP-полные задачи, которые недетерминированная машина Тьюринга может решить за полиномиальное время, тогда как для детерминированной машины Тьюринга полиномиальный алгоритм неизвестен. Обычно это сложные задачи оптимизации, например, задача коммивояжёра.

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





Временная и пространственная сложности

Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа.

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

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

Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).

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

Асимптотическая сложность

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

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

Обозначение Интуитивное объяснение Определение
<math>f(n) \in O(g(n))</math> <math>f</math> ограничена сверху функцией <math>g</math> (с точностью до постоянного множителя) асимптотически f(n)| \leq |Cg(n)| </math> или <math> \exists (C>0), n_0 : \forall(n>n_0) \; f(n) \leq Cg(n)</math>
<math>f(n) \in \Omega(g(n))</math> <math>f</math> ограничена снизу функцией <math>g</math> (с точностью до постоянного множителя) асимптотически Cg(n)| \leq |f(n)|</math>
<math>f(n) \in \Theta(g(n))</math> <math>f</math> ограничена снизу и сверху функцией <math>g</math> асимптотически Cg(n)| < |f(n)| < |C'g(n)| </math>
<math>f(n) \in o(g(n))</math> <math>g</math> доминирует над <math>f</math> асимптотически f(n)| < |Cg(n)|</math>
<math>f(n) \in \omega(g(n))</math> <math>f</math> доминирует над <math>g</math> асимптотически Cg(n)| < |f(n)|</math>
<math>f(n) \sim g(n)</math> <math>f</math> эквивалентна <math>g</math> асимптотически <math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1</math>

Примеры

  • «почистить ковёр пылесосом» требует время, линейно зависящее от его площади (<math>\Theta(A)</math>), то есть на ковёр, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз объём работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
  • «найти имя в телефонной книге» требует всего лишь времени, логарифмически зависящего от количества записей (<math>O(\log_2(n))</math>), так как, открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге объёмом в 1000 страниц любое имя находится не больше, чем за <math>\log_2 1000 \approx 10</math> раз (открываний книги). При увеличении объёма страниц до ста тысяч проблема все ещё решается за <math>\log_2 100000 \approx 17</math> заходов. (См. Двоичный поиск.)

Замечания

Поскольку <math>\log_a b = \frac{\log_c b}{\log_c a}</math>, в асимптотической оценке сложности часто пишут «логарифм» без упоминания основания — например, <math>O(n \log n)</math>.

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

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

Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения[1]. Вместе с тем и понятие «малости» входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения, асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее «эффективных» алгоритмов. Другой пример — фибоначчиевы кучи, несмотря на асимптотическую эффективность, с практической точки зрения программная сложность реализации и большие значения констант в формулах времени работы делают их менее привлекательными, чем обычные бинарные деревья[1].

Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка nC, а при другом — порядка n+n!/C, где C — постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй — нет, хотя, например, при С=10(1010) дело обстоит как раз наоборот[2].
А. А. Зыков

Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ.

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

В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

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

Класс сложности — это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:

Класс P

Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть время решения которых полиномиально зависит от размера входа. Сюда относится сортировка, поиск в массиве, выяснение связности графов и многие другие.

Класс NP

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

Проблема равенства классов P и NP

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

Исследователи

См. также

Напишите отзыв о статье "Вычислительная сложность"

Примечания

  1. 1 2 Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, Клифорд. Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — ISBN 5-8459-0857-4.
  2. А. А. Зыков. Основы теории графов. — 3-е изд. — М.: Вузовская книга, 2004. — С. 10. — 664 с. — ISBN 5-9502-0057-8.

Ссылки

  • Гирш Э. А. «[compscicenter.ru/program/course/Cryptography2012 Сложность вычислений и основы криптографии]». Курс лекций описывающий основы сложности вычислений и криптографии.
  • Юрий Лифшиц «[yury.name/modern.html Современные задачи теоретической информатики]». Курс лекций по алгоритмам для NP-трудных задач.
  • А. А. Разборов [old.computerra.ru/print/offline/2001/379/6782/ Theoretical Computer Science: взгляд математика] // Компьютерра. — 2001. — № 2. ([www.mi.ras.ru/~razborov/computerra.ps альтернативная ссылка])
  • А. А. Разборов [www.mccme.ru/free-books/matpros/i4127141.pdf.zip О сложности вычислений] // Математическое просвещение. — МЦНМО, 1999. — № 3. — С. 127-141.


Отрывок, характеризующий Вычислительная сложность

– Я к тебе заезжал, – сказал Ростов, краснея.
Долохов не отвечал ему. – Можешь поставить, – сказал он.
Ростов вспомнил в эту минуту странный разговор, который он имел раз с Долоховым. – «Играть на счастие могут только дураки», сказал тогда Долохов.
– Или ты боишься со мной играть? – сказал теперь Долохов, как будто угадав мысль Ростова, и улыбнулся. Из за улыбки его Ростов увидал в нем то настроение духа, которое было у него во время обеда в клубе и вообще в те времена, когда, как бы соскучившись ежедневной жизнью, Долохов чувствовал необходимость каким нибудь странным, большей частью жестоким, поступком выходить из нее.
Ростову стало неловко; он искал и не находил в уме своем шутки, которая ответила бы на слова Долохова. Но прежде, чем он успел это сделать, Долохов, глядя прямо в лицо Ростову, медленно и с расстановкой, так, что все могли слышать, сказал ему:
– А помнишь, мы говорили с тобой про игру… дурак, кто на счастье хочет играть; играть надо наверное, а я хочу попробовать.
«Попробовать на счастие, или наверное?» подумал Ростов.
– Да и лучше не играй, – прибавил он, и треснув разорванной колодой, прибавил: – Банк, господа!
Придвинув вперед деньги, Долохов приготовился метать. Ростов сел подле него и сначала не играл. Долохов взглядывал на него.
– Что ж не играешь? – сказал Долохов. И странно, Николай почувствовал необходимость взять карту, поставить на нее незначительный куш и начать игру.
– Со мной денег нет, – сказал Ростов.
– Поверю!
Ростов поставил 5 рублей на карту и проиграл, поставил еще и опять проиграл. Долохов убил, т. е. выиграл десять карт сряду у Ростова.
– Господа, – сказал он, прометав несколько времени, – прошу класть деньги на карты, а то я могу спутаться в счетах.
Один из игроков сказал, что, он надеется, ему можно поверить.
– Поверить можно, но боюсь спутаться; прошу класть деньги на карты, – отвечал Долохов. – Ты не стесняйся, мы с тобой сочтемся, – прибавил он Ростову.
Игра продолжалась: лакей, не переставая, разносил шампанское.
Все карты Ростова бились, и на него было написано до 800 т рублей. Он надписал было над одной картой 800 т рублей, но в то время, как ему подавали шампанское, он раздумал и написал опять обыкновенный куш, двадцать рублей.
– Оставь, – сказал Долохов, хотя он, казалось, и не смотрел на Ростова, – скорее отыграешься. Другим даю, а тебе бью. Или ты меня боишься? – повторил он.
Ростов повиновался, оставил написанные 800 и поставил семерку червей с оторванным уголком, которую он поднял с земли. Он хорошо ее после помнил. Он поставил семерку червей, надписав над ней отломанным мелком 800, круглыми, прямыми цифрами; выпил поданный стакан согревшегося шампанского, улыбнулся на слова Долохова, и с замиранием сердца ожидая семерки, стал смотреть на руки Долохова, державшего колоду. Выигрыш или проигрыш этой семерки червей означал многое для Ростова. В Воскресенье на прошлой неделе граф Илья Андреич дал своему сыну 2 000 рублей, и он, никогда не любивший говорить о денежных затруднениях, сказал ему, что деньги эти были последние до мая, и что потому он просил сына быть на этот раз поэкономнее. Николай сказал, что ему и это слишком много, и что он дает честное слово не брать больше денег до весны. Теперь из этих денег оставалось 1 200 рублей. Стало быть, семерка червей означала не только проигрыш 1 600 рублей, но и необходимость изменения данному слову. Он с замиранием сердца смотрел на руки Долохова и думал: «Ну, скорей, дай мне эту карту, и я беру фуражку, уезжаю домой ужинать с Денисовым, Наташей и Соней, и уж верно никогда в руках моих не будет карты». В эту минуту домашняя жизнь его, шуточки с Петей, разговоры с Соней, дуэты с Наташей, пикет с отцом и даже спокойная постель в Поварском доме, с такою силою, ясностью и прелестью представились ему, как будто всё это было давно прошедшее, потерянное и неоцененное счастье. Он не мог допустить, чтобы глупая случайность, заставив семерку лечь прежде на право, чем на лево, могла бы лишить его всего этого вновь понятого, вновь освещенного счастья и повергнуть его в пучину еще неиспытанного и неопределенного несчастия. Это не могло быть, но он всё таки ожидал с замиранием движения рук Долохова. Ширококостые, красноватые руки эти с волосами, видневшимися из под рубашки, положили колоду карт, и взялись за подаваемый стакан и трубку.
– Так ты не боишься со мной играть? – повторил Долохов, и, как будто для того, чтобы рассказать веселую историю, он положил карты, опрокинулся на спинку стула и медлительно с улыбкой стал рассказывать:
– Да, господа, мне говорили, что в Москве распущен слух, будто я шулер, поэтому советую вам быть со мной осторожнее.
– Ну, мечи же! – сказал Ростов.
– Ох, московские тетушки! – сказал Долохов и с улыбкой взялся за карты.
– Ааах! – чуть не крикнул Ростов, поднимая обе руки к волосам. Семерка, которая была нужна ему, уже лежала вверху, первой картой в колоде. Он проиграл больше того, что мог заплатить.
– Однако ты не зарывайся, – сказал Долохов, мельком взглянув на Ростова, и продолжая метать.


Через полтора часа времени большинство игроков уже шутя смотрели на свою собственную игру.
Вся игра сосредоточилась на одном Ростове. Вместо тысячи шестисот рублей за ним была записана длинная колонна цифр, которую он считал до десятой тысячи, но которая теперь, как он смутно предполагал, возвысилась уже до пятнадцати тысяч. В сущности запись уже превышала двадцать тысяч рублей. Долохов уже не слушал и не рассказывал историй; он следил за каждым движением рук Ростова и бегло оглядывал изредка свою запись за ним. Он решил продолжать игру до тех пор, пока запись эта не возрастет до сорока трех тысяч. Число это было им выбрано потому, что сорок три составляло сумму сложенных его годов с годами Сони. Ростов, опершись головою на обе руки, сидел перед исписанным, залитым вином, заваленным картами столом. Одно мучительное впечатление не оставляло его: эти ширококостые, красноватые руки с волосами, видневшимися из под рубашки, эти руки, которые он любил и ненавидел, держали его в своей власти.
«Шестьсот рублей, туз, угол, девятка… отыграться невозможно!… И как бы весело было дома… Валет на пе… это не может быть!… И зачем же он это делает со мной?…» думал и вспоминал Ростов. Иногда он ставил большую карту; но Долохов отказывался бить её, и сам назначал куш. Николай покорялся ему, и то молился Богу, как он молился на поле сражения на Амштетенском мосту; то загадывал, что та карта, которая первая попадется ему в руку из кучи изогнутых карт под столом, та спасет его; то рассчитывал, сколько было шнурков на его куртке и с столькими же очками карту пытался ставить на весь проигрыш, то за помощью оглядывался на других играющих, то вглядывался в холодное теперь лицо Долохова, и старался проникнуть, что в нем делалось.
«Ведь он знает, что значит для меня этот проигрыш. Не может же он желать моей погибели? Ведь он друг был мне. Ведь я его любил… Но и он не виноват; что ж ему делать, когда ему везет счастие? И я не виноват, говорил он сам себе. Я ничего не сделал дурного. Разве я убил кого нибудь, оскорбил, пожелал зла? За что же такое ужасное несчастие? И когда оно началось? Еще так недавно я подходил к этому столу с мыслью выиграть сто рублей, купить мама к именинам эту шкатулку и ехать домой. Я так был счастлив, так свободен, весел! И я не понимал тогда, как я был счастлив! Когда же это кончилось, и когда началось это новое, ужасное состояние? Чем ознаменовалась эта перемена? Я всё так же сидел на этом месте, у этого стола, и так же выбирал и выдвигал карты, и смотрел на эти ширококостые, ловкие руки. Когда же это совершилось, и что такое совершилось? Я здоров, силен и всё тот же, и всё на том же месте. Нет, это не может быть! Верно всё это ничем не кончится».
Он был красен, весь в поту, несмотря на то, что в комнате не было жарко. И лицо его было страшно и жалко, особенно по бессильному желанию казаться спокойным.
Запись дошла до рокового числа сорока трех тысяч. Ростов приготовил карту, которая должна была итти углом от трех тысяч рублей, только что данных ему, когда Долохов, стукнув колодой, отложил ее и, взяв мел, начал быстро своим четким, крепким почерком, ломая мелок, подводить итог записи Ростова.
– Ужинать, ужинать пора! Вот и цыгане! – Действительно с своим цыганским акцентом уж входили с холода и говорили что то какие то черные мужчины и женщины. Николай понимал, что всё было кончено; но он равнодушным голосом сказал:
– Что же, не будешь еще? А у меня славная карточка приготовлена. – Как будто более всего его интересовало веселье самой игры.
«Всё кончено, я пропал! думал он. Теперь пуля в лоб – одно остается», и вместе с тем он сказал веселым голосом:
– Ну, еще одну карточку.
– Хорошо, – отвечал Долохов, окончив итог, – хорошо! 21 рубль идет, – сказал он, указывая на цифру 21, рознившую ровный счет 43 тысяч, и взяв колоду, приготовился метать. Ростов покорно отогнул угол и вместо приготовленных 6.000, старательно написал 21.
– Это мне всё равно, – сказал он, – мне только интересно знать, убьешь ты, или дашь мне эту десятку.
Долохов серьезно стал метать. О, как ненавидел Ростов в эту минуту эти руки, красноватые с короткими пальцами и с волосами, видневшимися из под рубашки, имевшие его в своей власти… Десятка была дана.
– За вами 43 тысячи, граф, – сказал Долохов и потягиваясь встал из за стола. – А устаешь однако так долго сидеть, – сказал он.
– Да, и я тоже устал, – сказал Ростов.
Долохов, как будто напоминая ему, что ему неприлично было шутить, перебил его: Когда прикажете получить деньги, граф?
Ростов вспыхнув, вызвал Долохова в другую комнату.
– Я не могу вдруг заплатить всё, ты возьмешь вексель, – сказал он.
– Послушай, Ростов, – сказал Долохов, ясно улыбаясь и глядя в глаза Николаю, – ты знаешь поговорку: «Счастлив в любви, несчастлив в картах». Кузина твоя влюблена в тебя. Я знаю.
«О! это ужасно чувствовать себя так во власти этого человека», – думал Ростов. Ростов понимал, какой удар он нанесет отцу, матери объявлением этого проигрыша; он понимал, какое бы было счастье избавиться от всего этого, и понимал, что Долохов знает, что может избавить его от этого стыда и горя, и теперь хочет еще играть с ним, как кошка с мышью.
– Твоя кузина… – хотел сказать Долохов; но Николай перебил его.
– Моя кузина тут ни при чем, и о ней говорить нечего! – крикнул он с бешенством.
– Так когда получить? – спросил Долохов.
– Завтра, – сказал Ростов, и вышел из комнаты.


Сказать «завтра» и выдержать тон приличия было не трудно; но приехать одному домой, увидать сестер, брата, мать, отца, признаваться и просить денег, на которые не имеешь права после данного честного слова, было ужасно.
Дома еще не спали. Молодежь дома Ростовых, воротившись из театра, поужинав, сидела у клавикорд. Как только Николай вошел в залу, его охватила та любовная, поэтическая атмосфера, которая царствовала в эту зиму в их доме и которая теперь, после предложения Долохова и бала Иогеля, казалось, еще более сгустилась, как воздух перед грозой, над Соней и Наташей. Соня и Наташа в голубых платьях, в которых они были в театре, хорошенькие и знающие это, счастливые, улыбаясь, стояли у клавикорд. Вера с Шиншиным играла в шахматы в гостиной. Старая графиня, ожидая сына и мужа, раскладывала пасьянс с старушкой дворянкой, жившей у них в доме. Денисов с блестящими глазами и взъерошенными волосами сидел, откинув ножку назад, у клавикорд, и хлопая по ним своими коротенькими пальцами, брал аккорды, и закатывая глаза, своим маленьким, хриплым, но верным голосом, пел сочиненное им стихотворение «Волшебница», к которому он пытался найти музыку.
Волшебница, скажи, какая сила
Влечет меня к покинутым струнам;
Какой огонь ты в сердце заронила,
Какой восторг разлился по перстам!
Пел он страстным голосом, блестя на испуганную и счастливую Наташу своими агатовыми, черными глазами.
– Прекрасно! отлично! – кричала Наташа. – Еще другой куплет, – говорила она, не замечая Николая.
«У них всё то же» – подумал Николай, заглядывая в гостиную, где он увидал Веру и мать с старушкой.
– А! вот и Николенька! – Наташа подбежала к нему.