Для оценки эффективности алгоритма наиболее важными показателями являются:
Время выполнения алгоритма,
- требуемый объем оперативной памяти.
В наши дни, в силу полувека технического прогресса, первый показатель (время выполнения) зачастую значительно важнее, чем второй, поэтому далее подробно остановимся только на нем.
Упрощения для оценки времени выполнения алгоритмов
В работах Д.Кнута был предложен следующий подход для анализа времени выполнения алгоритмов: общее время складывается из величин стоимость * частота для каждой базовой операции. В число базовых операций могут входить сложение, умножение, деление, получение элемента по индексу из массива, сравнение целых чисел и т.д. Нетрудно заметить, что в этом случае вычисление оценки времени выполнения алгоритма довольно-таки утомительно. Поэтому А.Тьюринг сказал, что удобно пользоваться даже грубыми приближениями оценок времени выполнения алгоритмов: можно присвоить веса различным операциям в зависимости от их частоты появления во время работы алгоритма и учитывать только те операции, которым соответствуют наибольшие веса. Например, при перемножении матриц следует учитывать только такие операции, как умножение и запись чисел, т.к. это самые частые операции. Рассмотрение только наиболее часто встречающихся операций - первое упрощение , предложенное для приблизительного расчета времени выполнения алгоритмов.
Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число N характеризует размер входных данных),
\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),
вместо \(1/6N^3\) пишут "этот алгоритм имеет сложность \(O(N^3)\), вместо \(3N^4\) пишут "этот алгоритм имеет сложность \(O(N^4)\)".
Определение O-большого
Говорят, что \(f\) является "O большим" от \(g\) при \(x \to x_0\), если существует такая константа \(C>0\), что для всех \(x\) из окрестности точки \(x_0\) имеет место неравенство \(|f(x)| \leq C|g(x)|\). Ниже приведена иллюстрация определения (ось \(x\) - размер входных данных, ось \(y\) - время выполнения алгоритма). Мы видим, что начиная с некоторой точки при стремлении размера входных данных к \(\propto\) \(f(n)\) растет медленнее, чем \(g(n)\) и вообще \(g(n)\) как бы ограничивает ее сверху.
Примеры. \(1 = O(N), N = O(N^2).\)
Наряду с оценками вида \(O(N)\) используется оценка \(\Omega(N)\) (омега большое). Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция \(f(N)=\Omega(N^2)\). Это значит, что даже в самом удачном случае будет произведено не менее \(N^2\) действий. В то время как оценка \(O(N^3)\) гарантирует, что в худшем случае будет не более чем порядка \(N^3\) действий. Также используется оценка \(\Theta(N)\) (тэта), которая является верхней и нижней асимптотической оценкой, когда \(O(N)\) и \(\Omega(N)\) совпадают. Итак, \(O(N)\) - приближенная оценка алгоритма на худших входных данных, \(\Omega(N)\) - на лучших входных данных, \(\Theta(N)\) - сокращенная запись одинаковых \(O(N)\) и \(\Omega(N)\).
Оценки времени выполнения для разных алгоритмов
Обозначим T(N) - время выполнения алгоритма. Пусть исследуемый алгоритм имеет вид:
1. набор инструкций, включающих только базовые операции:
Statement 1;
...
statement k;
Тогда T(N) = T(statement 1) + ... + T(statement k).
Т.к. каждая инструкция включает только базовые операции, то время выполнения этого куска кода не зависит от размера входных данных (не растет с ростом размера входных данных), т.е. является константой. Этот алгоритм имеет сложность O(1).
2. if-else инструкции
If (condition) {
sequence of statements 1
}
else {
sequence of statements 2
}
Здесь выполнится либо sequence of statements 1, либо sequence of statements 2, поэтому, т.к. мы хотим получить оценку времени выполнения в наихудшем случае, T(N) = max(T(sequence of statements 1), T(sequence of statements 2)). Например, если время выполнения sequence of statements 1 будет O(N), а sequence of statements - O(1), то T(N) = O(N).
For (i = 0; i < N; i++) {
sequence of statements
}
Т.к. цикл выполнится N раз, то sequence of statements тоже выполнится N раз. Если T(sequence of statements) = O(1), то T(N) = O(N)*O(1) = O(N).
4. Вложенные циклы.
For (i = 0; i < N; i++) {
for (j = 0; j < M; j ++){
...
}
}
Внешний цикл выполняется N раз. Каждый раз, когда выполняется внешний цикл, выполняется внутренний цикл M Теперь рассмотрим такой код: For (i = 0; i < N; i++) { Посмотрим на изменение количества итераций внутреннего цикла в зависимости от итерации внешнего цикла. I цикл j (кол-во раз выполнения) Тогда sequence of statements выполнится N + N-1 + ... + 1 раз. Для быстрого подсчета подобных сумм пригодятся формулы из матанализа, в данном случае формула
А вот и другие наиболее часто нужные формулы, полезные для подобных случаев: 4. Когда утверждение включает вызов метода, то оценка времени выполнения утверждения рассчитывается с учетом оценки времени выполнения метода. Например: for (j = 0; j < N; j ++){ 5. Двоичный(бинарный) поиск. Int l = 0; Двоичный поиск позволяет найти индекс числа k в отсортированном массиве, если этого числа в нем нет, то возвращается -1. Сначала мы сравниваем k с числом, находящимся в середине массива. Если k меньше этого числа, то дальше мы должны искать его в левой половине массива, если больше - то в правой половине. Далее k сравнивается с числом, находящимся в середине выбранной на предыдущем шаге половины массива и т.д. С каждой итерацией пространство поиска сужается вдвое. Возникает вопрос: сколько итераций необходимо будет проделать в наихудшем случае (т.е. когда в массиве так и не будет найдено число, равное k и не останется данных для сравнения). Мы видим, что после 1 итерации останется \(N/2\) данных для поиска индекса \(k\), после 2 итерации останется \(N/4\) данных, после 3 итерации - \(N/8\) и т.д. Мы узнаем количество итераций в наихудшем случае, если решим уравнение \(\frac{N}{2^x}=1\). Это уравнение равносильно уравнению \(2^x=N\), отсюда \(x=log_{2}(N)\) или \(x=lg(N)\) (см. определение логарифма). Поэтому оценка сложности алгоритма бинарного поиска - \(O(logN)\). Хорошая новость заключается в том, что для характеризации времени выполнения большинства алгоритмов достаточно всего нескольких функций: \(1, logN, N, NlogN, N^2, N^3, 2^N\). На графике проиллюстрированы различные скорости роста времени выполнения алгоритма в зависимости от размера входных данных: Из этого графика, в частности, видно, что если время выполнения алгоритма "логарифмическое", т.е. алгоритм имеет сложность \(O(logN)\), то это очень круто, т.к. время его выполнения очень медленно растет с увеличением размера входных данных, если время выполнения линейно зависит от размера входных данных, то это тоже неплохо, а вот алгоритмы с экспоненциальным временем работы (\(O(2^N)\)) лучше не использовать совсем или использовать только на данных очень малого размера. классы P и NP
Вещественная неотрицательная функция \(f(m)\), определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином \(P(m)\) с вещественными коэффициентами такой, что \(f(m) \leq P(m)\) для всех \(m \in N^+\). Задачи, для которых существуют алгоритмы с "полиномиальным" временем работы принадлежат классу P (эти задачи в основном решаются быстро и без каких-либо проблем). Формальное определение.
Язык L принадлежит классу P, тогда и только тогда, когда существует детерминированная машина Тьюринга M, такая, что: При любых входных данных M заканчивает свою работу за полиномиальное время, Задачи класса NP
- задачи, удовлетворяющие условию: если имеется ответ (возможное решение), то его легко верифицировать - проверить, является оно решением или нет. Рассмотрим пример задачи из класса NP. Пусть дано множество целых чисел, например, {-7,-3, -2, 5, 8}. Требуется узнать, есть ли среди этих чисел 3 числа, которые в сумме дают 0. В данном случае ответ "да" (например, такой тройкой являются числа {-3,-2,5}. При возрастании размера множеств целых чисел количество подмножеств, состоящих из 3 элементов, экспоненциально возрастает. Между тем, если нам дают одно такое подмножество (его еще называют сертификатом), то мы легко можем проверить, равна ли 0 сумма его элементов. Формальное определение:
Язык L принадлежит классу NP, тогда и только тогда, когда существуют такие полиномы \(p\) и \(q\) и детерминированная машина Тьюринга M, такие, что: Для любых \(x,y\) машина M на входных данных \((x,y)\) выполняется за время \(p(|x|)\), Полиномиальная сводимость
или сводимость по Карпу. Функция \(f_1\) сводится к функции \(f_2\), если существует функция \(f \in P\), такая, что для любого \(x\) \(f_{1}(x)=f_{2}(f(x))\). Задача T называется NP-трудной
, если для нее существует такая NP-полная задача, которая сводится к T за полиномиальное время. Здесь имеется в виду сводимость по Куку. Сведение задачи \(R_1\) к \(R_2\) по Куку - это полиномиальный по времени алгоритм, решающий задачу \(R_1\) при условии, что функция, находящая решение задачи \(R_2\), ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг. Вот возможные соотношения между вышеупомянутыми классами задач (ученые до сих пор не уверены, совпадает ли P и NP). Необходимо подчеркнуть, что степень роста наихудшего времени выполнения - не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения: Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом - порядка n+n!/C, где C - постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй - нет, хотя, например, при С=10 (10 10) дело обстоит как раз наоборот. Класс сложности - это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя: Wikimedia Foundation
.
2010
.
временная сложность (алгоритма)
- — Тематики защита информации EN time complexity … Справочник технического переводчика
СЛОЖНОСТЬ ОПЕРАТОРСКОЙ ДЕЯТЕЛЬНОСТИ
- совокупность объективных факторов, влияющих на качество и продолжительность выполнения человеком требуемых функций в СЧМ. С. о. д. разделяется на несколько видов, каждый из которых характеризуется совокупностью факторов, определенным образом… … Энциклопедический словарь по психологии и педагогике
Вычислений функция, дающая числовую оценку трудности (громоздкости) процессов применения алгоритма к исходным данным. Уточнением А. с. вычислений служит понятие сигнализирующей функции (или просто сигнализирующей) функции, к рая задается… … Математическая энциклопедия
В информатике и теории алгоритмов вычислительная сложность алгоритма это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией… … Википедия
В информатике, теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми… … Википедия
Это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях… … Википедия
Алгоритм сортировки это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в… … Википедия
- (GM) криптографическая система с открытым ключом, разработанная Шафи Голдвассером и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических… … Википедия
Подробнее Определение сложности алгоритма
Получаемая в асимптотическом анализе оценка функции трудоемкости, называется сложностью алгоритма.
Следует иметь в виду, что существует несколько оценок сложности алгоритма. Асимптотика функции трудоемкости - это операционная сложность. Кроме нее можно указать следующие виды сложностей. Временная
сложность - асимптотическая оценка времени работы алгоритма на входных данных длиною п.
Очевидно, что при отсутствии распараллеливания вычислительных процедур время работы алгоритма однозначно определяется числом выполняемых операций. Постоянные коэффициенты, выражающие длительность выполнения операций, не влияют на порядок временной сложности, поэтому формулы операционной и временной сложностей часто совпадают друг с другом. Емкостная
сложность - асимптотическая оценка числа одновременно существующих скалярных величин при выполнении алгоритма на входных данных длиною п.
Структурная
сложность - характеристика количества управляющих структур в алгоритме и специфики их взаиморасположения. Когнитивная
сложность - характеристика доступности алгоритма для понимания специалистами прикладных областей. Виды и обозначения асимптотик
В асимптотическом анализе алгоритмов принято использовать обозначения математического асимптотического анализа. При этом рассматриваются три оценки (асимптотики) трудоемкости алгоритмов , которые обозначаются так: Вместо обозначения С1^(п))
очень часто используется более простое о(^(«)) с буквой «о» строчное курсивное. Поясним семантику формул на примере: если записано /(я) = 0(^2(л)), ТО ЭТО означает, ЧТО функция g(n)=og
2
(n)
является асимптотически точной оценкой функции трудоемкости /(«). По сути дела имеет место двухпозиционное определение в форме утверждения: Если f(n)
= @(log 2 («)), mo g(n)
= log 2 (л) - асимптотически точная оценка f(n).
Заметим, что постоянный множитель не влияет на порядок сложности алгоритма, поэтому основание логарифма опускают при указании логарифмической трудоемкости, и пишут просто /(л) = @(1о§(л)), подразумевая у логарифма произвольное основание большее единицы. Формальные определения асимптотик
Асимптотически точная оценка функции трудоемкости
с, с
2 , л 0 , такие что при л>л 0 функция /(л) с точностью до постоянных множителей не отличается от функции g(л), то функция g(n)
называется асимптотически точной оценкой функции /(л). где 9^, N - множества всех вещественных и натуральных чисел соответственно. Асимптотически точная верхняя оценка функции трудоемкости
вербально определяется так: если существуют положительные числа с
и л 0 , такие что при л>л 0 функция /(л) растет не быстрее, чем функция g(n)
с точностью до постоянного множителя с, то функция g{n)
называется асимптотически точной верхней оценкой функции Ап).
Более точная формальная запись определения имеет вид: Асимптотически точная нижняя оценка функции трудоемкости
вербально определяется так: если существуют положительные числа с
и л 0 , такие что при л>л 0 функция /(л) растет не медленнее, чем функция g{n)
с точностью до постоянного множителя с,
то функция?(л) называется асимптотически точной нижней оценкой функции Более точная формальная запись определения имеет вид: /(я) = 0.^(п))
Заметим, следующее: Совпадение и различие асимптотик
Обратим внимание на следующий факт: оценка /(я) = 0(?(я)) устанавливает для /(я) одновременно и верхнюю, и нижнюю оценки, поскольку ее определение предполагает справедливость отношения с г g(n)
Достаточно очевидно следующее свойство асимптотик: если оценка ф(п) = ©^(п))
существует, то справедливы равенства /(п
) = 0(^(я)) и /(я) = ?2(#(я)), т.е. верхние и нижние оценки трудоемкости совпадают друг с другом; если же /(я) = 0(? тах (я)) и ф(п) = С1^ тт (п
)), и g max (n)фg m
1п (я), то не существует функции g(n),
такой что /(я) = 0(?(я)). Совпадение верхней и нижней оценок трудоемкости возможно в следующих случаях: Следует помнить о существовании следующих трех важных правил, связанных с оценками порядка операционной сложности: В приведенных правилах использован символ только одной асимптотики 0(»), но они справедливы для всех асимптотических оценок - и для 0( )
, и &.{ ).
Во множестве элементарных функций можно указать список функционального доминирования: если -переменная, a,b -
числовые константы, то справедливы следующие утверждения: я" доминирует я!; я! доминирует а"; а"
доминирует Zj", если а>Ь а п
доминирует п
ь, если а
> 1 при любом b
е 9? ; п а
доминирует а/, если а>Ь
я доминирует log д (я), если а
> 1. Оценивание средней трудоемкости
В практике реальных вычислений существенный интерес представляет оценка /(я) математического ожидания трудоемкости М, поскольку в подавляющем большинстве случаев /(я) является случайной функцией. Однако в процессе экспериментальных исследований алгоритмов со случайной /(я) возникает дополнительная проблема - выбора количества испытаний для надежной оценки М. Преодоление этой проблемы является центральной задачей в . Предлагаемое в решение основано на использовании бета-распределения для аппроксимации /(я). Это весьма конструктивная и универсальная методика. Однако в современных условиях, когда производительность ЭВМ достаточно высока, во многих случаях можно использовать более простой способ выбора объема испытаний, основанный на контроле текущей вариативности значений f(n) -
значения оцениваются до тех пор, пока вариативность оценок не станет меньше заданной погрешности.
Оценивание операционной сложности алгоритма
Сложность алгоритма может быть определена исходя из анализа его управляющих структур. Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Поэтому определение сложности алгоритма сводится в основном к анализу циклов и рекурсивных вызовов. Рассмотрим алгоритм удаления к
-го элемента из массива размером п
, состоящий из перемещения элементов массива от (к +
1) -го до п
-го на одну позицию назад к началу массива и уменьшения числа элементов п
на единицу. Сложность цикла обработки массива составляет О(п-к),
так как тело цикла (операция перемещения) выполняется п-к
раз, а сложность тела цикла равна 0(1), т.е. является константой. В рассматриваемом примере сложность охарактеризована асимптотикой 0(»), поскольку количество выполняемых операций в этом алгоритме не зависит от конкретики значений данных. Функция трудоемкости является детерминированной, и все виды асимптотик совпадают друг с другом: f(n) = Q(n-k), f(n) = 0(n-k)
и f(n) = Q(n- к
). Об этом факте и свидетельствует указание именно ©( ). Использовать 0(*) и/или?2(*) следует только в том случае, если эти асимптотики различаются. Тип цикла (for, while, repeat) не влияет на сложность. Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. Вложенность повторений является основным фактором роста сложности. В качестве примера приведем сложности хорошо известных алгоритмов поиска и сортировки для массива размером п:
Заметим, что число операций сравнения в методе простого обмена имеют асимптотику 0(п
2), а число операций перестановки имеет две различных асимптотики 0(п 2)
и?2(0), потому что количество сравнений не зависит от конкретики значений сортируемых данных, в то время как количество перестановок определяется именно этой конкретикой. Перестановки могут не осуществляться вовсе, - если массив данных правильно упорядочен изначально, либо количество перестановок может быть максимальным - порядка п
2 , - если сортируемый массив исходно упорядочен в противном направлении. Название функции g(n)
в асимптотиках /(л) = @(^(л)) и /(«) = 0(g(n))
функции трудоемкости /(«) используется для характеристики алгоритма. Таким образом, говорят об алгоритмах полиномиальной, экспоненциальной, логарифмической и т. д. сложности.
Глава 2. Сложность алгоритмов.
2.1 Временная и вычислительная сложность алгоритмов.
Временная сложность алгоритма
(T
(N
)
, где N
– размер задачи) – это время выполнения алгоритма, измеренное в шагах (инструкциях алгоритма, которые нужно выполнять для достижения результата). Т. е. это – число элементарных операций, из которых складывается алгоритм решения задачи (:=, <>, =, +, –, *, /; and, or, not, xor; call, return). Различают три разновидности временной сложности, которые зависят от комбинации входных данных при решении задачи (равнозначность, разряженность, упорядоченность и др. свойства входных данных). https://pandia.ru/text/78/183/images/image002_151.gif" width="178 height=60" height="60"> Случай T
(N
)=
C
*
N
2
применим для квадратной матрицы. Элементарные операции в данном случае – совокупность «+» и «*». Если исходная матрица – единичная, то получаем Best Case. Если в матрице половина элементов – 0, половина – 1, то получаем Average Case. Константа С
, которая не может быть точно выражена, характеризует влияние внешних факторов на время выполнения алгоритмов (быстродействие ЭВМ, скорость компиляции). Поэтому использование единиц времени для оценки временной сложности алгоритмов не совсем корректно. В этом случае говорят, что временная сложность алгоритма умножения матрицы на вектор пропорциональна N
2
. 2.2
O
и Ω – нотации.
Характер поведения временной сложности при увеличении N
(N
®
¥
)
называется асимптотической сложностью алгоритма.
Для описания скорости роста асимптотической сложности используется О-нотация.
Когда говорят, что временная сложность алгоритма имеет порядок N
2
:
T
(N
)=
O
(N
2
)=
O
(f
(N
)),
То подразумевается, что существуют положительные константы C
, n0=
const
(C
>0),
такие, что для всех N
³
N
0
выполняется неравенство T
(N
)
£
C
*
f
(N
)
Это – верхняя граница оценки сложности. Пример 2
: Пусть Т(0)=1, Т(1)=4, …, Т(N
)=(N
+1)2
, тогда временная сложность этого алгоритма имеет порядок роста T
(N
)=
O
(N
2
).
Можно показать, что для всех N
>
n
0
при n
0
= 1,
C
= 4
выполняется неравенство (1). (N
+1)2
£
4*
N
2
Пример 3
: Если временная сложность записывается в виде полинома T
(N
)=
C
1
N
2
+
C
2
N
+
C
3
,
то такой алгоритм имеет порядок сложности, кратный степени максимального элемента полинома, т. к. он растет наиболее быстро при N
®
¥
:
T
(N
)=
O
(N
2
).
Например: 3
n
2
+5
n
+1
£
5
n
2
"
n
³
1
Пример 4
: Если некоторый алгоритм имеет сложность, кратную 3
n
, тогда можно показать, что порядок роста скорости не может быть кратен O
(2
n
):
T
(N
)=3
n
¹
O
(2
n
).
Пусть существуют константы C
,
n
0
, такие, что выполняются неравенство: 3
n
£
C
*2
n
,
n
>
n
0
.
Отсюда получаем: С
³
(3/2)2,
n
>
n
0
.
Но при n
®
¥
не существует такой константы С
, которая удовлетворяла бы данному неравенству. Кроме верхней границы сложности существует и нижняя граница скорости роста временной сложности: T
(N
)
³
W
(f
(N
))
Неравенство (2) подразумевает, что существует некоторая константа С
, для которой при N
®
¥
временная сложность T
(N
)
³
C
*
f
(N
).
Учитывая сложность точного определения T(N) (асимптотической временной сложности), в зависимости от размеров исходных данных на практике используют нижние и верхние границы временной сложности алгоритма: T
(N
) =
q
(f
(N
))
В зависимости от значения константы С
скорость роста сложности алгоритма может существенно меняться. Пример 5
: Пусть временная сложность записывается формулой T(N)=3n2 –100n+6=O(n2)
3n2 >3n2 –100n+6, n
³
1, C=3.
Если С1
»
0 (С1=0,00001)
, тогда неравенство 10-5
n
2
> 3
n
2
–100
n
+6,
n
³
1
не выполняется. Но можно показать, что порядок роста сложности 3n2 –100n+6
¹
O(N).
C*N < 3N2, N>C.
3n2 –100n+6=(n2)
C
=2.29,
n
³
n
0.
2.99*
n
2
< 3
n
2
–100
n
+6
3
n
2
–100
n
+6
¹
W
(n
3
)
при С=1.
Неравенство 3
n
2
–100
n
+6
³
n
3
не выполняется. 3
n
2
–100
n
+6=
W
(n
)
C
1
=
,
n
>
n
0
.
https://pandia.ru/text/78/183/images/image007_89.gif" width="305" height="247 src="> f
1
(N
)=100
n
2
f
2
(N
)=5
n
3
n
0
=20 –
критическая точка. Другой причиной предпочтения алгоритмов с меньшим порядком сложности является то, что чем меньше порядок сложности, тем больший размер задачи N
можно решить практически. 0 " style="margin-left:5.4pt;border-collapse:collapse;border:none"> n
!
Пример 6:
Нужно учитывать, что больший порядок роста сложности алгоритмов как правило имеет меньшую константу С1
по сравнению с малым порядком роста сложности, характеризующимся константой С2
. В этом случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для решения задач с малыми размерами данных (n
®
0
). Пусть заданы пять алгоритмов решения одной и той же задачи, имеющие сложности: А1: 100
N
А2: 100
N
*
logN
А3: 10
N
2
А4: N
3
А5: 2
N
Тогда для задач с N
=2
¸
9
более быстродействующим будет А5 (f
(N
) ~ 4
¸
512
). Другие алгоритмы при подстановке дадут существенно более низкие показатели. При N
=10
¸
58
предпочтительным оказывается А3. При N
=59
¸
1024
самым эффективным будет А2. При N
>1024
предпочтителен А1. Для программ, состоящих из нескольких последовательно или параллельно выполняющихся алгоритмов, сложность оценивается по правилу сумм
и правилу произведений
. Правило сумм
:
Пусть программа состоит из двух последовательно выполняющихся алгоритмов Р1 и Р2, для которых определены сложности O
(f
(n
))
и O
(g
(n
))
соответственно. Тогда временная сложность всей программы будет определяться как сумма временных сложностей каждого из алгоритмов: T
(n
) =
T
1
(n
)+
T
2
(n
)
В общем случае получаем: T(n)
Þ
O(max f(n), g(n))
Правило произведений:
Пусть временная сложность программы, состоящей из двух параллельно выполняющихся алгоритмов, имеющих порядок сложности O
(f
(n
))
и O
(g
(n
))
соответственно, определяется как произведение временных сложностей каждого из алгоритмов: T
(n
) =
T
1
(n
)*
T
2
(n
)
В общем случае: T
(n
)
Þ
O
(f
(n
)*
g
(n
))
Логарифмы.
2.3. Рекурсия.
Сложность рекурсивных алгоритмов оценить непросто в силу вложенности алгоритмических структур f
(n
)
Þ
f
(n
*
f
(n
-1))
Например, для рекурсивного вычисления алгоритма n! Сложность будет зависеть от сложности каждого из алгоритмов, входящих в рекурсию. В общем случае T
(n
) ~
O
(N
).
Другие рекурсивные алгоритмы в общем случае имеют временную сложность T
(n
) ~
O
(an
)
, где a
=
const
, что в результате дает суммарную сложность, большую, чем сложность не рекурсивного алгоритма решения этой же задачи. 2.4 Оценка сложности алгоритмов и программ.
2.4.2 Алгоритмы восстановления зависимостей.
В ряде случаев неизвестна структура программы, и можно лишь определить время ее работы при различных размерах входных данных T
(N
)
(сек.) Для построения аналитической зависимости сложности программы оценивают функцию T
(N
)
на некотором интервале [
Nmin
,
Nmax
]
. Затем проводят аппроксимацию найденной кривой некоторой аналитической функции с изменением параметров функции и оценкой ошибки аппроксимации. Как правило, в качестве такой функции используют известные функции временной сложности: O
(n
!),
O
(XN
),
O
(NX
),
O
(logN
),
O
(https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">В результате эксперимента над программой была получена таблица временных сложностей: В результате поиска аппроксимации функции была получена следующая аналитическая зависимость: https://pandia.ru/text/78/183/images/image012_68.gif" width="321" height="143 src="> Пример 2:
В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма. Полиномиальный или экспоненциальный характер работы алгоритма инвариантен относительно формы представления входных данных (двоичная, десятичная или другая система счисления). Говорят, что алгоритм является полиномиальным, если время его работы, т. е. временная сложность, ограничивается сверху полиномом некоторой степени T
(N
)=
O
(Nm
)
. Тогда все задачи, которые решаются таким алгоритмом, образуют Р-класс задач. Говорят, что эти задачи входят в Р. Задачи, временная сложность которых экспоненциальна (T
(N
)=
O
(K
N
)
), не входят в Р. Замечание
: Можно показать, что задачи с линейной сложностью входят в Р T
(N
)=
O
(N
1
)
Введем класс NP-задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма. Определим состояние алгоритма как совокупность адреса выполняемой в данный момент команды и значений всех переменных, что эквивалентно вектору состояния процесса. Поэтому большинство алгоритмов являются детерминированными, т. е. в них для любого состояния существует лишь одно допустимое следующее состояние (включая операции условия и выбора). Это значит, что такой алгоритм в каждый момент времени может делать что-то одно. В недетерминированном алгоритме
(НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора. НДА не является случайным или вероятностным алгоритмом. Он представляет собой алгоритм, который может находиться во многих состояниях (это эквивалентно параллельному решению задачи с множеством вариантов). Пример
: Детерминированный алгоритм (ДА) решал бы эту задачу последовательно (перебор всех вариантов, сравнение с критерием оптимальности K0 до тех пор, пока не выберет альтернативу А0). НДА может одновременно (параллельно) получить все альтернативы и сравнить с K0, копируя самого себя в виде отдельного процесса для каждой альтернативы, которая выполняется независимо. При этом если какая-либо копия обнаружит, что получен неправильный результат или результат не получен, то она прекращает свое исполнение. Если же копия находит решение, удовлетворяющее K0, то она объявляет об успехе, и все другие копии прекращают работу. Т. о. НДА характеризуется тремя параметрами: 1. выбор
– многозначная функция, значения которой являются элементами множества S; 2. неудача
заставляет копию алгоритма прекратить работу; 3. успех
заставляет все копии алгоритма прекратить работу и сформировать результат. Очевидно, что никакое физическое устройство не способно на неограниченное недетерминированное поведение, значит, НДА является теоретическим методом. Задачи, которые можно решить с помощью полиномиального НДА, образуют класс NP-задач. 2.5.2
NP
-трудные и
NP
-полные задачи.
Задача, входящая в Р, является NP
-трудной
, если существует полиномиальный ДА (ПДА) ее решения, который модно использовать для получения решения всех задач, входящих в NP. Т. е. такая задача является NP-трудной, если она, по крайней мере, так же трудна, как любая задача, входящая в NP. NP-трудная задача, принадлежащая NP, называется NP
-полной
задачей. Такие задачи не менее трудны, чем любая задача из NP. При этом существование ПДА для NP-трудной или NP-полной задачи означает, что классы Р и NP совпадают, т. е. возможно решение всех задач 3-го класса быстрым алгоритмом. Для доказательства того, что задача является NP-трудной, необходимо показать, что если для задачи существует ПДА, то его можно использовать для получения другого ПДА решения задач, входящих в NP. Чтобы установить, что задача является NP-полной, необходимо доказать, что она принадлежит NP. Идея использовать алгоритм решения одной задачи для получения алгоритма решения другой является одной из наиболее важных в теории алгоритмов. Определение 1
: Задача Р1 преобразуется в задачу Р2, если любой частный случай задачи Р1 можно преобразовать за полиномиальное время в некоторый частный случай задачи Р2. Тогда решение Р1 можно получить за полиномиальное время из решения частного случая задачи Р2. https://pandia.ru/text/78/183/images/image024_39.gif" width="158 height=56" height="56"> Например: f
2
(xi
)=(x
1
Ú
x
2
)
Ù
( )
Ù
()
не является выполнимой, т. к. при любых xi
f
2
(xi
)=
false
. Теорема
: Задача о выполнимости является NP-полной. xi выбор (true, false) if E(x1, x2, …, xN) then успех else неудача Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным. К-выполнимость
. К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных. Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*(х2)
, содержащую не более трех переменных в каждом дизъюнкте. Тогда Е
выполнима, если выполнима Е*.
E
*
(x
1
,
x
2
,…,
xn
)
®
E
*
(xi
)
Для этого используется метод уменьшения порядка дизъюнкта (a
1
Ú
a
2
Ú
…
Ú
a
k
)=(a
1
Ú
a
2
Ú
z
)
Ù
(a
3
Ú
a
4
Ú
…
Ú
a
k
Ú
)
Применяя итерационный процесс разложения, можно получить Е*
. Найти алгоритм решения Е*
проще, чем функции Е
. Но при этом доказав выполнимость Е*
, докажем выполнимость исходной функции Е
. Частный случай: при К=2 функция Е
входит в Р. Примерами задач NP-класса могут послужить также задачи на графах
: 1) Определение максимума клик неориентированного графа (NP-трудная задача). 2) Задача определения полного подграфа (NP-полная задача). 3) Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача). 4) Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача). 5) Задача определения существования Гамильтонова цикла для графа (NP-полная задача). 6) Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача). 7) Задача составления расписания (NP-полная задача). 2.6 Алгоритмически неразрешимые проблемы
Разделяют проблемы одиночные
и массовые
. Например: 5+7=? – одиночная проблема. х+у=? – массовая проблема. Принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения задач, из которых вытекало бы существование парадоксальных объектов. Например, парадоксами являются: Пример 1:
10-ая проблема Гильберта. Д. Гильберт в 1901 г. при решении диофантовых уравнений выдвинул проблему, которая гласит: Найти алгоритм, определяющий некоторое целочисленное решение для произвольного диофантового уравнения F
(x
,
y
, …)=0
Это – полином с целыми показателями степеней и целыми коэффициентами при неизвестных anxn+an-1xn-1+…+a2x2+a1x+a0=0
Для приведенного уравнения существует частное решение, которое заключается в том, что всякий целочисленный корень xi
является делителем a
0
. При этом a
0
раскладывают на простые множители и проверяют каждый множитель на соответствие корню. В 1970 г. ленинградский математик Ю. Матиясевич математически доказал алгоритмическую невозможность решения диофантового уравнения в общем виде. Пример 2:
Теорема Ферма: Не существует таких целых чисел a
,
b
, с, n (n
>2)
, для которых справедливо равенство an
+
bn
=
cn
Эта теорема была доказана для многих значений n
и проверена для частных случаев, однако до сих пор не создано общее доказательство теоремы. Пример 3:
Проблема Гольдбаха. Х. Гольбах в 1742 г. в письме к Эйлеру сформулировал проблему: Доказать, что каждое целое число N
³
6
может быть представлено в виде суммы трех простых чисел N
=
a
+
b
+
c
Это значит, что нужно найти алгоритм, который позволил бы для любого целого числа N
³
6
найти хотя бы одно разложение на три простых слагаемых. Частый случай решения этой проблемы предложил Эйлер: для четных N
эта проблема разрешима и равносильна разложению на два простых слагаемых. И. Виноградов в 1937 г. доказал, что для нечетных N
можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.
for (j = i + 1; j < N; j ++){
sequence of statements
}
}
0 N
1 N-1
2 N-2
...
N-1 1
Т.е. этот алгоритм будет иметь сложность \(O(N^2)\).
Если время выполнения метода \(g(N)=O(N)\), то \(T(N) = O(N)*O(N) = O(N^2)\).
int u = A.length - 1
int m;
while (l <= u) {
m = l + (u - 1)/2
if A[m] < k {
l = m +1;
}
else if A[m] == k {
return m;
}
else{
u = m - 1;
}
}
return -1;
- для всех \(x \in L\) M выдает результат 1,
- для всех \(x\), не принадлежащих \(L\), M выдает результат 0.
- для любого \(x \in L\) существует строка \(y\) длины \(q(|x|)\), такая что \(M(x,y)=1\),
- для любого \(x\) не из \(L\) и всех строк длины \(q(|x|)\) \(M(x,y)=0\).
Задача T называется NP-полной
, если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время. Пожалуй, наиболее известным примером NP-полной задачи является задача SAT(от слова satisfiability). Пусть дана формула, содержащая булевы переменные, операторы "И", "ИЛИ", "НЕ" и скобки. Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь
и истина
так, чтобы формула приняла значение "истина
".Обозначение
Интуитивное объяснение
Определение
f
ограничена сверху функцией g
style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
f
ограничена снизу функцией g
(с точностью до постоянного множителя) асимптотически
style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
f
ограничена снизу и сверху функцией g
асимптотически
0), n_0: \forall (n>n_0) \; |Cg(n)|
g
доминирует над f
асимптотически
style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
f
доминирует над g
асимптотически
style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
f
эквивалентна g
асимптотически
Примеры
Замечания
Классы сложности
Класс P
Проблема равенства классов P и NP
Знаменитые ученые
См. также
Ссылки
Смотреть что такое "Временная сложность алгоритма" в других словарях:
Можно показать, что нижняя граница
Часто бывает, что на время работы одного и того же алгоритма кроме размера задачи влияют другие параметры, вводимые пользователем.
Трудоемкость" href="/text/category/trudoemkostmz/" rel="bookmark">трудоемкостью (временем работы).
Если для решения задачи существует один алгоритм, то можно придумать и много других алгоритмов для решения этой же задачи. Какой алгоритм лучше подходит для решения конкретной задачи? По каким критериям следует выбирать алгоритм из множества возможных? Как правило, мы высказываем суждение об алгоритме на основе его оценки исполнителем-человеком. Алгоритм кажется нам сложным, если даже после внимательного его изучения мы не можем понять, что же он делает. Мы можем назвать алгоритм сложным и запутанным из-за того, что он обладает разветвленной логической структурой, содержащей много проверок условий и переходов. Однако для компьютера выполнение программы, реализующей такой алгоритм, не составит труда, так как он выполняет одну команду за другой, и для компьютера неважно - операция ли это умножения или проверка условия.
Более того, мы можем написать громоздкий алгоритм, в котором выписаны подряд повторяющиеся действия (без использования циклической структуры). Однако с точки зрения компьютерной реализации такого алгоритма практически нет никакой разницы, использован ли в программе оператор цикла (например, 10 раз на экран выводится слово "Привет") или 10 раз последовательно выписаны операторы вывода на экран слова "Привет".
Для оценки эффективности алгоритмов введено понятие сложности алгоритма.
Определение. Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.
Определение. Сложность алгоритма - количество элементарных шагов в вычислительном процессе этого алгоритма.
Обратите внимание, именно в вычислительном процессе, а не в самом алгоритме. Очевидно, для сравнения сложности разных алгоритмов необходимо, чтобы сложность подсчитывалась в одних и тех же элементарных действиях.
Определение. Временная сложность алгоритма - это время Т, необходимое для его выполнения. Оно равно произведению числа элементарных действий на среднее время выполнения одного действия: Т = kt.
Поскольку t зависит от исполнителя, реализующего алгоритм, то естественно считать, что сложность алгоритма в первую очередь зависит от k. Очевидно, что в наибольшей степени количество операций при выполнении алгоритма зависит от количества обрабатываемых данных. Действительно, для упорядочивания по алфавиту списка из 100 фамилий требуется существенно меньше операций, чем для упорядочивания списка из 100 000 фамилий. Поэтому сложность алгоритма выражают в виде функции от объема входных данных.
Пусть есть алгоритм А. Для него существует параметр а, характеризующий объем обрабатываемых алгоритмом данных, этот параметр часто называют размерностью задачи. Обозначим через Т(n) время выполнения алгоритма, через f - некую функцию от п.
Определение. Будем говорить, что Т(n) алгоритма имеет порядок роста f(n), или, по-другому, алгоритм имеет теоретическую сложность O * (f(n)) , если найдутся такие константы с 1 , с 2 > 0 и число п 0 , что c 1 f(n)) < Т(п) < c 2 f(n) при всех п >= n 0 . Здесь предполагается, что функция f(n) неотрицательна, но крайней мере при п >= n 0 . Если для Т(п) выполняется условие Т(n) <= сf(п), то говорят, что алгоритм имеет теоретическую сложность О(п) (читается "о" большое от n).
Так, например, алгоритм, выполняющий только операции чтения данных и занесения их в оперативную память, имеет линейную сложность 0(п). Алгоритм сортировки методом прямого выбора имеет квадратичную сложность 0(п 2) , так как при сортировке любого массива надо выполнить (п 2 - п)/2 операций сравнения (при этом операций перестановок вообще может не быть, например, на упорядоченном массиве, в худшем случае надо будет выполнить п перестановок). А сложность алгоритма умножения матриц (таблиц) размера п x п будет уже кубической O(n 3) , так как для вычисления каждого элемента результирующей матрицы требуется п умножений и п - 1 сложений, а всего этих элементов п 2 .
Для решения задачи могут быть разработаны алгоритмы любой сложности. Логично воспользоваться лучшим среди них, т.е. имеющим наименьшую сложность.
Наряду со сложностью важной характеристикой алгоритма является эффективность. Под эффективностью понимается выполнение следующего требования: не только весь алгоритм, но и каждый шаг его должны быть такими, чтобы исполнитель был способен выполнить их за конечное разумное время. Например, если алгоритм, выдающий прогноз погоды на ближайшие сутки, будет выполняться неделю, то такой алгоритм просто-напросто никому не нужен, даже если его сложность будет минимальной для класса подобных задач.
Если мы рассматриваем алгоритмы, реализующиеся на компьютере, то к требованию выполнения за разумное время прибавляется требование выполнения в ограниченном объеме оперативной памяти.
Известно, что во многих языках программирования нет операции возведения в степень, следовательно, такой алгоритм надо программисту писать самостоятельно. Операция возведения в степень реализуется через операции умножения; с ростом показателя степени растет количество операций умножения, которые выполняются достаточно долго. Следовательно, актуален вопрос о создании эффективного алгоритма возведения в степень.
Рассмотрим метод быстрого вычисления натуральной степени вещественного числа х. Этот метод был описан еще до нашей эры в Древней Индии.
Запишем п в двоичной системе счисления.
Заменим в этой записи каждую " 1" парой букв КХ, а каждый "О" - буквой К.
Вычеркнем крайнюю левую пару КХ.
Полученная строка, читаемая слева направо, дает правило быстрого вычисления х n , если букву К рассматривать как операцию возведения результата в квадрат, а букву X - как операцию умножения результата на х. Вначале результат равен х.
Пример 1. Возвести х в степень п = 100.
Переведем число п в двоичную систему счисления: п = 100 10 = 1100100,
Строим последовательность КХКХКККХКК
Вычеркиваем АХ слева => КХКККХКК
Вычисляем искомое значение
К => возводим х в квадрат => получаем х 2 ,
X => умножаем результат на х=> получаем х 3
К => возводим результат в квадрат => получаем х 6
К=> возводим результат в квадрат => получаем х 12 ,
К=> возводим результат в квадрат => получаем х 24 ,
Х=> умножаем результат на х =>получаем х 25
К=> возводим результат в квадрат => получаем x 50
К=> возводим результат в квадрат => получаем х 100 .
Таким образом, мы вычислили сотую степень числах всего за 8 умножений. Этот метод достаточно эффективный, так как он не требует дополнительной оперативной памяти для хранения промежуточных результатов. Однако заметим, что этот метод не всегда самый быстрый.
Например, при п = 49 учащиеся могут предложить такой эффективный алгоритм возведения в степень:
При реализации этого алгоритма было выполнено 7 операций умножения (вместо 48 операций при вычислении "в лоб") и использовано 3 ячейки (для хранения переменной х , для хранения значения х 16 и для хранения текущего результата, получаемого на каждом шаге). Если же использовать алгоритм "Быстрого возведения в степень", то получим то же количество операций (7 операций умножения), но для реализации этого алгоритма потребуется только 2 ячейки (для хранения переменной х и для хранения текущего результата).
Сама операция умножения реализуется в процессоре не "в лоб", а опять же через эффективные рекурсивные алгоритмы. Об одном из таких алгоритмов вы можете прочитать в Хрестоматии. Мы же рассмотрим алгоритм "быстрого" умножения, который был известен еще в Древнем Египте, его также называют "русским", или "крестьянским", методом. Разберем пример применения этого алгоритма.
Пример 2. Умножим 23 на 43 "русским" методом.
Ответ: 23 х 43 = 23 + 46 + 184 + 736 = 989.
В итоговую сумму вошли числа первого столбца, рядом с которыми во втором столбце стоят нечетные числа.
