компьютерное, сложность

[avva]

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

Однако практическое применение этих теоретических знаний опирается, по-моему, на определенные допущения, которые далеко не столь математически точны, как теоретические факты. Под "практическим применением" я имею в виду то, что мы, например, склонны предпочесть алгоритм O(n) эквивалентному алгоритму O(n²) - конечно, это простейший случай, и на практике все бывает намного сложнее, плюс есть вопрос затрат на память, а не только затрат времени, но суть ясна. Есть математические факты, и есть их интерпретации в виде предпочтения тех или иных алгоритмов, попыток улучшить, прагматичных советов и указаний, итд. итп.

Эти предпочтения, советы итд. опираются на некоторые неявные допущения. Допущения эти, во-первых, иногда неверны, а во-вторых, что более важно, нет (по-моему) удовлетворительного объяснения тому, что обычно они верны. Отсутствие такого объяснения - своего рода дыра в теоретическом фасаде анализа программ и алгоритмов.

Вот два примера.

Во-первых, мы обычно пользуемся оценками для худшего случая (worst-case complexity). Если разные значения входных данных приводят к разным затратам времени (или памяти) алгоритмом, мы выбираем худшие результаты (для данного фиксированного количества входных данных), и их используем для оценки функции затрат в общем случае. Однако худший случай и общий случай - весьма разные вещи. На практике может оказаться, что худший случай случается достаточно редко, а в типичном случае алгоритм ведет себя намного лучше, чем утверждает наша пессимистичная оценка.

Известный пример - алгоритм quicksort. Он выполняется в худшем случае за время O(n²), а в среднем или типичном случае - за O(nlogn). Есть алгоритмы сортировки, которые всегда выполняются за O(nlogn), и в худшем случае тоже, т.е. теоретически они как бы лучше, чем quicksort, но на практике часто оказывается, что quicksort реально быстрее.

Но интересно не то, что есть пример того, как теоретическая основа приводит к неверной интерпретации. Интересно то, что это происходит так редко! Quicksort - известное исключение, но таких исключений мало; обычно сложность худшего случая хорошо отражает "практическую" пользу от алгоритма. Почему? Это не обязано априори быть так. Априори я не вижу причин, почему в огромном количестве самых обычных алгоритмов не может быть небольшого количества очень плохих случаев, как в quicksort, которые бы "искажали статистику". Но на практике это обычно не так, и мы пользуемся этим в качестве неявного допущения. Есть ли объяснение этому?

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

Второй пример - само понятие асимптотической сложности. Не вполне ясно, почему оно вообще имеет какое-то отношение к окружающей нас действительно, где, грубо говоря, размеры всех входных данных и результатов ограничены на практике какой-то константой, скажем, 10³⁵. Математика говорит нам, что асимптотическая оценка, вообще говоря, ничего не значит в случае "небольших" значений, где "небольшое" значит "меньшее сколь угодно большой заранее зафиксированной постоянной". Асимптотика проявляется только в стремлении к бесконечности. Почему она оказывается полезной в реальном мире?

Можно сформулировать этот вопрос более конкретно. Скажем, есть два алгоритма, один O(2ⁿ), экспоненциальный, другой O(n), линейный. Мы "знаем", что первый намного намного хуже второго. Но конечно же может быть так, что при первом стоит очень очень очень малый множитель, а при втором - очень очень очень большой, так что на практике, для всех размеров данных, которыми мы можем оперировать в реальном мире, первый будет намного намного лучше второго.

Но этого не происходит, за редкими исключениями. Почему? Есть ли у нас удовлетворительный ответ на этот вопрос?

Comments

[akusasik.livejournal.com]

Так есть нормальные теоретичекие подходы к этому. Вместо "worst case complexity", если алгоритм бегает н раз нужно считать "amortized complexity". Expeted runtime of quicksort быстрее expected runtime of determenistic sorting algorithms that run in nlogn.

Совершенно формальные способы обосновывать и то, и другое.

Только этими вещами программисты не пользуются, потому что там математика чуть-чуть бывает нетривиальная.

