Что такое полиномиальное время

Какой смысл понятия «полиномиальное время»?

А в оценке сложности алгоритмов оно тут как?

Типа N*log(N) — это полином?

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

То есть если время равно N + log(N)*N + N*N*N*(N/10), то это полиномиальное время?

А если N в степени N, то уже экспоненциальное и не полиномиальное?

Это значит O(n^k) для некого неотрицательного k.

Если для любого входа количество операций при выполнении алгоритма не больше какого-то полинома от размера входа

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

Но реальное время одной операции может быть разной.

Берется некая машина, на которой определен некий набор операций, каждая из которых выполняется за 1 условный такт, это если придираться.

Это, как бы, понятно. Не понятно, как это соотностися с реальностью. Грубо говоря, для любой машины такт — это шаг вычисления, например, 1 редукция в лямбда машине. Но к реальному времени вычисления это не имеет отношения. Поэтому и толк этих полиномов весьма сомнителен.

Царь что ли? Оценка нужна, чтобы знать, как будет себя вести алгоритм, когда у тебя данных станет в k раз больше.

это что значит? расшифруй

Смысл в оценке изменения требуемого времени при изменении количества входных данных.

Предположим, что у нас некий кусок кода выполняется 10 секунд для ста элементов, а другой для того же количества аж 30 секунд. Вроде первый лучше, но если у него сложность O(n) против O(log(n)) у другого и если потребуется обработать пару миллиардов элементов, то на линейной сложности наступит ад израиль в отличии от логарифмической.

Делаешь ты крутой вебсайт, алгоритм у тебя O(N), 100 пользователей, страница генерится за секунду. Через год у тебя 10000 пользователей, страницу никто и не ждёт (генерация 100 секунд). Сосед твой сделал такой же сайт, страницы генерится две секунды, но алгоритм O(ln N), через год у него тоже рост со ста до 10000 юзеров, но страница генеритя 4 секундсы и всё норм.

По-моему, чтобы оценивать такие вещи, никаких матанов не надо. Типа, на какой структуре поиск будет эффективней, на списке, или на массиве? Надо подумать, покумекать, посчитать полиномы в вакууме, короче, все это муде.

Ладно, я понял короче смысл, спасибо.

Не кумекать надо, а пользоваться формально проработанными теориями.

К реальности это относится в «относительном» смысле. Вы можете сравнивать алгоритмы до их реализации. Сказать, что один в среднем требует больше времени, чем другой. И тогда на реальной машине запиливаете тот, который победил в соревновании.

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

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

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

N*log(N) — это неполиномиальная сложность, но для любого a>0 найдется такое N, что будет выполнены неравенства

N*log(N) — это неполиномиальная сложность, но для любого a>0 найдется такое N, что будет выполнены неравенства

Вот что ты начинаешь? Нормально же общались(даже с анонимусом). Специально для буквоедов: это ты про О или про тету?

Не угадал автора по заголовку!

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

Вот да, и теги неправильные к тому же. И слишком мало жаваскрипта в тексте.

Важно понимать, что это именно сложность алгоритма (в математическом смысле), а не его реализации.

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

А в оценке сложности алгоритмов оно тут как?

Euler diagram for P, NP, NP-complete, and NP-hard set of problems. © (картинка справа).

[troll]ну, раз понимаешь, расскажи мне, что такое переменная и что такое константа[/troll]

и, кстати, переменных может быть больше одной.

кстати, знак равенства в случае с O-обозначениями несимметричен, т.е. O(N^2) = O(N*log N) неверно

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

В таком случае, какой прок от этого «знания»

Чтобы знать, как это время исполнения будет изменяться при изменении размера входных данных.

Это, как бы, понятно. Не понятно, как это соотностися с реальностью. Грубо говоря, для любой машины такт — это шаг вычисления, например, 1 редукция в лямбда машине. Но к реальному времени вычисления это не имеет отношения. Поэтому и толк этих полиномов весьма сомнителен.

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

В данном случае, за шаг вычисления можно считать как кладку одного зернышка, так и заполнение клетки, все зависит от точки зрения. Вот у тебя и получиться, что алгоритм одновременно линейный и нелинейный. Парадокс.

