Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

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

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

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

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

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

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

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 82 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →