шпаргалка

Оценка сложности алгоритма

[ Назад ]

Основы оценок сложности алгоритмов

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

Нахождение точной зависимости для конкретной программы -- задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее примерного поведения при больших значениях параметра . Иногда для асимптотических оценок используют традиционное отношение (читается <<О большое>>) между двумя функциями , определение которого можно найти в любом учебнике по математическому анализу, хотя чаще применяют отношение эквивалентности (читается <<тэта большое>>). Его формальное определение есть, например, в книге [#!korman!#], хотя нам пока достаточно будет понимания данного вопроса в общих чертах.

В качестве первого примера вернемся к только что рассмотренным программам нахождения факториала числа. Легко видеть, что количество операций, которые должны быть выполнены для нахождения факториала числа в первом приближении прямо пропорционально этому числу, ибо количество повторений цикла (итераций) в данной программе равно . В подобной ситуации принято говорить, что программа (или алгоритм) имеет линейную сложность (сложность или ).

Можно ли вычислить факториал быстрее? Оказывается, да. Можно написать такую программу, которая будет давать правильный результат для тех же значений , для которых это делают все приведенные выше программы, не используя при этом ни итерации, ни рекурсии. Ее сложность будет , что фактически означает организацию вычислений по некоторой формуле без применения циклов и рекурсивных вызовов!

Не менее интересен и пример вычисления -го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна . Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи.



КАТЕГОРИИ:

Network | английский | архитектура эвм | астрономия | аудит | биология | вычислительная математика | география | Гражданское право | демография | дискретная математика | законодательство | история | квантовая физика | компиляторы | КСЕ - Концепция современного естествознания | культурология | линейная алгебра | литература | математическая статистика | математический анализ | Международный стандарт финансовой отчетности МСФО | менеджмент | метрология | механика | немецкий | неорганическая химия | ОБЖ | общая физика | операционные системы | оптимизация в сапр | органическая химия | педагогика | политология | правоведение | прочие дисциплины | психология (методы) | радиоэлектроника | религия | русский | сертификация | сопромат | социология | теория вероятностей | управление в технических системах | физкультура | философия | фотография | французский | школьная математика | экология | экономика | экономика (словарь) | язык Assembler | язык Basic, VB | язык Pascal | язык Си, Си++ |