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

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

То есть если время равно 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 < N*log(N) < N^(1+a)

Т.е. твой алгоритм асимптотически медленнее любого линейного, но быстрее любого суперлинейного.

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

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

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

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

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

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

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

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

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

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

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

Вот представь что ты пылесосишь ковёр. Ты посчитал время за которое ты пропылисосил квадратный метр ковра и примерно можешь прикинуть за сколько ты пропылисосишь 10 метров квадратных этого ковра. Тут вообще у тебя линейная сложность. Во сколько раз увеличилась площадь, по столько и увеличилось время. А вот во втором случае ты раскладываешь зернышки пшеницы на клеточки шахматной доски. На первую кладешь одно зёрнышко, на вторую - два, на третью - 4... И времени на то чтобы положить это зёрнышко тебе надо 1 секунду. А теперь скажи, когда ты закончишь раскладывать зёрна? Солнце ещё не погаснет? Тут у тебя не линейная сложность и время не полиномиальное.

Чё такое полином я понимаю - это сумма разных степеней одной переменной с коэффициентами константными

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

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

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

N*log(N) - это не полином, во всяком случае не полином от одной переменной N. тем не менее, для оценки алгоритмов обычно используется верхняя асимптотическая оценка, и O(N*log N) - это как ни странно полиномиальное время, т.к. N*log(N) < N^2 с точностью до константы при N->бесконечности, т.е. O(N*log N) = O(N^2)

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

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

Возьми и померяй.

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

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

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

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

На первую кладешь одно зёрнышко, на вторую - два, на третью - 4... И времени на то чтобы положить это зёрнышко тебе надо 1 секунду.

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

Тебе надо доску заполнять (8 на 8). Элемент - клетка.

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

На первую кладешь одно зёрнышко, на вторую - два, на третью - 4... И времени на то чтобы положить это зёрнышко тебе надо 1 секунду.

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

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

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

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

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

Никаких нахрен днище O(n) и O(log(n)) в реальном мире нет - это проявление того, что ты просто нулёвый балабол.

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

Тут уже начинаются не массивы и вуаля, а для не массивов никаких нахрен O(n) в общем случае нет. Тут балабол серанул. Тут уже брёвна/хеш-индексация и прочее, но алгоритмическая разница - тут максимум порядок.

Тут уже начинается, что нихрена логарифма нет, ибо балансировка. Это ещё тонна жопы к константе. Хешец - 2^длинна хеша байт адресспейса и по в среднем два-три порядка оверхеда по памяти. И жопа с константной, ибо летенси. Т.е. примерно в 10гиговый по памяти хешмап влезает данных на llc текущих камней - т.е. 1-2 порядка по летенси.

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

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

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

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

Царь что ли?

Нет, тут всё хуже:

java

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

Никаких нахрен днище O(n) и O(log(n)) в реальном мире нет - это проявление того, что ты просто нулёвый балабол.

Что за пиздец? Есть это в реальной жизни.

А не полиномиальная сложность - это не про асимптотическую сложность? Квадратичная сложность - не про асимптотическую?

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

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

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

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

Что за пиздец? Есть это в реальной жизни.

Примеры осилишь, аль как и предыдущие - обосрёшься?

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

А не полиномиальная сложность - это не про асимптотическую сложность? Квадратичная сложность - не про асимптотическую?

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

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

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

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

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

Допустим не один ракал не понимает, что линейным поиском можно искать сразу дохренуа значений - те же нюансы.

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

Т.е. где-то за пределами лабы школьника и куллстори среди домохозяек - она нахрен не упала. Ничего не даёт. Это вещь совершенно с другого, не прикладного уровня.

Школьники пихают её в основном потому, что 99% из них не понимают, что эта днищесистема не оценивает время, а оценивает рост, которая сам по себе не имеет смысла без оценки времени и n. Понимай они хотябы это - такой херни бы не происходило, а пока пичаль. Ну и примитивная подмена понятия «против днищесистемыоценкидляшкольников == против алгоритмической потимизации» и прочее. У тебя похоже с этим тоже проблема.

Ну и да, я не понимаю - а нахрена нужна эта степень?

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

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

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

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

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

Разбросы данных минимальны - в реальном мире всё упирается в реализацию.

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

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

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

Ну и да, я не понимаю - а нахрена нужна эта степень?

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

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

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

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

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

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

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

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

Казалось бы зачем, если ко-ко-кэши?

Незачем. Только на лабе. В реальном жизни нахрен не нужно, так где нужно - кмп нахрен не нужно.

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

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

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

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

Меня не интересуют рассуждения без конкретики. Есть задачка - выкатывай - обосрёшься, авось что-то поймёшь.

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

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

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

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

Вот тебе популярным языком: http://postnauka.ru/video/42416

Матрица на вектор. Ой, а вот мы и нашли задачку, правда к реальности не имеет никакого отношения. Давай ты мне покажешь «не 640кб» - выкатывай задачу.

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

Конкретно - выкатывай.

Вся суть балаболов. Кукареку есть - утверждения есть - конкретики нет.

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

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

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

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

это не разделяй и властвуй