Мне больше нравится реальный пример с возведением в степень. Можно возвести число в четвёртую степень тупо тремя умножениями, а можно, посчитав квадрат, умножить его сам на себя — итого всего два умножения. Так, увеличивая показатель степени до, скажем, 1024, первый способ потребует 1023 умножения, второй же всего 10.

В данном случае, за шаг вычисления можно считать как кладку одного зернышка, так и заполнение клетки, все зависит от точки зрения. Вот у тебя и получиться, что алгоритм одновременно линейный и нелинейный. Парадокс.

Ну как бы надо представлять, как математическая модель соотносится с реальностью. Если у тебя реальные зернышки, которые надо точно пересчитать, то элементарной операцией будет «положить одно зерно на клетку». А если у тебя клетки доски это 128-битные целые числа в памяти компьютера, то естественно считать элементарными операциями битовый сдвиг и присваивание.

Не от точки зрения, а от определений и аксиоматики.

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

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

И потом уже всякие страуструпы говорят своим школьничкам не юзать «списки». Хотя со списками та ещё история, ибо школьнички не понимают разницу между произвольным доступом и доступом в списке. У пацанов случается O(1).

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

То есть Ъ цари велосипедят идеальную реализацию поиска брутфорсом, не заморачиваясь с какими-то там несуществующими алгоритмическими сложностями? Не удивительно, что кроме слабоосмысленного кукареканья про лалок на лоре от них никакого полезного выхлопа.

В таком случае, какой прок от этого «знания»

А возведение в квадрат чем-то отличается от умножения самого на себя?

А как с понятием «полином» связано полиномиальное время?

Ничем. Мы лишь мыслим здесь в терминах умножения, чтобы не запутывать.

Напрямую: сложность некого алгоритма ограничена сверху неким полиномом.

Я выше писал про https://ru.wikipedia.org/wiki/Алгоритм_быстрого_возведения_в_степень
Сейчас ты скажешь про экспоненту, но возводить в степень нужно, например, и матрицы.

И полиномиальная (N^k) и квадратичная (её частный случай k=2) — это всё примеры асимптотических сложностей алгоритмов, да.

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

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

Шизофрения не лечится, но ее симптомы купируются медикаментозно. Не забывай свои таблеточки принимать, дурень!

потом каким-то мистическим способом сравнивается с чем-то

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

А вот вопрос, а с чего кто-то решил, что я не додумаюсь множить квадраты?

Это же детский пример. Просто до КМП тебе уже умишка не хватит додуматься. Между тем, алгоритм подобного класса используется во всём, начиная с strstr. Казалось бы зачем, если ко-ко-кэши?

В реальном мире представление какого-нибудь социального графа может занимать десятки гигабайт и более. И даже какой-нибудь сраный Дейкстра будет работать на нём хоть как-нибудь приемлемо быстро только с использованием фибоначчиевых куч. А до тех пор ты просто соснёшь со своей реализацией.

где-то за пределами лабы школьника и куллстори среди домохозяек

Печально, что ты настолько же упрям, насколько невеж. Ты просто никак не можешь понять, что у кого-то данных может быть больше 640 Кб, которых хватит всем. И тогда всем вдруг становится пофиг на большие константы сложных алгоритмов, асимптотика и только она (зачастую амортизированная) начинает играть первостепенную роль. Вот тебе популярным языком: http://postnauka.ru/video/42416

Как минимум, чтобы найти в графе пути длины n.

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

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

Это же детский пример. Просто до КМП тебе уже умишка не хватит додуматься.

Между тем, алгоритм подобного класса используется во всём, начиная с strstr.

В реальном мире представление какого-нибудь социального графа может занимать десятки гигабайт и более.

Который ты никогда не писал и мне не покажешь, а так кукарекать конечно мастер.

Собственно вся суть о которой я уже 10раз писал. Школьник ничего, кроме лабы на пару метров не видел, но рассуждает.

И даже какой-нибудь сраный Дейкстра будет работать на нём хоть как-нибудь приемлемо быстро только с использованием фибоначчиевых куч. А до тех пор ты просто соснёшь со своей реализацией.

Я тебе и с кнутом предлагал обосраться на реальной задаче. Но почему-то от вас, кроме как курлык-курлык я ничего не слышу.

