Обсуждение:Вычислительная сложность

«Выход алгоритма»?

«как изменится время исполнения и объём занятой памяти в зависимости от размера входа и выхода?» Это как? Если задача всех алгоритмов сортировки — отсортировать все N строк, то корректным результатом будет вывод всех N строк в правильном порядке, а работать они будут в совершенно разных классах сложности. См. также енвики, там сказано коротко и ясно: «As the size of the input to an algorithm increases, how do the running time and memory requirements of the algorithm change [..]». Прошу объяснить, какой-такой «выход», определяющий сложность алгоритма. --Peni 20:51, 16 декабря 2008 (UTC)

Начнем с того, что в классах сложности P, NP и т.д. лежат задачи распознавания (см. en:Decision problem), у которых выход - это по сути один бит (да/нет). Поэтому в определении сложности для задач распознавания говорится только лишь о зависимости от размера входа. Сложность других вычислительных задач определяется сведением к задачам распознавания (см. en:Decision problem#Equivalence with function problems), при этом ожидаемый выход исходной задачи преобразуется к части входа задач распознавания и, таким образом, должен учитываться при определении сложности.

Вышесказанное можно проиллюстрировать на примере простой задачи: дано число n, вывести последовательно все числа от 1 до n. Решением этой задачи является простой цикл по переменной i от 1 до n, который на каждой итерации выводит число i. Этот алгоритм полиномиален от длины входа и выхода (которая есть $\Theta (n\ln n)$), но экспоненциален, если рассматривать лишь длину входа (равную $\Theta (\ln n)$). Более того, если определять сложность как функцию лишь от длины входа, то данная задача в принципе не имеет полиномиального решения, что выглядит довольно абсурдно ;)

Пример с задачей сортировки не так интересен, так как длина входа и длина выхода в ней равны - в этом случае можно забыть про длину выхода и говорить лишь о зависимости сложности от длины входа (я написал про подобные случае в статье). Maxal 21:18, 16 декабря 2008 (UTC)

«пропылесосить ковер»

"«пропылесосить ковер» требует время, линейно зависящее от его размера (O(S)), то есть на ковер, площадь которого больше в два раза, уйдет в два раза больше времени" - вспоминается армейский анекдот: прапорщик в наказание приказал рядовому вырыть яму 3х3х3 метра, рядовой: тов. прапорщик, можно я лучше вырою целых три ямы 1х1х1? - Хорошо, валяй,- ответил прапор, - это же одинаково.

Я к тому, что если ковер квадратный, то время, в лучшем случае, будет квадратично зависеть от стороны квадрата, в реальности же при реализации алгоритма, чем больше ковер, тем труднее его кантовать, кто чистил ковры, знает о дополнительных потерях времени.(Кстати, ковры, как известно, чистят с двух сторон). Дать же оценку для наихудшего случая, для ковра достаточно больших размеров, вообще затруднительно... Может, поискать менее спорный пример? ;-) --tim2 13:20, 19 декабря 2008 (UTC)

1. «время, в лучшем случае, будет квадратично зависеть от стороны квадрата» …только если вводом алгоритма является сторона квадратного ковра. В примере ведь совсем не это говорится, а, на мой взгляд, довольно однозначно: «на ковер, площадь которого больше в два раза, уйдет в два раза больше времени». Я уточнил: «требует время, линейно зависящее от его площади».
2. кантовать или чистить ковёр не входит в задачу. «Пропылесосить» — неужели это неоднозначно? Это всего лишь пример, идеальной корректности вы добьётесь только дав формальное определение задачи, но тут другой раздел.
3. в этом случае худший, средний и лучший случаи совпадают. --Peni 16:24, 19 декабря 2008 (UTC)

