Оценка сложности алгоритмов, или Что такое О(log n). Оценка сложности алгоритмов, или Что такое О(log n) Вычислительная сложность алгоритма
| Обозначение | Интуитивное объяснение | Определение |
|---|---|---|
| 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 асимптотически |  |
Примеры
Замечания
Необходимо подчеркнуть, что степень роста наихудшего времени выполнения - не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения:
Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом - порядка n+n!/C, где C - постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй - нет, хотя, например, при С=10 (10 10) дело обстоит как раз наоборот.
- Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
- Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
- В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.
Классы сложности
Класс сложности - это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:
Класс P
Проблема равенства классов P и NP
Знаменитые ученые
- Леонид Левин
- Александр Разборов
- Эди Шеймир
См. также
Ссылки
- Юрий Лифшиц «Современные задачи теоретической информатики » . Курс лекций по алгоритмам для NP-трудных задач.
- А. А. Разборов Theoretical Computer Science: взгляд математика // Компьютерра . - 2001. - № 2. (альтернативная ссылка)
- А. А. Разборов О сложности вычислений // Математическое просвещение . - МЦНМО , 1999. - № 3. - С. 127-141.
Wikimedia Foundation . 2010 .
Смотреть что такое "Временная сложность алгоритма" в других словарях:
временная сложность (алгоритма) - — Тематики защита информации EN time complexity … Справочник технического переводчика
СЛОЖНОСТЬ ОПЕРАТОРСКОЙ ДЕЯТЕЛЬНОСТИ - совокупность объективных факторов, влияющих на качество и продолжительность выполнения человеком требуемых функций в СЧМ. С. о. д. разделяется на несколько видов, каждый из которых характеризуется совокупностью факторов, определенным образом… … Энциклопедический словарь по психологии и педагогике
Вычислений функция, дающая числовую оценку трудности (громоздкости) процессов применения алгоритма к исходным данным. Уточнением А. с. вычислений служит понятие сигнализирующей функции (или просто сигнализирующей) функции, к рая задается… … Математическая энциклопедия
В информатике и теории алгоритмов вычислительная сложность алгоритма это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией… … Википедия
В информатике, теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми… … Википедия
Это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях… … Википедия
Алгоритм сортировки это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в… … Википедия
- (GM) криптографическая система с открытым ключом, разработанная Шафи Голдвассером и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических… … Википедия Подробнее
Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики нас учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.
Всегда следует искать оптимум в соответствии с поставленной задачей, в частности, при разработке алгоритмов решения класса задач.
Важно также оценивать, как будет вести себя алгоритм при начальных значениях разного объёма и количества, какие ресурсы ему потребуются и сколько времени уйдёт на вывод конечного результата.
Этим занимается раздел теории алгоритмов – теория асимптотического анализа алгоритмов.
Предлагаю в этой статье описать основные критерии оценки и привести пример оценки простейшего алгоритма. На Хабрахабре уже есть про методы оценки алгоритмов, но она ориентирована, в основном, на учащихся лицеев. Данную публикацию можно считать углублением той статьи.
Определения
Основным показателем сложности алгоритма является время, необходимое для решения задачи и объём требуемой памяти.
Также при анализе сложности для класса задач определяется некоторое число, характеризующее некоторый объём данных – размер входа
.
Итак, можем сделать вывод, что сложность алгоритма
– функция размера входа.
Сложность алгоритма может быть различной при одном и том же размере входа, но различных входных данных.
Существуют понятия сложности в худшем , среднем или лучшем случае . Обычно, оценивают сложность в худшем случае.
Временная сложность
в худшем случае – функция размера входа, равная максимальному количеству операций, выполненных в ходе работы алгоритма при решении задачи данного размера.
Ёмкостная сложность
в худшем случае – функция размера входа, равная максимальному количеству ячеек памяти, к которым было обращение при решении задач данного размера.
Порядок роста сложности алгоритмов
Порядок роста сложности (или аксиоматическая сложность) описывает приблизительное поведение функции сложности алгоритма при большом размере входа. Из этого следует, что при оценке временной сложности нет необходимости рассматривать элементарные операции, достаточно рассматривать шаги алгоритма.
Шаг алгоритма – совокупность последовательно-расположенных элементарных операций, время выполнения которых не зависит от размера входа, то есть ограничена сверху некоторой константой.
Виды асимптотических оценок
O – оценка для худшего случая
Рассмотрим сложность f(n) > 0
, функцию того же порядка g(n) > 0
, размер входа n > 0
.
Если f(n) = O(g(n))
и существуют константы c > 0
, n 0 > 0
, то
0 < f(n) < c*g(n),
для n > n 0
.
Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).
Данное выражение определяет класс функций, которые растут не быстрее, чем g(n) с точностью до константного множителя.
Примеры асимптотических функций
| f(n) | g(n) |
|---|---|
| 2n 2 + 7n - 3 | n 2 |
| 98n*ln(n) | n*ln(n) |
| 5n + 2 | n |
| 8 | 1 |
Ω – оценка для лучшего случая
Определение схоже с определением оценки для худшего случая, однако
f(n) = Ω(g(n))
, если
0 < c*g(n) < f(n)
Ω(g(n)) определяет класс функций, которые растут не медленнее, чем функция g(n) с точностью до константного множителя.
Θ – оценка для среднего случая
Стоит лишь упомянуть, что в данном случае функция f(n)
при n > n 0
всюду находится между c 1 *g(n)
и c 2 *g(n)
, где c – константный множитель.
Например, при f(n) = n 2 + n
; g(n) = n 2
.
Критерии оценки сложности алгоритмов
Равномерный весовой критерий (РВК)
предполагает, что каждый шаг алгоритма выполняется за одну единицу времени, а ячейка памяти за одну единицу объёма (с точностью до константы).
Логарифмический весовой критерий (ЛВК)
учитывает размер операнда, который обрабатывается той или иной операцией и значения, хранимого в ячейке памяти.
Временная сложность при ЛВК
определяется значением l(O p)
, где O p
– величина операнда.
Ёмкостная сложность при ЛВК
определяется значением l(M)
, где M
– величина ячейки памяти.
Пример оценки сложности при вычислении факториала
Необходимо проанализировать сложность алгоритма вычисление факториала. Для этого напишем на псевдокоде языка С данную задачу:
Void main() { int result = 1; int i; const n = ...; for (i = 2; i <= n; i++) result = result * n; }
Временная сложность при равномерном весовом критерии
Достаточно просто определить, что размер входа данной задачи – n
.
Количество шагов – (n - 1)
.
Таким образом, временная сложность при РВК равна O(n) .
Временная сложность при логарифмическом весовом критерии
В данном пункте следует выделить операции, которые необходимо оценить. Во-первых, это операции сравнения. Во-вторых, операции изменения переменных (сложение, умножение). Операции присваивания не учитываются, так как предполагается, что она происходят мгновенно.
Итак, в данной задаче выделяется три операции:
1) i <= n
На i-м шаге получится log(n)
.
Так как шагов (n-1)
, сложность данной операции составит (n-1)*log(n)
.
2) i = i + 1
На i-м шаге получится log(i)
.
.
3) result = result * i
На i-м шаге получится log((i-1)!)
.
Таким образом, получается сумма 
.
Если сложить все получившиеся значения и отбросить слагаемые, которые заведомо растут медленнее с увеличением n
, получим конечное выражение 
.
Ёмкостная сложность при равномерном весовом критерии
Здесь всё просто. Необходимо подсчитать количество переменных. Если в задаче используются массивы, за переменную считается каждая ячейка массива.
Так как количество переменных не зависит от размера входа, сложность будет равна O(1)
.
Ёмкостная сложность при логарифмическом весовом критерии
В данном случае следует учитывать максимальное значение, которое может находиться в ячейке памяти. Если значение не определено (например, при операнде i > 10), то считается, что существует какое-то предельное значение V max
.
В данной задаче существует переменная, значение которой не превосходит n (i)
, и переменная, значение которой не превышает n! (result)
. Таким образом, оценка равна O(log(n!))
.
Выводы
Изучение сложности алгоритмов довольно увлекательная задача. На данный момент анализ простейших алгоритмов входит в учебные планы технических специальностей (если быть точным, обобщённого направления «Информатика и вычислительная техника»), занимающихся информатикой и прикладной математикой в сфере IT.
На основе сложности выделяются разные классы задач: P
, NP
, NPC
. Но это уже не проблема теории асимптотического анализа алгоритмов.
Глава 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:
Часто бывает, что на время работы одного и того же алгоритма кроме размера задачи влияют другие параметры, вводимые пользователем.
В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма.
Трудоемкость" href="/text/category/trudoemkostmz/" rel="bookmark">трудоемкостью (временем работы).
Полиномиальный или экспоненциальный характер работы алгоритма инвариантен относительно формы представления входных данных (двоичная, десятичная или другая система счисления).
Говорят, что алгоритм является полиномиальным, если время его работы, т. е. временная сложность, ограничивается сверху полиномом некоторой степени 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 можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.
Для решения одной и той же задачи часто можно придумать более одного алгоритма. В связи с чем, возникает вопрос: какой из алгоритмов “лучше”?
В большинстве случаев, “лучше”, видимо, такой алгоритм, который на тех же входных данных приходит к решению задачи, потребляя меньшее количество вычислительных ресурсов (памяти и времени). Это, конечно, нестрогое рассуждение. Для более строгого рассуждения введем несколько понятий.
Вычислительный процесс алгоритма это последовательность шагов, пройденная при исполнении алгоритма для некоторых входных данных.
Важно понимать разницу между самим алгоритмом и вычислительным процессом, порождаемым этим алгоритмом. Первый является только описанием второго.
Временна́я сложность алгоритма это время \(T\) , необходимое для завершения вычислительного процесса алгоритма для некоторых входных данных.
Ясно, что время выполнения зависит от конкретного исполнителя. Скажем, электронный калькулятор и суперкомпьютер, вероятно, будут выполнять один и тот же алгоритм разное время.
Однако можно время \(T\) выразить через количество элементарных действий \(k\) и среднее время выполнения элементарного действия \(t\) :
При этом, \(k\) является свойством самого алгоритма, а \(t\) – свойством исполнителя.
Ввиду того, что \(t\) можно считать константой для данного исполнителя, обычно сложность алгоритмов оценивается с точностью до константного множителя. Другими словами, сложность алгоритма оценивается порядком роста .
Порядок роста положительно-определенная функция \(g(x)\) имеет порядок роста \(f(x)\) (записывается \(g(x)=\mathcal{O}(f(x))\) ), если \(\exists c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\) .
В зависимости от входных данных, алгоритм может выполняться различное время. Обычно оценивается средняя сложность и сложность в худшем случае . Так же есть зависимость от количества входных данных \(n\) . Обычно оценивается именно порядок роста от \(n\) .
Так, например, чтение данных и сохранение их в памяти в виде массива будет иметь сложность \(\mathcal{O}(n)\) , или линейную сложность , а умножение матриц уже кубическую \(\mathcal{O}(n^3)\) .
Кроме времмено́й сложности алгоритма, важной оказывается так же пространственная сложность алгоритма.
Пространственная сложность алгоритма это количество дополнительной памяти \(S\) , которое алгоритм требует для работы. Память \(D\) , необходимая для хранения входных данных, не включается в \(S\) .
\(S\) в общем случае тоже зависит от исполнительного устройства. Скажем, если два исполнительных устройства поддерживают целые длинной 4 и 8 байт соответственно, то пространственная сложность алгоритма на 8-байтных целых будет вдвое больше, чем на 4-байтных целых. Поэтому пространственная сложность оценивается так же порядком роста.
Классы сложности алгоритмов
Выделяются определенные классы сложности : это категории, которые имеют схожую сложность.
Выделяют следующие основные классы сложности:
DTIME Машина Тьюринга находит решение задачи за конечное время (количество шагов). Часто уточняется асимптотика алгоритма, так, скажем, если порядок роста времени работы \(T(n) = \mathcal{O}(f(n))\) , то указывают \(DTIME(f(n))\) . P Машина Тьюринга находит решение задачи за полиномиальное время (количество шагов), т.е. \(T(n) = \mathcal{O}(n^k)\) , где \(k\in \mathbb{N}\) . \(P=DTIME(n^k)\) EXPTIME Машина Тьюринга находит решение задачи за экспоненциальное время (количество шагов), т.е. \(T(n) = \mathcal{O}(2^{n^k})\) , где \(k\in \mathbb{N}\) . \(EXPTIME=DTIME(2^{n^k})\) . DSPACE Машина Тьюринга находит решение задачи, используя конечное количество дополнительной памяти (ячеек). Часто уточняется асимптотика алгоритма, так, скажем, если порядок роста потребления памяти \(S(n) = \mathcal{O}(f(n))\) , то указывают \(DSPACE(f(n))\) . L Машина Тьюринга находит решение задачи c логарифмической пространственной сложностью, то есть \(S(n) = \mathcal{O}(\log n)\) . \(L=DSPACE(\log n)\) . PSPACE Машина Тьюринга находит решение задачи c полиномиальной пространственной сложностью, то есть \(S(n) = \mathcal{O}(n^k)\) , где \(k\in \mathbb{N}\) . \(PSPACE=DSPACE(n^k)\) . EXPSPACE Машина Тьюринга находит решение задачи c экспоненциальной пространственной сложностью, то есть \(S(n) = \mathcal{O}(2^{n^k})\) , где \(k\in \mathbb{N}\) . \(EXPSPACE=DSPACE(2^{n^k})\) .
Кроме того, существуют теоретические классы сложности, которые оперируют понятием недетерменированной машины Тьюринга (НМТ). Их определения совпадают с вышеприведенными, с заменой машины Тьюринга на НМТ, а названия имеют префикс N (например NP), кроме NTIME и NSPACE, где D заменяется на N.
НМТ – это чисто теоретическое построение, которое по принципам действия аналогично МТ, с тем отличием, что для каждого из состояний может быть несколько возможных действий. При этом, НМТ всегда выбирает из возможных действий то, которое приводит к решению за минимально возможное число шагов. Эквивалентно, НМТ производит вычисления всех ветвей и выбирает ту ветвь, которая приводит к решению за минимально возможно число шагов.
Иногда можно услышать, что квантовые компьютеры являются реализацией НМТ. Хотя это может казаться верным в некоторых случаях, в общем случае НМТ является более мощной системой, чем квантовый компьютер.
Известно, что \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)
Кроме того, \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)
Так же известно, что если \(P = NP\) , то \(EXPTIME = NEXPTIME\) .
Вопрос равенства P и NP является одним из главных нерешенных вопросов современной информатики.
Примеры алгоритмов
Приведем несколько примеров простых алгоритмов и рассмотрим их сложность.
Возведение в целую степень
Этот алгоритм был описан в Древней Индии еще до нашей эры и используется для вычисления натуральной степени \(n\) вещественного числа \(x\)
- Записать \(n\) в двоичной системе счисления
- Заменить в этой записи каждую из 1 парой букв КХ, а каждый 0 – буквой К
- Вычеркнуть крайнюю левую пару КХ
- Читая полученную строку слева направо, встречая букву К возвести результат в квадрат, а встречая букву X – умножить результат на x. В начале результат равен x.
В этом алгоритме, мы имеем число операций умножения, равное количеству цифр в двоичном представлении \(n\) в лучшем случае, и \(2(n-1)\) в худшем случае. В любом случае, временная сложность .
Дополнительной памяти в эффективной реализации алгоритма практически не требуется, и она не зависит от входных данных, поэтому пространственная сложность \(S(n) = \mathcal{O}(1)\) .
Следует заметить, что существуют более эффективные алгоритмы. Однако по сравнению с “наивной” реализацией, требующей \(\mathcal{O}(n)\) операций умножения, этот алгоритм сравнительно эффективен.
Умножение целых
Этот алгоритм умножения называют иногда русским или крестьянским, хотя он был известен еще в Древнем Египте.
Первый множитель последовательно умножается на два, а второй – делится нацело на 2. Результаты записываются в два столбика, пока во втором не получится 1.
Результатом умножения является сумма чисел первого столбика, напротив которых стоят нечетные числа во втором столбике.
Поскольку целочисленное деление и умножение на 2 можно реализовать сдвигом, этот алгоритм дает \(2 \log_2 n\) операций сдвига, где \(n\) – меньшее из двух чисел. В худшем случае так же получается \(\log_2 n - 1\) операций сложения. В любом случае, временная сложность \(T(n) = \mathcal{O}(\log n)\) .
Для эффективной реализации алгоритма, дополнительной памяти практически не требуется, и она не зависит от входных данных, поэтому \(S(n) = \mathcal{O}(1)\)
Опять же, следует заметить, что существуют более эффективные алгоритмы. Однако по сравнению с “наивной” реализацией, требующей \(\mathcal{O}(n)\) операций сложения, этот алгоритм сравнительно эффективен.
Пример
Умножение 23 на 43.
Возьмем 23 в качестве второго множителя.
| 43 | 23 | нечетное |
| 86 | 11 | нечетное |
| 172 | 5 | нечетное |
| 344 | 2 | |
| 688 | 1 | нечетное |
Результат \(43+86+172+688 = 989\)
Получили 10 операций сдвига и 4 операции сложения. Для справки, \(\log_2(23) \approx 4.52\) .
Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы так и не понимаете, что это значит, - эта статья для вас.
Оценка сложности
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.
Допустим, некоторому алгоритму нужно выполнить 4n 3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n 3) , т. е. зависит от размера входных данных кубически.
Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .
Примеры
O(n) - линейная сложность
Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
O(log n) - логарифмическая сложность
Простейший пример - бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива - там его точно нет. Если же меньше, то наоборот - отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
O(n 2) - квадратичная сложность
Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n 2 .
Бывают и другие оценки по сложности, но все они основаны на том же принципе.
Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.
Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.
