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

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

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

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

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

Во-первых, мы обычно пользуемся оценками для худшего случая (worst-case complexity). ( Read more... )