Формально Вы совершенно правы – я с этим и не спорил. Мое замечание касалось традиционного для примеров столкновения наглядности прототипа и абстракции мат. модели (абстрагирующейся от большинства свойств прототипа). Вспоминается известная шутка на эту тему, что математики решают задачи, которые решаются, а программисты - которые нужно решить. Это вопросы философии и методологии науки, связанные с темой статьи, но явно не связанные с контекстом, в котором приводится данный пример, и т.о. в этом месте статьи лишние. Поскольку выбор примера не критичен и на эту тему можно привести множество примеров, лучше заменить этот пример на другой, более удачный, не провоцирующий читателя на подобные вопросы. Типа – натуральный счет, т.е. время, затраченное на перечисление всех целых чисел в заданном интервале, будет линейно зависеть от величины этого интервала.--tim2 13:11, 22 декабря 2008 (UTC)

На мой взгляд, проблема несколько надуманная, примеров действительно много, и придраться можно к любому из них. Натуральный счёт менее наглядный, так как тут может возникнуть вопрос: а в чём, собственно, заключается «проблема» и при чём тут «алгоритмическое решение». Если хотите помочь развить статью, напишите лучше еще один пример экспоненциальной сложности (типа, отгадать пароль из двух цифр → увеличить кол-во цифр вдвое, и т. д.) --Peni 15:00, 22 декабря 2008 (UTC)

• Реальный (практически значимый) пример экспоненциальной сложности - Индекс Хосойи.
• в чём, собственно, заключается «проблема» Натуральный счёт: for i:=1 to 1000 do
• Да! при желании придраться можно к любому примеру, но ИМХО к "for i:=1 to 1000 do" придраться сложнее.--tim2 11:13, 24 декабря 2008 (UTC)
• PS. В отношеннии наглядности - спорно, на мой взгляд "for i:=1 to 1000 do" нагляднее, чем моделирование процесса чистки ковра.--tim2 11:23, 24 декабря 2008 (UTC)

Индекс Хосойи — слишком сложный, натуральный счёт — слишком простой. Мне кажется, что пример из реальной жизни — самое то. --Peni 17:40, 24 декабря 2008 (UTC)

Не понимаю: что сложного в полном числе паросочетаний? неужели понятие "паросочетание" сложнее материала данной статьи? Без определенного мат. базиса и культуры - эту статью все равно не понять. А что плохого в слишком простом примере? "пример из реальной жизни" - звучит слишком расплывчато с философской точки зрения: математические объекты - это реальность? Химические молекулы, для предсказания свойств которых используется индекс Хосойи, - это реальность? ;-) Более того, в реальной жизни зачастую можно наблюдать парадоксы - возьмем второй пример из статьи: очень многие люди затратят на поиск в телефонном справочнике гораздо больше усилий, что объясняется как плохим знанием алфавита, так и нечетким следованием алгоритму поиска. --tim2 12:26, 25 декабря 2008 (UTC)

Убрать цитату Зыкова из раздела Замечания

• цитата вставлена в текст в совершенно неподходящем месте.
• в цитате упоминается некая «полиномиальная идеология», о которой в тексте нет ни слова.
• если говорить о самой цитате, то там написано, что алгоритм «занимает время (число шагов) порядка n^C», в слове «порядка» как раз и заключены все константы. Например, пусть алгоритм выполняет ровно 2N² шагов, в этом случае мы можем сказать, что этот алгоритм выполняет порядка N² шагов (поправьте меня, если я ошибаюсь), в этом случае цитата вообще бессмысленна.
• тем не менее смысл цитаты понятен, но этот простой и очевидный факт, о том что асимптотическое сравнение имеет смысл лишь для больших размеров входа, уже описан в пункте 2 этого раздела и в дополнительной цитате не нуждается. MDA 15:07, 23 декабря 2008 (UTC)

Мне эта цитата совсем не нравится. Дескать, давайте возьмём «практичный» размер ввода N, дефакто непрактичную константу C=10^(10^10) и удивимся тому, что получится. А до тех пор будем сидеть и молча решать неравенство $N^{C}<N+{\frac {N!}{C}}$, а не заниматься риторикой.. --Peni 18:10, 23 декабря 2008 (UTC)

Вполне допускаю, что цитата может не нравиться, кому-то и теорема Пифагора может не нравиться :-), но это цитата из известной книги широко известного специалиста - более чем авторитетный источник. И именно что она перекликается с приведенными выше замечаниями (в том числе и с пунктом 2), однако замечания не имеют ссылки на источники, и таким образом цитата их дополняет и указывает на конкретное критическое отношение, высказанное авторитетным ученым. Насчет очевидности, с одной стороны, да, очевидно, с другой стороны, многие авторы слишком увлекаются полиномиальными алгоритмами в теории, когда же дело доходит до реализации, получается совсем не здорово. Безусловно, с этой цитатой, как и с любой другой, можно спорить, однако наверное не здесь, поскольку это будет оригинальным исследованием. На мой взгляд, цитата крайне интересна - поскольку в ней высказывается более негативное отношение к предмету статьи, чем у многих других авторов - и т.о. она нужна в энциклопедии для нейтральности точки зрения.--tim2 11:12, 24 декабря 2008 (UTC)

Именно в этом и проблема, что цитата куцая, и обо всём, о чём вы говорите, умалчивает, но зато приводит абсолютно искусственный пример. Гораздо полезнее было бы найти источник, в котором оценка сложности описывается с практической точки зрения, с реальными примерами конкретных задач, где полиномиальный алгоритм уступает неполиномиальному для какого-то входа. А для того, чтобы решить неравенство (см. выше), Зыков не нужен. --Peni 17:27, 24 декабря 2008 (UTC)

Согласен с Вами, что полезно "было бы найти источник ... где полиномиальный алгоритм уступает неполиномиальному", однако пока такой источник не найден, ИМХО, лучше будет Зыков, чем вообще никакого. (В замечаниях нет ни одного источника!) Но и Зыков высказался предельно ясно, что полиномиальный алгоритм может быть хуже неполиномиального - вполне законченная мысль, не куцая. И все, что я сказал, я сказал, опираясь на цитату, а предшествующие замечания статьи ее, на мой взгляд, вполне разъясняют - я же ведь не предлагаю их убрать и оставить только цитату. Пример же в цитате не искусственный, а очень жизненный - нередко можно встретить публикацию, озаглавленную "Эффективный полиномиальный алгоритм для...", где автор дает абстрактное описание оригинального (т.е. этим автором сочиненного) алгоритма и приводит доказательство, что он относится к классу Р. Точка. Никаких оценок констант, никаких попыток реализации. Такая вот "математически узаконенная" халтура. Автор сам себе не враг и в явном виде подобного неравенства приводить не будет.--tim2 12:24, 25 декабря 2008 (UTC)

Цитата негодная по нескольким причинам: во-первых, в ней не говорится о каком-либо конкретном алгоритме, следовательно никаких оснований верить в то что подобные алгоритмы существуют нет. Во-вторых, использование оборота "порядка n+n!/C" вызывает серьезные сомнения в математической грамотности автора.216.239.33.8 04:14, 26 декабря 2008 (UTC)

Цитата неуместна. Также весь раздел "Замечания" не имеет никакого отношения к теории сложности. Предложение "Будем надеяться ..." неуместно по форме. 216.239.33.8 04:08, 26 декабря 2008 (UTC)

216.239.33.8 написал: "вызывает серьезные сомнения в математической грамотности автора". Приехали! Зыков - один из наиболее известных российских специалистов по теории графов! И такое заявление - явный зашкал, заставляющий в свою очередь усомниться в мат.грамотности заявившего. Но так или иначе, цитата из авторитетного источника, ей же противопоставляется неопубликованное мнение анонимного автора предыдущего комментария, т.е. всего лишь его оригинальное "исследование".--tim2 09:13, 27 декабря 2008 (UTC)

дело в том, что говорить о порядке "(n + n!/C)" бессмысленно, поскольку O(n!) = O(n + n!). Это объясняют в первом курсе мат. анализа. Именно поэтому цитата вызывает сомнение в грамотности автора. И прошу заметить, что мое высказывание относится к цитате, а не к автору. Поэтому прошу оставить ваши заявления о величчи Зыкова в стороне. А цитату следует удалить.