[ygam.livejournal.com]

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

[roza.livejournal.com]

Шёпотом: а таги кто ставить будет?

[andreev.livejournal.com]

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

[prosto-tak.livejournal.com]

Именно так объяснял это дело Леонид Левин на курсе алгоритмов. Он говорил, что нужно считать, что входные данные подсовывают враги, и именно исходя из этого анализировать алгоритмы. Что иногда не так уж далеко от истины, например, если мы имеем дело с Denial of Service attacks.

[vinopivets.livejournal.com]

+1. Оценка по наихудшему - историческое явление. Есть нормальные оценки и для средних времен, и для времен вычислений в условиях ограниченной памяти, но программисты туда, видимо, теперь не ходят - математически много сложнее.

[waxtep.livejournal.com]

По-первому мне кажется зависит от приложения - если алгоритм используется регулярно и должен гарантированно давать результат "не позднее, чем к ланчу", то именно оценка по худшему случаю важна. Он рано или поздно приключится, и ланч остынет. А если приложение не такое, то у человека, возможно, неприятие риска повышенное, диагноз по переписке готов ! :-)

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

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

[michk.livejournal.com]

Оценка по худшему случаю - очевидно, из желания гарантировать результат (т.е. время).
По поводу квадратичного алгоритма с малым фактором и линейного с большим - довольно нелегко представить себе 2 таких алгоритма, делающих одно и то же, с фактором, скажем, 1000, не говоря уже о 1000000. Соответственно, в задачах, где размер исходных не сильно ограничен, квадратичный будет хуже.

[waxtep.livejournal.com]

>>Здоровенных бессмысленных

Здоровенных осмысленных конечно, запуталсо окончательно.

[sillykong.livejournal.com]

Выбор наихудшей оценки на практике вполне объясним на интуитивном уровне.
Забиваясь на худший враиант, мы обеспечиваем некий гарантированный "запас прочности". Т.е. наш алгоритм точно будет работать не медленнее некоей определённой величины и в этом мы можем быть уверены на 100%. А если мы в критичном куске кода забьёмся на статистику, говорящую о том, что "с вероятностью 99% на практике всё работает быстро, но есть 1% случаев, когда будет медленно", мы лишаем себя запаса прочности. Т.е. если в случае понижения производительности у нас возникает исключительная ситуация, то мы обязаны забиваться на худший расклад. Это является следствием стремления человека делать всё с запасом.
Шоб ничё, если чё.
Это если говорить о бытовом уровне понимания.
Т.е. это простейшая логика, которая объясняет такую традицию в оценке.
Или Вы не об этом?

[eterevsky.livejournal.com]

Поставленные вопросы таки рассматриваются в теории сложности.

Во-первых, что касается QuickSort, обычно используется его вариант, когда разбиение ведётся по случайному элементу. Это -- вероятностный алгоритм, имеющий сложность именно O(n log n). Далее, есть вариант QuickSort'а, который будет работать за O(n log n) в худшем случае. Но им никто не пользуется, так как он становится куда медленнее любого вменяемого алгоритма.

Во-вторых, рассмотрим, например, алгоритмы умножения длинных чисел. Умножение «столбиком» работает за O(n²), но именно его стоит использовать в случае относительно небольших чисел. Немного более сложный алгоритм работает за время, если я не ошибаюсь, O(n^(log 4/log 3)). Наконец, наилучший известный на сей день алгоритм, основанный на дискретном преобразовании Фурье, работает за O(n log(n) log(log(n))). Но им пользуются только когда приходится осуществлять вычислений с совсем длинными числами, скажем от сотни тысяч знаков, а такая надобность всё-таки встречается нечасто. :)

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

[dmpogo.livejournal.com]

Ne znaju, w nauchnyh prilozhenijah dovol'no chasta situacija kogda kak raz prefaktory wazhny, i asimptoticheskoe powedenie mozhet ne dostigat'sja w real'nyh zadachah.

[al-zatv.livejournal.com]

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

