2.5 Резюме¶
1. Ключевые выводы¶
Оценка эффективности алгоритмов
- Временная и пространственная эффективность являются двумя основными критериями для оценки качества алгоритмов.
- Эффективность алгоритмов можно оценивать с помощью практических тестов, однако это сложно из-за влияния тестовой среды и значительных затрат вычислительных ресурсов.
- Анализ сложности позволяет устранить недостатки практических тестов, а результаты анализа применимы ко всем платформам и могут выявить эффективность алгоритма при различных объемах данных.
Временная сложность
- Временная сложность используется для оценки тенденции изменения времени выполнения алгоритма с увеличением объема данных, что позволяет оценивать его эффективность. Однако в некоторых случаях она может работать не так хорошо, например когда объем входных данных мал или временная сложность одинакова, что не позволяет точно сравнить эффективность алгоритмов.
- Худшая временная сложность обозначается символом Big \(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)\).
2. Q & A¶
Q: Является ли пространственная сложность хвостовой рекурсии равной \(O(1)\)?
Теоретически пространственную сложность хвостово-рекурсивных функций можно оптимизировать до \(O(1)\) . Однако большинство языков программирования (например Java, Python, C++, Go, C# и другие) не поддерживают автоматическую оптимизацию хвостовой рекурсии, поэтому на практике пространственная сложность обычно считается равной \(O(n)\) .
Q: В чем разница между терминами function и method?
Функция (function) может выполняться независимо, и все ее параметры передаются явно. Метод (method) связан с объектом, неявно получает объект, который его вызывает, и может работать с данными, содержащимися в экземпляре класса.
Ниже это проиллюстрировано на примере нескольких распространенных языков программирования.
- C - процедурный язык программирования без объектно-ориентированной модели, поэтому в нем есть только функции. Однако мы можем имитировать объектно-ориентированное программирование через структуры (
struct), и функции, связанные со структурами, эквивалентны методам в других языках. - Java и C# - объектно-ориентированные языки программирования, в которых блоки кода (методы) обычно являются частью класса. Статические методы по поведению похожи на функции, потому что они привязаны к классу и не могут обращаться к конкретным переменным экземпляра.
- C++ и Python поддерживают как процедурное программирование (функции), так и объектно-ориентированное программирование (методы).
Q: Отражает ли диаграмма «распространенных типов пространственной сложности» абсолютный размер занятой памяти?
Нет, эта диаграмма показывает пространственную сложность, а значит отражает именно тенденцию роста, а не абсолютный объем занятого пространства.
Если взять \(n = 8\) , можно заметить, что значения на кривых не совпадают напрямую с соответствующими функциями. Это связано с тем, что каждая кривая содержит константный член, который сжимает диапазон значений до визуально удобного масштаба.
На практике, поскольку мы обычно не знаем, какова «константная» сложность каждого метода, только по сложности мы, как правило, не можем выбрать оптимальное решение для случая \(n = 8\) . Но для \(n = 8^5\) выбор уже очевиден: в этой области доминирует именно тенденция роста.
Q: Бывают ли случаи, когда в реальных сценариях алгоритм специально проектируют так, чтобы жертвовать временем ради пространства или пространством ради времени?
На практике в большинстве случаев выбирают обмен пространства на время. Например, для индексов в базах данных обычно строят B+ деревья или хеш-индексы, расходуя значительный объем памяти ради эффективных запросов уровня \(O(\log n)\) или даже \(O(1)\).
В сценариях, где память особенно дорога, наоборот, могут жертвовать временем ради пространства. Например, в embedded-разработке память устройства очень ограничена, поэтому инженеры могут отказаться от хеш-таблиц и выбрать последовательный поиск по массиву, экономя память ценой более медленного поиска.