Цитата явно выдернута из контекста, об этом говорит и некая «полиномиальная идеология», и неопределенное понятие «порядка». Совершенно очевидно, что в этом случае она не может быть использована как самостоятельное утверждение. Цитату необходимо убрать, а ссылку на источник оставить. MDA 15:07, 27 декабря 2008 (UTC)

Ничего подобного - цитата НЕ выдернута из контекста, здесь полный текст примечания к тексту Введения. Взяли бы книгу и проверили сначала (книга-то недавно издана центральным издательством и с нею просто ознакомиться), прежде чем обвинять на построенных Вами же догадках, уровня гадания на кофейной гуще. Нелепо и несолидно так вести обсуждение. И второе нелепое предложение: "Цитату необходимо убрать, а ссылку на источник оставить" - а какой смысл оставить только ссылку на источник, в котором автор только в очень немногих местах говорит на тему статьи? Книга-то о теории графов, а не о сложности вычислений.--tim2 15:52, 27 декабря 2008 (UTC)

PS. Вам кажется, что голословное утверждение о нарушении контекста - это универсальный метод отклонить любую непонравившуюся цитату. Но, как и любое утверждение, это утверждение надо доказывать - о математике все же говорим, а не об "альтернативных науках". Последнее время этот "универсальный метод" все чаще и чаще используется на страницах Вики и похоже, что поклонники этого метода даже не удосужились прочесть, что такое "контекст". В частности, в этой не очень полной статье сказано: "Потерять контекст в разговоре — это перестать понимать, на что опирается собеседник, или интерпретировать его в ином смысле, нежели то, что должно было следовать из подразумевавшегося контекста." И в каком же еще смысле можно интерпретировать данную цитату или что в ней непонятного? Данная цитата совершенно однозначно выражает законченную мысль Зыкова, что принадлежности к Р для алгоритма недосточно, чтобы быть эффективным. Разве не понятно? Какого еще контекста Вам недостает? Надеюсь, Вы бываете в научных библиотеках - возьмите книгу Зыкова и прочтите - там немного. И очень прошу, прежде чем высказывать догадки о первоисточнике, знакомьтесь сначала с этим источником, этим Вы сильно сэкономите время Вашим оппонентам. --tim2 15:52, 27 декабря 2008 (UTC)

PPS. Перефразируя великую фразу советского "критика": "я Пастернака не читал, но скажу" - могу предложить в контексте данного разговора "Зыкова не читал, но скажу".--tim2 15:52, 27 декабря 2008 (UTC)

Что-то вы разгорячились… но не будем об этом. Я действительно не читал эту книгу и даже не посмотрел место из которого взята цитата (не так-то легко найти эту книгу в свободном доступе: есть только издание 87 года). Но тем не менее я посчитал что цитата была вырвана из контекста. И сделал я это не беспричинно: повторюсь, во всем тексте статьи понятие «полиномиальная идеология» встречается только один раз — в этой цитате и нигде не расшифровывается, и второе, понятие «порядка» будучи неопределенным дает широкие возможности для критики цитаты (и эта критика уже приводилась). Теперь о галочках. С чего вы взяли, что цитирование «полного текста примечания к тексту Введения» гарантирует ненарушение контекста? Что касается «а какой смысл оставить только ссылку на источник, в котором автор только в очень немногих местах говорит на тему статьи?», то ответ такой же как и ответ на вопрос: «а какой смысл оставить ссылку на источник, в котором автор говорит на тему статьи?» MDA 17:09, 30 декабря 2008 (UTC)

"Что-то вы разгорячились…" -Нет. "С чего вы взяли, что цитирование «полного текста примечания к тексту Введения» гарантирует ненарушение контекста?" - А с чего Вы взяли, что цитирование «полного текста примечания к тексту Введения» НЕ гарантирует ненарушение контекста? --tim2 21:58, 2 января 2009 (UTC)

Хотя бы с того, что ваше цитирование «полного текста примечания к тексту Введения» является выдернутым из контекста. (Только не надо говорить, что это ни на чем не основанные догадки: все доводы приведены выше) --MDA 07:47, 3 января 2009 (UTC)