[syarzhuk.livejournal.com]

что при первом стоит очень очень очень малый фактор
Наверное, всё-таки множитель.

[nevsky.livejournal.com]

В прошлом году, например, был наконец найден детерменированный полиномиальный (от длины числа) алгоритм для проверки его на простоту.
Ссылку не дадите?

[al-zatv.livejournal.com]

O(2^n) хуже (в большинстве случаев) независимо от фактора. Почему? Потому что при росте n неприлично растёт. Поэтому, вот что мы имеем при анализе применения алгоритма.

Пусть есть два алгоритма - A1 с O(n), и A2 с O(n^2), работающий на БД.

1)Пусть в БД 100 записей. Пусть A1 работает 10 секунд, А2 - 2 секунды. Вроде бы, лучше А2.
(условно, у первого t=n*0.1, у второго 2*(n/100)^2
2)В БД стало 200 записей. A1 работает 20 секунд, А2 - 8 секунд. Вроде бы, лучше А2.
3)В БД стало 300 записей. A1 работает 30 секунд, А2 - 18 секунд. Вроде бы, лучше А2.
4)В БД стало 10 000 записей. A1 работает 1000 секунд, А2 - 20 000 секунд. Вроде бы, лучше А2.
4)В БД стало 100 000 записей. A1 работает 10000 секунд, А2 - 2 миллиона секунд. Вроде бы, лучше
А2.

И это ведь не зависит от фактора. А уж если брать не n^2 а 2^n, то можно быть уверенным: чуть станет больше данных, как он "свалится". Так что в данном случае теория очень практична:)

[archernikov.livejournal.com]

"В прошлом году, например, был наконец найден детерменированный полиномиальный (от длины числа) алгоритм для проверки его на простоту."
В прошлом году?!

[eterevsky.livejournal.com]

Упс. Ошибся. В 2002-м.

[ygam.livejournal.com]

Prime numbers, for those of us mathematically challenged, are those that are divisible only by itself or by one. Although it sounds simple enough, it's quite a task to determine what mathematicians call the "primality" of a number. For instance, is 4958372640287988786544 a prime number?

[eterevsky.livejournal.com]

С ходу не нашёл. Наверное, стоит посмотреть тут (http://www.google.ru/search?hl=en&q=deterministic+primality+test&btnG=Google+Search).
В вики (http://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests) написано буквально в двух словах. Насколько я понимаю, метод получен путём запуска какого-то из стандартных вероятностных тестов (вероятно, Соловэя-Штрассена) на полиномиальном количестве вариантов входных данных. Соответсвующее множество входов получается путём достаточно нетривиальных трюков.

[eterevsky.livejournal.com]

Да, феерический ляп. :)

[archernikov.livejournal.com]

Первая гугл-ссылка на "primes in P" или "AKS", например.

[sply.livejournal.com]

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

А вот вполне обычный пример http://en.wikipedia.org/wiki/String_search , правда, без памяти.

[netch]

Если посмотреть что Кнут пишет про обменную сортировку Хоара, сиречь quicksort, видно, что для последовательностей короче 20 элементов он применяет не её, а вполне себе квадратичный метод вставок. Понятно, что конкретное число 20 - специфика его MIX-1009, но пример показателен.

И сложность действительно можно мерять по-разному. Например, как матожидание от сложности для каждого конкретного случая, и тогда для quicksort получится всё то же O(n log n). Но с худшим случаем тут получилась особая история: он слишком вероятный и показательный - и, что ещё более важно, недетектируемый за меньшие затраты чем сам алгоритм. Поэтому - спецмеры. А если бы детектирование того, что пошли куда-то не туда, занимало бы время значительно меньшее чем сама сортировка - был бы применён какой-то другой метод. Хотя это и так, похоже, возможно: если при разделении подотрезка получились слишком неравные длины - сменить медианное значение или применить другой метод разделения (например, ван Эмдена).

[vasja-iz-aa.livejournal.com]

Вы забыли упомянуть плату памятью за скорость.