Печально, что ты настолько же упрям, насколько невеж. Ты просто никак не можешь понять, что у кого-то данных может быть больше 640 Кб, которых хватит всем. И тогда всем вдруг становится пофиг на большие константы сложных алгоритмов, асимптотика и только она (зачастую амортизированная) начинает играть первостепенную роль.

Выкатывай задачу, в которой не хватит 640кб. Конкретную задачу.

Пока что я ничего не вижу.

Как минимум, чтобы найти в графе пути длины n.

Почему я могу выкатить реальные задачи на которых кпм, да и всё это говно обосрёться, а ты обратные нет?

Ну и по теме ответов я так и не увидел.

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

Источник

Полиномиальное время как показатель эффективности

Когда аналитики только начали заниматься анализом дискретных алгоритмов (а эта область исследований стала набирать темп в 1960-е годы), у них начал формироваться консенсус относительно того, какой количественной оценкой можно описать концепцию «разумного» времени выполнения.

Время поиска в естественных комбинаторных задачах склонно к экспоненциальному росту относительно размера N входных данных; если размер увеличивается на единицу, то количество возможностей возрастает мультипликативно.

Предположим, алгоритм обладает следующим свойством: существуют такие абсолютные константы c > 0 и d > 0, что для любого набора входных данных N время выполнения ограничивается cNd примитивными вычислительными шагами. (Иначе говоря, время выполнения не более чем пропорционально Nd.)

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

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

Обратите внимание: любая граница с полиномиальным временем обладает искомым свойством масштабирования. Если размер входных данных возрастает с N до 2N, то граница времени выполнения возрастает с cNd до c(2N)d = c · 2dNd, что соответствует замедлению с коэффициентом 2d.

Так как d является константой, коэффициент 2d тоже является константой; как нетрудно догадаться, полиномы с меньшими степенями масштабируются лучше, чем полиномы с высокими степенями.

Из новых терминов и интуитивного замечания, изложенного выше, вытекает наша третья попытка сформулировать рабочее определение эффективности.

Предлагаемое определение эффективности (3): алгоритм считается эффективным, если он имеет полиномиальное время выполнения.

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

И неполиномиальное время выполнения n1+0,02(log n) покажется нам относительно приемлемым? Конечно, в обоих случаях ответ будет положительным. В самом деле, как бы мы ни старались абстрактно оправдать определение эффективности в контексте полиномиального времени, главное оправдание будет таким: это определение действительно работает.

У задач, для которых существуют алгоритмы с полиномиальным временем, эти алгоритмы почти всегда работают с временем, пропорциональным полиномам с умеренной скоростью роста, такой как n, n log n, n2 или n3.

И наоборот, задачи, для которых алгоритм с полиномиальной скоростью неизвестен, обычно оказываются очень сложными на практике.

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

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

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

Источник

NP-полнота

Построение и анализ алгоритмов.

Введение

Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.

Полиномиальное время

Абстрактные задачи

Как уже упоминалось, понятие полиномиально разрешимой задачи принято считать уточнением идеи «практически разрешимой» задачи. Чем объясняется такое соглашение? Во-первых, используемые на практике полиномиальные алгоритмы обычно действительно работают довольно быстро. Второй аргумент в пользу рассмотрения класса полиномиальных алгоритмов — тот факт, что объем этого класса практически не зависит от выбора конкретной модели вычислений. Например, класс задач, которые могут быть решены за полиномиальное время на последовательной машине с произвольным доступом (RAM), совпадает с классом задач, полиномиально разрешимых на машинах Тьюринга. Класс будет тем же и для модели параллельных вычислений, если, конечно, число процессоров ограничено полиномом от длины входа. В-третьих, класс полиномиально разрешимых задач обладает естественными свойствами замкнутости. Например, композиция двух алгоритмов также работает полиномиальное время. Это объясняется тем, что сумма, произведение и композиция многочленов есть многочлен.

Часто встречаются — задачи, в которых требуется максимизировать или минимизировать значение некоторой величины. Прежде чем ставить вопрос о NP-полноте таких задач, их следует преобразовать в задачи разрешения. Так, например, в задаче о поиске кратчайшего пути в графе мы перешли от задачи оптимизации к задаче разрешения, добавив ограничение на длину пути. Если после преобразования получается NP-полная задача, то тем самым установлена и трудность исходной задачи.