• Данная цитата является отдельной и самостоятельной законченной мыслью и, таким образом, является контекстно независимой. Следуя Вашей "логике", цитировать вообще нельзя, поскольку про всякую цитату можно заявить, что она вне контекста оригинала. Абсурд!

• Когда мы говорим, что напряжение батарейки имеет порядок нескольких вольт, а в розетке напряжение порядка 220В, обычно никто не цепляется к словам - каждый знает, что есть батарейки в полтора, а есть и в 9В, а амплитудное значение в розетке может быть и 200 и 250В - в зависимости от времени суток и электропотребления. Если, например, речь идет о технике безопасности, то сказать, что напряжение порядка 40В может быть опасным для жизни - достаточно. Есть любители определять годность батарейки языком - это не опасно, хотя и не гигиенично, проверять языком розетку явно не стоит :) Из этого примера видно, что слово порядок общеупотребимое, смысл его достачно очевиден и особого уточнения контекста обычно не требует.

• "Полиномиальная идеолигия" взято автором (Зыковым) в кавычки, это означает, что это не более чем образное сравнение (в литературном смысле), а не какой-то особый строгоопределяемый термин. Общеизвестный литературный прием. С тем же успехом пристрастие к полиномиальным алгоритмам я мог бы назвать "полиномофилией" - все бы поняли, что это фигура речи и не более того.

• Еще раз - я не "горячусь" - образная речь еще не означает возмущения, но при этом я не понимаю, зачем заниматься подобным буквоедством? Добро бы речь шла об определении какого-то важного понятия или о формулировке теоремы, а то ведь всего о мнении - ценном, интересном, авторитетном, но мнении. Так, например, Шопенгауэр высказывал мнение, что Гегель писал ерунду. Ни я, ни кто другой, кто сообщит об этом факте, не должен отстаивать это мнение - оно "на совести" Шопенгауэра, но тем, кто интересуется философией, оно будет интересно, поскольку это мнение не мое и не Ивана Иваныча, а Шопенгауэра. Точно так же мнение Зыкова "на совести" Зыкова, я могу его разделять, а могу и не разделять, но не должен его здесь отстаивать, приводя данную цитату.--tim2 10:30, 3 января 2009 (UTC)

• PS. "не так-то легко найти эту книгу в свободном доступе" - очень странно! Пару лет назад я спокойно купил эту книгу в магазине НТ книги на Лен. проспекте в Москве. А какими научными библиотеками Вы пользуетесь? Неужели они настолько плохо комплектуются? Есть ли у них возможность пользоваться межбиблиотечным обменом?--tim2 10:30, 3 января 2009 (UTC)

• PPS. Следуя Вашей логике, предполагаю, что в случае, если я процитирую известную фразу из советского словаря, что кибернетика - продажная девка империализма, Вы скажете, что вне контекста понятие "продажная девка" является неопределенным и "дает широкие возможности для критики цитаты"...--tim2 10:30, 3 января 2009 (UTC)

"слово порядок общеупотребимое, смысл его достачно очевиден и особого уточнения контекста обычно не требует", совершенно верно - обычно. В разговорной речи не требуется пояснение. Но беда в том, что разговорная речь не требует точного определения используемых понятий, достаточно лишь чтобы собеседники одинаковые понятия определяли почти одинаково. Здесь же нам предлагается математическая задача, у нас есть формулы и нам надо сравнить время работы алгоритмов, но вот беда - нету точных формул времени, есть только приближение, охарактеризованное словом "порядка". Это означает, что решение неравенства даст нам неточную характеристику, о которой мы ничего не можем сказать (в силу неопределенности слова "порядка"). В этом смысле это сравнение даже хуже асимптотического. Если бы это была не цитата - просто убрали это слово "порядка", но увы... надо убирать всю цитату. --MDA 10:23, 4 января 2009 (UTC)

