Сложность и анализ алгоритмов
Анализ алгоритмов количественно определяет, как время выполнения и объем памяти алгоритма растут с увеличением размера входных данных, предоставляя асимптотический аппарат и инструменты, используемые для сравнения алгоритмов и выявления изначально сложных задач.
Definition
Анализ алгоритмов — это исследование вычислительных ресурсов (главным образом времени и пространства), которые алгоритм потребляет как функция от размера входных данных, а также методов, используемых для вывода, выражения и сравнения этих границ ресурсов.
Scope
Эта область охватывает измерение и сравнение использования алгоритмических ресурсов: асимптотическую нотацию (большое О, большая Омега, большая Тета), решение рекуррентных соотношений, возникающих из рекурсивных алгоритмов, амортизированный анализ последовательностей операций, а также основы классов вычислительной сложности и NP-полноты в их применении к проектированию алгоритмов. Она рассматривает наихудший, средний и амортизированный случаи затрат, а также различие между разрешимыми и неразрешимыми задачами. Более широкая теория вычислений (вычислимость, формальные классы сложности) относится к отдельной подобласти; здесь основное внимание уделяется анализу конкретных алгоритмов.
Sub-topics
Core questions
- Как выражается использование ресурсов алгоритма независимо от машины и деталей реализации?
- Что показывают анализ наихудшего, среднего и амортизированного случаев?
- Как решаются рекуррентные соотношения, возникающие в рекурсивных алгоритмах, для определения асимптотических границ?
- Как можно установить нижние границы, показывающие, что ни один алгоритм не может быть лучше?
- Что означает NP-полнота задачи и почему это важно для проектирования?
Key concepts
- большое О, большая Омега, большая Тета
- анализ наихудшего и среднего случаев
- рекуррентные соотношения
- основная теорема (master theorem)
- амортизированный анализ
- нижние границы
- полиномиальное время
- NP-полнота
Key theories
- Асимптотическая нотация
- Большое О, большая Омега и большая Тета описывают скорость роста использования ресурсов по мере увеличения размера входных данных, абстрагируясь от констант и членов низшего порядка, чтобы обеспечить машинонезависимое сравнение алгоритмов.
- Разрешимость и NP-полнота
- Задачи, разрешимые за полиномиальное время, считаются разрешимыми; NP-полные задачи — это те, к которым сводятся все задачи из класса NP, и нахождение полиномиального алгоритма для любой из них решило бы все, что является открытым вопросом (P против NP).
Clinical relevance
Анализ алгоритмов лежит в основе каждого инженерного решения о том, какой алгоритм или структура данных использовать, предсказывая, как системы будут масштабироваться по мере роста данных. Признание того, что проблема является NP-трудной, указывает специалистам на необходимость поиска приближенных, эвристических или частных методов вместо точного полиномиального алгоритма, что формирует работу в области оптимизации, планирования и крупномасштабных вычислений.
History
Асимптотическая нотация была заимствована в информатику из аналитической теории чисел и популяризирована Дональдом Кнутом в 1960-х и 1970-х годах. Теория NP-полноты была основана Стивеном Куком (1971) и расширена Ричардом Карпом (1972), что изменило подход к проектированию алгоритмов, сосредоточив внимание на границе между разрешимыми и неразрешимыми задачами.
Debates
- P против NP
- Является ли каждая задача, решения которой можно быстро проверить, также быстро разрешимой (P = NP), — это центральный открытый вопрос теоретической информатики; широко предполагается, что P не равно NP, но доказательства не существует.
Key figures
- Donald Knuth
- Stephen Cook
- Richard Karp
- Robert Tarjan
Related topics
Seminal works
- cormen2009
- knuth1976bigo
- kleinberg2006
Frequently asked questions
- В чем разница между анализом наихудшего и среднего случаев?
- Анализ наихудшего случая ограничивает использование ресурсов при наиболее неблагоприятных входных данных каждого размера, предоставляя гарантию. Анализ среднего случая оценивает ожидаемое использование ресурсов по распределению входных данных, что может быть более репрезентативным для типичной производительности, но зависит от предположений о распределении входных данных.
- Если задача является NP-полной, безнадежно ли ее решать?
- Нет. NP-полнота означает, что для наихудшего случая неизвестен эффективный алгоритм, но экземпляры часто могут быть решены с помощью аппроксимационных алгоритмов, эвристик, экспоненциальных алгоритмов, которые достаточно быстры на практике, или путем использования специальной структуры. Это сигнализирует об изменении стратегии, а не о невозможности.