Представление данных

Прежде чем подавать на вход алгоритма исходные данные (то есть элемент множества I ), надо договориться о том, как они представляются в «понятном для компьютера виде». Будем считать, что исходные данные закодированы последовательностью битов. Формально говоря, элементов некоторого множества S называется отображение e из S во множество битовых строк. Например, целые числа 0, 1, 2, 3, … обычно представляются битовыми строками 0, 1, 10, 11, 100, …

Формальные языки

Теорема

Проверка принадлежности языку и класс NP

Гамильтонов цикл

Проверка принадлежности языку

Сложностной класс NP

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

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

NP-полнота и сводимость

Наиболее убедительным аргументом в пользу того, что классы P и NP различны, является существование так называемых NP-полных задач. Этот класс обладает тем важным свойством, что если какая-нибудь NP-полная задача разрешима за полиномиальное время, то и все задачи из класса NP разрешимы за полиномиальное время, то есть P = NP. В частности, задача HAM-CYCLE является NP-полной. Таким образом, научившись решать ее за полиномиальное время, мы получим полиномиальные алгоритмы для всех задач класса NP. Неформально говоря, NP-полные языки являются самыми «трудными» в классе NP. При этом трудность языков можно сравнивать, сводя один язык к другому. Метод сведения является основным при доказательстве NP-полноты многих задач.

Сводимость

Неформально, задача Q сводится к задаче Q ′, если задачу Q можно решить для любого входа, считая известным решение задачи Q ′ для какого-то другого входа. Например, задача решения линейного уравнения сводится к задаче решения квадратного уравнения.

Лемма

Если язык L ₁ ⊂ <0, 1>* сводится за полиномиальное время к языку L ₂ ⊂ <0, 1>* и L ₂ ⊂ P, то L ₁ ⊂ P.

Доказательство. Пусть A ₂ — полиномиальный алгоритм, распознающий язык L ₂, а F — полиномиальный алгоритм, сводящий язык L ₁ к языку L ₂. Построим алгоритм A ₁, который будет за полиномиальное время разрешать язык L ₁, согласно нижепреведенной иллюстрации, а именно: получив на вход x ∈ <0, 1>*, алгоритм A ₁ (с помощью алгоритма F ) получает f ( x ) и с помощью алгоритма A ₂ проверяет, принадлежит ли слово f ( x ) языку L ₂. Результат работы алгоритма A ₂ на основе f ( x ) и выдается алгоритмом A ₁ в качестве ответа. Определение полиномиальной сводимости гарантирует, что алгоритм A ₁ дает правильный ответ; он полиномиален, поскольку полиномиальны алгоритмы F и A ₂.

NP-полнота

Теорема

Если некоторая NP-полная задача разрешима за полиномиальное время, то P = NP. Другими словами, если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP-полные задачи таковы.

Таким образом, гипотеза P ≠ NP означает, что NP-полные задачи не могут быть решены за полиномиальное время. Видимо, это действительно так, а потому доказательство NP-полноты некоторой задачи является существенным аргументом в пользу ее практической неразрешимости.

Заключение

Итак, какой же практический смысл имеет изучение теории сложности и классификация задач с точки зрения NP-полноты? Ответ очевиден — зачастую гораздо разумнее и эффективнее найти доказательство того, что рассматриваемая задача принадлежит к классу NP-полных, и в соответствие с этим заняться поиском достаточно точных приближенных алгоритмов, нежели безрезультатно тратить время на отыскание полиномиальных алгоритмов ее решения. Ясно, что именно NP-полные задачи играют здесь центральную роль — дело в том, что полиномиальное время является, хоть и первым, но достаточно хорошим приближением понятия «практической разрешимости задачи».

Как уже было упомянуто ранее, определяющим источником данной статьи является [1]. Однако существует немало других интересных книг по данной тематике, заслуживающих пристального внимания со стороны читателя. Среди них хотелось бы выделить [2], где можно найти большое разнообразие NP-полных задач из самых различных областей. Читателям, желающим подробнее ознакомиться с теорией сложности, на мой взгляд, будет интересен подробный курс лекций [3], глубоко освещающий данную тематику.

Источник