Понятие сложности алгоритма

Дисциплина «Алгоритмы и структуры данных» Лекция № 1 Понятие сложности алгоритма Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-3 «Управление и моделирование систем» Литература • Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2016 • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. – М.: «Вильямс», 2020 • Левитин А.В., Красиков И.В. Алгоритмы: введение в разработку и анализ.: Пер. с англ.– М.:Издательский дом «Вильямс», 2017. – 576. Сложность и эффективность алгоритма Алгоритм должен удовлетворять следующим противоречащим друг другу требованиям: • 1) • 2) Сложность и эффективность алгоритма Алгоритм должен удовлетворять следующим противоречащим друг другу требованиям: • быть простым для понимания, перевода в программный код и отладки; • эффективно использовать вычислительные ресурсы и выполняться по возможности быстро. Какие вычислительные ресурсы бывают? Сложность и эффективность алгоритма Алгоритм должен удовлетворять следующим противоречащим друг другу требованиям: • быть простым для понимания, перевода в программный код и отладки; • эффективно использовать вычислительные ресурсы и выполняться по возможности быстро. Сложность алгоритма – это величина, отражающая порядок величины требуемого ресурса (времени или дополнительной памяти) в зависимости от размерности задачи. Сложность и эффективность алгоритма Алгоритм должен удовлетворять следующим противоречащим друг другу требованиям: • быть простым для понимания, перевода в программный код и отладки; • эффективно использовать вычислительные ресурсы и выполняться по возможности быстро. Сложность алгоритма – это величина, отражающая порядок величины требуемого ресурса (времени или дополнительной памяти) в зависимости от размерности задачи. Будем различать временну’ю T(n) и пространственную (её также называют ёмкостной) V(n) сложности алгоритма. Временная сложность Необходимо различать термины «время выполнения алгоритма» и «время выполнения программы» т.к. время выполнения программы зависит от временной сложности алгоритма. Время выполнения программы есть время, затрачиваемое центральным процессором для решения задачи от момента запуска процесса до его останова и может быть измерено в физических единицах времени (секунды, миллисекунды, «тики» ЦП) Под временной сложностью алгоритма понимается "время" выполнения алгоритма, измеряемое в "шагах" (инструкциях алгоритма), которые необходимо выполнить алгоритму для достижения запланированного результата. Временная сложность Необходимо различать термины «время выполнения алгоритма» и «время выполнения программы» т.к. время выполнения программы зависит от временной сложности алгоритма. Время выполнения программы есть время, затрачиваемое центральным процессором для решения задачи от момента запуска процесса до его останова и может быть измерено в физических единицах времени (секунды, миллисекунды, «тики» ЦП) Под «временем выполнения алгоритма» или временной сложностью алгоритма понимается "время" выполнения алгоритма, измеряемое в "шагах" (инструкциях алгоритма), которые необходимо выполнить алгоритму для достижения запланированного результата. Формальная система выполнения алгоритма В качестве формальной системы выполнения алгоритма будем рассматривать абстрактную машину, включающую процессор с фон-Неймановской архитектурой, поддерживающий адресную память (ресурсы!) и набор «элементарных» операций соотнесенных с языком высокого уровня. Допущения: • каждая машинная команда выполняется не более чем за фиксированное время • рассматриваем правильные и финитные алгоритмы, т.е. алгоритмы, дающие единственное решение общей проблемы Формальная система выполнения алгоритма В силу сделанных допущений: • для любого начального набора данных алгоритм выполняет не более, чем конечное количество «элементарных» операций абстрактной машины. • под временной трудоемкостью Fd алгоритма для данного набора начальных данных d(n), будем понимать количество «элементарных» операций (время их выполнения), совершаемых алгоритмом для решения конкретной проблемы, в данной формальной системе. здесь d(n) – набор начальных (входных) данных, на котором будет выполняться алгоритм. Длина входных данных или размер? Поскольку время выполнения программы зависит от ввода исходных данных, его можно определить как функцию от исходных (входных) данных d(n). Но зачастую время выполнения программы зависит не от самих исходных данных, а от их "размера" (или объема). Для задачи сортировки массива из n элементов понятию «размера исходных данных» соответствует размер массива, т.е. количество элементов массива. Естественной мерой объема входной информации для программы сортировки будет число элементов, подлежащих сортировке, или, другими словами, длина входного списка или, в общем случае, длина входных данных d(n). Длина входных данных или размер? Поскольку время выполнения программы зависит от ввода исходных данных, его можно определить как функцию от исходных (входных) данных d(n). Но зачастую время выполнения программы зависит не от самих исходных данных, а от их "размера" (или объема). Поскольку конкретные переменные (параметры) от которых зависит время выполнения программы могут принимать различные значения, что в программировании нашло отражение в виде типа данных – т.е. размера области памяти, достаточной для хранения любого значения, которое может принимать переменная или структура (в нашем случае – входной список), а типу соответствует определенное значение «размера памяти», то обозначим через N – размер <памяти>, достаточный для хранения любого набора входных данных d(n). Тогда через F (N) будем обозначать время выполнения алгоритма как функцию по всем возможным входным данным размерности N. Чувствительность алгоритма к исходным данным Содержательно алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Чтобы учитывать этот факт, полностью сохраняя при этом возможность анализировать алгоритмы независимо от данных, различают: • максимальную сложность Tmax(N), или сложность наиболее неблагоприятного случая, когда алгоритм работает дольше всего; • среднюю сложность Tmid(N) – сложность алгоритма в среднем; • минимальную сложность Tmin(N) – сложность в наиболее благоприятном случае, когда алгоритм справляется быстрее всего. Чувствительность алгоритма к исходным данным Содержательно алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Чтобы учитывать этот факт, полностью сохраняя при этом возможность анализировать алгоритмы независимо от данных, различают: • максимальную сложность Tmax(N), или сложность наиболее неблагоприятного случая, когда алгоритм работает дольше всего; • среднюю сложность Tmid(N) – сложность алгоритма в среднем; • минимальную сложность Tmin(N) – сложность в наиболее благоприятном случае, когда алгоритм справляется быстрее всего. Соответственно, • 1. – худший случай – наибольшее количество операций, совершаемых алгоритмом А для решения конкретных задач размерностью N • 2. – лучший случай – наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N • 3. – средний случай – среднее количество операций, совершаемых алгоритмом А Определению этих значений будет посвящена практическое занятие № 2. Классификация алгоритмов по виду функции трудоемкости • Количественно-зависимые по трудоемкости алгоритмы – это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений: Fd (N)= f(n); T^ = Tv = Ť Пример: перемножение матриц • Параметрически-зависимые по трудоемкости алгоритмы Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти. Пример: вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов • Порядко-зависимые Fd (N) = f(d,n); Tv(d,n)  Ť(n)  T^(d,n) Пример: алгоритмы сортировок, поиска… Классификация алгоритмов по виду функции трудоемкости • Количественно-зависимые по трудоемкости алгоритмы – это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений: Fd (N)= f(n); T^ = Tv = Ť Пример: перемножение матриц • Параметрически-зависимые по трудоемкости алгоритмы Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти. Пример: вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов • Порядко-зависимые Fd (N) = f(d,n); Tv(d,n)  Ť(n)  T^(d,n) Пример: алгоритмы сортировок, поиска… Оценка сложности алгоритма Способы оценки (временной) сложности алгоритма 1) 2) Оценка сложности алгоритма Способы оценки (временной) сложности алгоритма 1) экспериментальный 2) теоретический Оценка сложности алгоритма Способы оценки (временной) сложности алгоритма 1) экспериментальный – выполнить полученную программу на нескольких задачах, оценивая (измеряя) время выполнения программ 2) теоретический Экспериментальный способ Самый простой способ оценки – экспериментальный, то есть запрограммировать алгоритм и выполнить полученную программу на нескольких задачах, оценивая время выполнения программ. Однако, этот способ имеет ряд недостатков: 1. Экспериментальное программирование – это, возможно, дорогостоящий процесс. 2. Необходимо учитывать, что на время выполнения программ влияют следующие факторы: • затраты на преобразование информации для последующей обработки на ЭВМ (в т.ч. «человеческий» фактор при вводе информации); • внешние задержки, вызванные работой операционной системы, например, при реализации механизма многозадачности или других программ, работающих в «фоновом» режиме (например, антивирусы); • качество скомпилированного кода исполняемой программы в силу различий в реализации отдельных операторов языка высокого уровня с учетом «оптимизации» компилятора под конкретный процессор; • машинные инструкции, используемые для выполнения программы, которые ориентированы на аппаратные особенности архитектуры ЭВМ, например, параллельную обработку линейной последовательности данных; • временная сложность алгоритма программы. Экспериментальный способ Самый простой способ оценки – экспериментальный, то есть запрограммировать алгоритм и выполнить полученную программу на нескольких задачах, оценивая время выполнения программ. Однако, этот способ имеет ряд недостатков: 1. Экспериментальное программирование – это, возможно, дорогостоящий процесс. 2. Необходимо учитывать, что на время выполнения программ влияют следующие факторы: • затраты на преобразование информации для последующей обработки на ЭВМ (в т.ч. «человеческий» фактор при вводе информации); • внешние задержки, вызванные работой операционной системы, например, при реализации механизма многозадачности или других программ, работающих в «фоновом» режиме (например, антивирусы); • качество скомпилированного кода исполняемой программы в силу различий в реализации отдельных операторов языка высокого уровня с учетом «оптимизации» компилятора под конкретный процессор; • машинные инструкции, используемые для выполнения программы, которые ориентированы на аппаратные особенности архитектуры ЭВМ, например, параллельную обработку линейной последовательности данных; • временная сложность алгоритма программы. Экспериментальный способ Самый простой способ оценки – экспериментальный, то есть запрограммировать алгоритм и выполнить полученную программу на нескольких задачах, оценивая время выполнения программ. Однако, этот способ имеет ряд недостатков: 1. Экспериментальное программирование – это, возможно, дорогостоящий процесс. 2. Необходимо учитывать, что на время выполнения программ влияют следующие факторы: • затраты на преобразование информации для последующей обработки на ЭВМ (в т.ч. «человеческий» фактор при вводе информации); • внешние задержки, вызванные работой операционной системы, например, при реализации механизма многозадачности или других программ, работающих в «фоновом» режиме (например, антивирусы); • качество скомпилированного кода исполняемой программы в силу различий в реализации отдельных операторов языка высокого уровня с учетом «оптимизации» компилятора под конкретный процессор; • машинные инструкции, используемые для выполнения программы, которые ориентированы на аппаратные особенности архитектуры ЭВМ, например, параллельную обработку линейной последовательности данных; • временная сложность алгоритма программы. Экспериментальный способ Самый простой способ оценки – экспериментальный, то есть запрограммировать алгоритм и выполнить полученную программу на нескольких задачах, оценивая время выполнения программ. Однако, этот способ имеет ряд недостатков: 1. Экспериментальное программирование – это, возможно, дорогостоящий процесс. 2. Необходимо учитывать, что на время выполнения программ влияют следующие факторы: • затраты на преобразование информации для последующей обработки на ЭВМ (в т.ч. «человеческий» фактор при вводе информации); • внешние задержки, вызванные работой операционной системы, например, при реализации механизма многозадачности или других программ, работающих в «фоновом» режиме (например, антивирусы); • качество скомпилированного кода исполняемой программы в силу различий в реализации отдельных операторов языка высокого уровня с учетом «оптимизации» компилятора под конкретный процессор; • машинные инструкции, используемые для выполнения программы, которые ориентированы на аппаратные особенности архитектуры ЭВМ, например, параллельную обработку линейной последовательности данных; • временная сложность алгоритма программы. Экспериментальный способ факторы: • внешние задержки, вызванные работой операционной системы, например, при реализации механизма многозадачности или других программ, работающих в «фоновом» режиме (например, антивирусы); • качество скомпилированного кода исполняемой программы в силу различий в реализации отдельных операторов языка высокого уровня с учетом «оптимизации» компилятора под конкретный процессор; • машинные инструкции, используемые для выполнения программы, которые ориентированы на аппаратные особенности архитектуры ЭВМ, например, параллельную обработку линейной последовательности данных; Наличие трех указанных факторов не позволяет применять типовые единицы измерения времени (секунды, миллисекунды и т.п.) в качестве временной сложности алгоритма, так как можно получить самые различные оценки для одного и того же алгоритма, если использовать труд разных программистов (которые реализуют алгоритм каждый по-своему), разные компиляторы, операционные системы и разные вычислительные машины. Оценка сложности алгоритма Способы оценки (временной) сложности алгоритма 1) экспериментальный выполнить полученную программу на нескольких задачах, оценивая (измеряя) время выполнения программ 2) теоретический основан на асимптотической оценке с использованием аппарата O-символики. Спасибо за внимание!