Ваши примеры так же неуместны, и в случае с розеткой и в с случае с батарейкой существуют вполне конкретные нормы отклонения фактического значения напряжения от номинального. Именно эти нормы и скрываются под словом "порядка".--MDA 10:24, 4 января 2009 (UTC)

"я спокойно купил эту книгу в магазине НТ книги на Лен. проспекте в Москве", извините, но чтобы посмотреть 10ю страницу малонужной мне книги, в Москву не поеду. "А какими научными библиотеками Вы пользуетесь? Неужели они настолько плохо комплектуются". А кто такой этот Зыков? Кто он такой, чтобы по отсутствию новых изданий его работ можно было судить о качестве комплектации научных библиотек? --MDA 10:23, 4 января 2009 (UTC)

• "А кто такой этот Зыков?" - один из крупнейших специалистов в области теории графов, доктор физ-мат. наук, профессор, автор двух фундаментальных учебников по теории графов, один из них издан также на английском в США.
• Отсутствие свежеизданных фундаментальных учебников плохо свидетельствует о качестве комплектации научной библиотеки.
• "извините, но чтобы посмотреть 10ю страницу малонужной мне книги, в Москву не поеду" - извините, но разговор получается несолидным: не могу достать книгу - поэтому требую убрать цитату из нее. Как в школе: не выучил урок, потому что не было учебника!
• "в с случае с батарейкой существуют вполне конкретные нормы отклонения фактического значения напряжения от номинального" - в случае с батарейкой определенного типа, модели и даже определенного производителя - существует, а вот насчет нормы для всех вообще батареек - я о такой не слышал. Кроме того, Вы подменили термин: я говорил не об отклонении фактического значения напряжения от номинального, а об разбросе номинальных значений для батареек разных типов. Здесь и выше про "нету точных формул времени" Вы сами крайне неконкретно употребляете понятие "точный". Вот здесь уж действительно непонятно, в каком это смысле "это сравнение даже хуже асимптотического" и почему одно противопоставлено другому? Речь ведь не идет о замене асимптотической оценки какой-то другой, а всего лишь о дополнительной осторожности при использовании этой оценки и о недостаточности факта принадлежности к классу Р для гарантированной эффективности алгоритма.
• Посмотрите статью Порядок: "Порядок может использоваться при классификации объектов и часто определяется максимальным значением некоторой характеристики объекта: например, уравнения первого порядка, кривые второго порядка, многочлен порядка n и т.д." - не вижу разницы между выражением "многочлен порядка n" и из цитаты "время (число шагов) порядка n^C, а при другом — порядка n+n!/C".
• Итак, про "вырванность цитаты из контекста" Вы уже больше не говорите? Т.е. все Ваши несогласия теперь сводятся к несогласиям с мнением Зыкова: "Если бы это была не цитата - просто убрали это слово "порядка", но увы...", т.е. свое неопубликованное мнение (оригинальное исследование), Вы противопоставляете мнению из авторитетного источника. Имеете полное право, но не здесь. В Вики оригинальное исследование основанием не считается. И отстаивать правоту Зыкова я здесь не должен, для Вики достаточно, что мнение из авторитетного источника, а верно ли оно - решать редактора Вики не могут.--tim2 12:32, 5 января 2009 (UTC)
• PS. Чтобы поставить уж все возможные точки над i - еще одна цитата: "Символы O(g(n)) и Ω(g(n)) читаются соответственно: "порядка не более чем g(n)" и "порядка не менее чем g(n)". Если сложность какого-либо алгоритма есть O(g(n)), то мы говорим, что этот алгоритм "затрачивает порядка O(g(n)) времени"" (В.Липский, Комбинаторика для программистов, М.:Мир, 1988, С.14.)--tim2 13:24, 5 января 2009 (UTC)

Вы правы, эти неточности несущественны. --MDA 17:28, 5 января 2009 (UTC)

Статья Эффективность алгоритма

На данный момент уже существует переведенная статья Эффективность алгоритма. Бегло пробежавшись по обеим статьям, не понял, чем они отличаются Мышка сосиска (обс.) 06:38, 12 марта 2022 (UTC)