Решение рекуррентных соотношений

Методы анализа алгоритмов
План:
1. Эффективность алгоритмов
2. Анализ рекурсивных программ
3. Решение рекуррентных соотношений


Ключевые слова: Деревья двоичного поиска, рекурсия, рекуррентные соотношениалгоритм, типы данных, абстрактный тип данных, программа, указатель, стек.
Эффективность алгоритмов. Один из способов определения временной эффективности алгоритма заключается в следующем: на основе данного алгоритма надо написать программу и измерить время ее выполнения на определенном компьютере для выбранного множества входных данных. Хотя такой способ популярен и, безусловно, полезен, он порождает определенные проблемы. Определяемое здесь время выполнения зависит не только от используемого алгоритма, но также от архитектуры и набора внутренних инструкций данного компьютера, от качества компилятора, да и от уровня программиста, реализовавшего тестируемый алгоритм. Время выполнения также может существенно зависеть от выбранного множества тестовых входных данных. Эта зависимость становится совершенно очевидной при реализации одного и того же алгоритма с использованием различных компьютеров, различных компиляторов, при привлечении программистов разного уровня и при использовании различных тестовых входных данных. Чтобы повысить объективность оценок алгоритмов, ученые, работающие в области компьютерных наук, приняли асимптотическую временную сложность как основную меру эффективности выполнения алгоритма. Термин эффективность является синонимом этой меры и относится в основном к времени выполнения в самом худшем случае (в отличие от среднего времени выполнения).
Напомним читателю определения О(f(n)) и Ω(f(n)), данные в главе 1. Говорят, что алгоритм имеет эффективность (т.е. временную сложность в самом худшем случае) О(f(n)), или просто f(n), если функция от n, равная максимуму числу шагов, выполняемых алгоритмом, имеет порядок роста О(f(n)), причем максимум берется по всем входным данным длины n. Можно сказать по-другому: существует константа с, такая, что для достаточно больших га величина сf(n) является верхней границей количества шагов, выполняемых алгоритмом для любых входных данных длины n.
Существует еще "подтекст" в утверждении, что "эффективность данного алгоритма есть f(n)’: время выполнения алгоритма также равно Ω(f(n)), т.е. f(n) является функцией от га с наименьшей степенью роста, которая ограничивает сверху время выполнения алгоритма в самом худшем случае. Но последнее условие (о наименьшей степени роста) не является частью определения О(f(n)), часто вообще невозможно сделать никакого заключения о наименьшей степени роста верхней границы.
Наше определение эффективности алгоритма игнорирует константы пропорциональности, которые участвуют в определениях О(f(n)) и Ω(f(n)), и для этого есть весомые причины. Во-первых, поскольку большинство алгоритмов записываются на языках программирования высокого уровня, нам приходится описывать их в терминах "шагов", каждый из которых должен выполняться за конечное фиксированное время после трансляции их в машинный язык какого-нибудь компьютера. Однако, как можно точно определить время выполнения какого-либо шага алгоритма, когда оно зависит не только от "природы" самого этого шага, но также от процесса трансляции и машинных инструкций, заложенных в компьютере? Поэтому вместо точной оценки эффективности алгоритма, пригодной только для конкретной машины (и для получения которой надо еще пробраться через запутанные подробности машинных вычислений), используют менее точные (с точностью до константы пропорциональности), но более общие оценки эффективности в терминах О(f(n)).
Вторая причина, по которой используются асимптотические оценки и игнорируются константы пропорциональности, заключается в том, что асимптотическая временная сложность алгоритма в большей степени, чем эти константы, определяет граничный размер входных данных, которые можно обрабатывать посредством данного алгоритма. В главе 1 эта ситуация исследована подробно. С другой стороны, читатель должен быть готовым к тому, что при анализе некоторых важных задач (например, сортировки) мы, возможно, будем применять такие утверждения, как "алгоритм А на типовом компьютере выполняется в два раза быстрее, чем алгоритм В".
Возможны ситуации, когда мы будем отходить от времени выполнения в самом худшем случае как меры эффективности алгоритма. В частности, если известно ожидаемое распределение входных данных, на которых выполняется алгоритм, то в этой ситуации среднестатистическое время выполнения алгоритма является более
разумной мерой эффективности по сравнению с оценкой времени выполнения в самом худшем случае. Например, в предыдущей главе мы анализировали среднее время выполнения алгоритма быстрой сортировки в предположении, что все первоначальные упорядочения входных последовательностей равновероятны.