hello-algo/ru/docs/chapter_computational_complexity/summary.md

Резюме

Ключевые моменты

Оценка эффективности алгоритмов

• Временная эффективность и пространственная эффективность являются двумя основными критериями оценки качества алгоритма.
• Мы можем оценивать эффективность алгоритмов с помощью практического тестирования, но сложно исключить влияние тестовой среды, и это требует значительных вычислительных ресурсов.
• Анализ сложности позволяет преодолеть недостатки практического тестирования, результаты анализа применимы ко всем платформам выполнения и могут продемонстрировать эффективность алгоритма при различных объемах данных.

Временная сложность

• Временная сложность используется для измерения тенденции роста времени выполнения алгоритма по мере увеличения объема данных, может эффективно оценивать эффективность алгоритма, но в некоторых случаях может быть неприменима, например, при небольшом объеме входных данных или при одинаковой временной сложности невозможно точно сравнить эффективность алгоритмов.
• Наихудшая временная сложность обозначается символом большого O, соответствует асимптотической верхней границе функции, отражает порядок роста количества операций T(n) при стремлении n к положительной бесконечности.
• Вычисление временной сложности состоит из двух этапов: сначала подсчитывается количество операций, затем определяется асимптотическая верхняя граница.
• Распространенные временные сложности в порядке возрастания: O(1), O(\log n), O(n), O(n \log n), O(n^2), O(2^n) и O(n!) и т. д.
• Временная сложность некоторых алгоритмов не является фиксированной, а зависит от распределения входных данных. Временная сложность делится на наихудшую, наилучшую и среднюю временную сложность, наилучшая временная сложность почти не используется, так как входные данные обычно должны удовлетворять строгим условиям для достижения наилучшего случая.
• Средняя временная сложность отражает эффективность работы алгоритма при случайных входных данных, наиболее близка к производительности алгоритма в реальных приложениях. Вычисление средней временной сложности требует статистики распределения входных данных и расчета математического ожидания.

Пространственная сложность

• Пространственная сложность действует аналогично временной сложности, используется для измерения тенденции роста объема памяти, занимаемой алгоритмом, по мере увеличения объема данных.
• Связанное с выполнением алгоритма пространство памяти можно разделить на входное пространство, временное пространство и выходное пространство. Обычно входное пространство не учитывается при расчете пространственной сложности. Временное пространство можно разделить на временные данные, пространство стекового кадра и пространство инструкций, при этом пространство стекового кадра обычно влияет на пространственную сложность только в рекурсивных функциях.
• Обычно мы обращаем внимание только на наихудшую пространственную сложность, то есть оцениваем пространственную сложность алгоритма при наихудших входных данных и в наихудший момент выполнения.
• Распространенные пространственные сложности в порядке возрастания: O(1), O(\log n), O(n), O(n^2) и O(2^n) и т. д.

Вопросы и ответы

В: Является ли пространственная сложность хвостовой рекурсии O(1)?

Теоретически пространственная сложность хвостовой рекурсивной функции может быть оптимизирована до O(1). Однако большинство языков программирования (например, Java, Python, C++, Go, C# и т. д.) не поддерживают автоматическую оптимизацию хвостовой рекурсии, поэтому обычно считается, что пространственная сложность составляет O(n).

В: В чем разница между терминами функция и метод?

Функция (function) может выполняться независимо, все параметры передаются явно. Метод (method) связан с объектом, неявно передается вызывающему его объекту, может работать с данными, содержащимися в экземпляре класса.

Рассмотрим на примере нескольких распространенных языков программирования.

• C является процедурным языком программирования, не имеет концепции объектно-ориентированного программирования, поэтому имеет только функции. Но мы можем имитировать объектно-ориентированное программирование, создавая структуры (struct), и функции, связанные со структурой, эквивалентны методам в других языках программирования.
• Java и C# являются объектно-ориентированными языками программирования, блоки кода (методы) обычно являются частью какого-либо класса. Статические методы ведут себя как функции, поскольку они привязаны к классу и не могут обращаться к конкретным переменным экземпляра.
• C++ и Python поддерживают как процедурное программирование (функции), так и объектно-ориентированное программирование (методы).

В: Отражает ли иллюстрация "Распространенные типы пространственной сложности" абсолютный размер занимаемого пространства?

Нет, эта иллюстрация показывает пространственную сложность, которая отражает тенденцию роста, а не абсолютный размер занимаемого пространства.

Предположим, что n = 8, вы можете заметить, что значение каждой кривой не соответствует функции. Это связано с тем, что каждая кривая содержит константный член, используемый для сжатия диапазона значений до визуально комфортного диапазона.

На практике, поскольку мы обычно не знаем, какова "константная" сложность каждого метода, обычно невозможно выбрать оптимальное решение только на основе сложности для n = 8. Но для n = 8^5 выбор очевиден, так как тенденция роста уже доминирует.

В: Существуют ли случаи, когда в зависимости от реального сценария использования выбирают жертвовать временем (или пространством) при разработке алгоритма?

В реальных приложениях в большинстве случаев выбирают жертвовать пространством ради времени. Например, индексы баз данных, мы обычно выбираем построение B+ дерева или хеш-индекса, занимая большой объем памяти, чтобы получить высокоэффективный поиск O(\log n) или даже O(1).

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