Для сравнения алгоритмов принято использовать обобщенную характеристику, называемую эффективностью. Говорят, что алгоритм Л, эффективнее алгоритма А 2 , если алгоритм Л, выполняется за меньшее время и (или) требует меньше компьютерных ресурсов (оперативной памяти, дискового пространства, сетевого трафика и т.п.).
Эффективный алгоритм должен удовлетворять требованиям приемлемого времени исполнения и разумной ресурсоемкое™, о чем уже упоминалось в параграфе 1.1. Совокупность этих характеристик составляет понятие сложности алгоритма. При увеличении времени исполнения алгоритма и (или) задействованных ресурсов сложность возрастает. Таким образом, понятия эффективности и сложности являются обратными один относительно другого.
Характеристика алгоритма, отражающая временные затраты на его реализацию, называется временной сложностью. Характеристика алгоритма, отражающая компьютерные ресурсные затраты на его реализацию, называется емкостной сложностью.
При количественной и качественной оценках алгоритма, связанных с определением сложности, используют два подхода - практический и теоретический.
Практический подход связан с реально выполняемыми алгоритмами на конкретных физических устройствах. Он характеризуется параметрами, которые можно измерить и зафиксировать. Временная сложность при таком подходе может выражаться во временных единицах (например, миллисекундах) или количестве тактов процессора, затрачиваемых на выполнение алгоритма. Емкостная сложность может выражается в битах (или других единицах измерения информации), минимальных аппаратных требованиях, необходимых для выполнения алгоритма, и пр.
Практическая оценка не является абсолютным показателем эффективности алгоритма. Количественные значения, получаемые при таком подходе, зависят от множества факторов, таких как:
- технические характеристики компонент, составляющих вычислительную систему. Так, чем выше тактовая частота работы процессора, тем больше элементарных операций в единицу времени может быть выполнено;
- характеристики программной среды (количество запущенных процессов, алгоритм работы планировщика заданий, особенностей работы операционной системы и т.д.);
- выбранный язык программирования для реализации алгоритма. Программа, написанная на языке высокого уровня, скорее всего, будет выполняться медленнее и потребует больше ресурсов, нежели программа, написанная на низкоуровневых языках, имеющих непосредственный доступ к аппаратным ресурсам;
- опыт программиста, реализовавшего алгоритм. Скорее всего, начинающий программист напишет менее эффективную программу, чем программист, имеющий опыт.
Таким образом, алгоритм, выполняемый в одной и той же вычислительной системе для одних и тех же входных данных, может иметь различные количественные оценки в различные моменты времени. Поэтому более важным оказывается теоретический подход к определению сложности.
Теоретическая сложность характеризует алгоритм без привязки к конкретному оборудованию, программному обеспечению и средствам реализации. В этом случае временная сложность выражается в количестве операций, тактах работы машины Тьюринга и т.д. Емкостная сложность определяется объемом данных (входных, промежуточных, выходных), числом задействованных ячеек на ленте машины Тыоринга и т.д.
При теоретическом подходе к оценке эффективности считается, что алгоритм выполняется на некотором идеализированном компьютере , для которого время выполнения каждого вида операций известно и постоянно. Также считается, что ресурсы такого компьютера бесконечны, поэтому емкостную сложность при теоретическом подходе обычно не определяют. В качестве временной характеристики сложности выбирают количество инструкций (операций), выполняемых на идеализированном компьютере.
Количественные оценки, получаемые при теоретическом подходе, также могут зависеть от ряда следующих факторов:
- объем входных данных. Чем он больше, тем больше времени потребуется на выполнение алгоритма;
- выбранный метод решения задачи. Например, для большого объема входных данных алгоритм быстрой сортировки эффективное, чем алгоритм пузырьковой сортировки, хотя и приводит к такому же результату.
Время выполнения алгоритма обычно зависит от объема входных данных (размер входа), под которым понимают размерность решаемой задачи. Так, при сортировке множества значений объем данных составляет количество элементов этого множества. При обработке строк объемом входных данных считается длина строки.
Пусть п - объем входных данных для некоторого алгоритма. Обозначим за Т(п) количество инструкций, выполняемых на идеализированном компьютере при исполнении алгоритма, причем оно определяется для «наихудшего случая», когда объем операций максимален.
Понятие «наихудшего случая» можно проиллюстрировать на примере. Пусть рассматривается алгоритм проверки наличия числового элемента в некотором множестве (массиве) чисел. Если это множество упорядочено по возрастанию, то, вообще говоря, нет смысла проверять элементы, расположенные после первого элемента, который больше искомого. В этом случае Т(п) п. Однако в наихудшем случае (для произвольного несортированного множества) придется просмотреть все элементы множества. Очевидно, здесь Т(п) = п.
Вообще говоря, Т(п) является некоторой функцией от объема входных данных п. Во многих случаях Т(п) выражается полиномиальной, степенной или логарифмической функцией от п.
Поведение величины Т(п) в зависимости от увеличения п называют асимптотической сложностью алгоритма. Говорят, что Т(п ) имеет порядок сложности 0(J(n)) (читается «О большое от/от п») для некоторого алгоритма, если существуют константа с и объем данных щ такие, что Уп > п 0 и имеет место неравенство Т(п ) с/(п).
Данный факт записывается как Т(п) = 0(J(n)) и означает, что для функции Т(п) существуют такая функция f(n) и константа с, для которых, начиная с некоторого п 0 , значение Т(п) не превосходит cf(n).
Функция f(n) представляет собой верхнюю границу значений функции Т(п). Пусть, например, Т(п) = 2п А + п 2 . Выбрав значения п 0 = 0 и с = 5, для любого п > п 0 имеем Т(п) = 2п А + п 2 Т(п) имеет порядок я 4 .
Функция Т(п ) связана с определенным алгоритмом, поэтому часто говорят, что порядок сложности 0(/(п)) имеет именно алгоритм.
Говорят, что Т(п) имеет нижнюю границу Q(g(n)) (читается «омега большое от g от /г»), если существуют константа с и объем данных п 0 такие, что /п и имеет место неравенство Т(п) > cg(n).
Данный факт записывается как Т(п) = Q(g(n)). Пусть, например, Т(п) = 2я 4 + п 2 . Выбрав значение с = 1, для любого п имеем Т{п) = 2я 4 + п 2 > сп А > следовательно, Т(п ) имеет нижнюю границу я 4 .
Нетрудно видеть, что порядок и нижняя граница не являются единственными для некоторой функции Т(п). В примерах выше в качестве /(я) можно было выбрать я 5 , я 6 ,..., а в качестве g(n) - я 3 , я 2 ,.... Обычно в качестве /(я) выбирают функцию с минимальной степенью, а в качестве g(n) - с максимальной.
Порядок сложности 0(/(я)) и нижняя граница Q(g(rc)) представляют собой классы функций. Интуитивно Q(g"(n)) можно понимать как класс функций растущих по крайней мере так же быстро, как и Т(п). Аналогично, интуитивно 0(f(n)) можно понимать как класс функций, растущих не быстрее, чем Т(п). С практической точки зрения при оценке сложности алгоритма наиболее важным оказывается именно класс функций 0(f(n)). Определение вида функции /(я) и является основной задачей расчета теоретической сложности алгоритма.
Для любого алгоритма при определении степени роста можно воспользоваться следующими свойствами 0(/(я)):
1) 0(kf(ji)) = 0(/(я)), где k = const. Таким образом, постоянный множитель в функции не оказывает влияние на скорость роста. Например,
2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)). Таким образом, порядок произведения двух функций равен произведению их сложностей. Например,
Иногда это свойство записывают как
3) 0(/(п) + g(n)) равен доминанте (функции с максимальной степенью) функций /(я) и g(n). Например,
В теории сложности алгоритмов выделяют следующие классы функций сложности:
- 1) константная сложность 0(1). Время работы алгоритма и используемые ресурсы не имеют зависимости от объема входных данных. Обычно такую сложность имеют алгоритмы, не содержащие циклов и рекурсивных вызовов;
- 2) линейная сложность 0(п). Обычно такую сложность имеют задачи, в которых каждый элемент входных данных должен быть обработан определенное количество раз, никак не связанное с количеством обработок других элементов;
- 3) логарифмическая сложность 0(log 2 w), 0(nog 2 n). Иногда используются и другие основания логарифма;
- 4) полиномиальная сложность 0(я 2), 0(/г 3), 0(я 4),...;
- 5) экспоненциальная сложность 2 п, 3",....
При увеличении размера входа сложность каждого последующего типа функций растет быстрее, чем предыдущего (кроме 0(log 2 /?)). Для достаточно большого объема входных данных предпочтительнее использовать алгоритмы с меньшей сложностью.
При количественном подсчете сложности первоначально выбирают операцию или группу операций, которая значима для этого алгоритма (составляет его основу). В их качестве обычно выступают операции сравнения и арифметические операции. К операциям сравнения относят проверку значений двух величин (меньше, больше, равно, меньше или равно, больше или равно, не равно). Они считаются эквивалентными по времени выполнения. Арифметические операции, в свою очередь, делят на аддитивные и мультипликативные. К первым (часто называемым просто сложением) относят сложение, вычитание, уменьшение или уменьшение значения счетчика. Ко вторым (называемым просто умножением) относят умножение, деление, взятие остатка по модулю.
Операции сложения выполняются быстрее, чем операции умножения, поэтому алгоритмы с меньшим количеством умножений являются предпочтительными, даже если количество сложений растет пропорционально количеству уменьшения умножений.
Операции целочисленного умножения или деления па степень числа 2 относят к аддитивным операциям, так как при работе с ячейками памяти они сводятся к сдвигу, который эквивалентен операции сложения.
После выбора значимых операций они делятся на две категории:
- 1) операции, непосредственно влияющие на сложность алгоритма;
- 2) операции, составляющие «накладные расходы» при выполнении алгоритма (например, выделение памяти для хранения промежуточных данных).
Непосредственный подсчет или оценка количества выполняемых операций позволяет оценить Т(п).
Для оценки порядка сложности можно использовать анализ программного кода, реализующего алгоритм. При этом:
- алгоритмы без циклов и рекурсивных вызовов имеют сложность порядка 0(1). Таким образом, операции присваивания, ввода и вывода данных, условные конструкции имеют константную сложность;
- если две части программного кода имеют сложности 0(J { (ri)) и 0(J 2 (n)), то последовательное выполнение имеет сложность
- если тело цикла выполняется один раз для каждого элемента входных данных, то сложность выполнения цикла имеет порядок 0(п)0( 1) = 0(п);
- порядок сложности выполнения вложенных циклов вычисляется по правилу произведения 0(J x (n)f 2 (n)) = 0(/,(/?))- 0(J 2 (ri)). Если каждый из них имеет сложность порядка 0(п), выполнение вложенных циклов имеет сложность порядка 0(п 2).
Пример 1.3
Определить порядок сложности алгоритма программы на языке
Pascal, приведенного в листинге 1.2. Строки программы пронумерованы в виде комментариев (см. параграф 2.6).
Листинг 1.2
{01} for i:=l to n do
{02} begin
{03} write("Введите элемент массива
с индексом ",i,": ");
{04} Readln(MyArray[i]);
{05} end;
{06} for i:=l to n do
{07} for j:=1 to n do
{08} begin
{09} write("Введите элемент массива
с индексами ", i, ",", j, " : ");
{10} Readln(МуDArray);
{11} end;
Решение
Строки 02, 05, 08, 11 не содержат исполняемых операторов, поэтому при определении порядка они не учитываются.
Строки 03 и 04 имеют порядок 0(1). Последовательное их выполнение имеет порядок 0(1) + 0(1) = 0(1). Аналогично, последовательное выполнение строк 09 и 10 имеет сложность 0(1).
Цикл в строках 01-05 имеет сложность порядка О(п), вложенные циклы в строках 06-11 - порядка 0(п 2). Итоговая сложность алгоритма имеет порядок
Оценка сложности алгоритма, как временной, так и ресурсной, позволяет определить максимальное и среднее время исполнения алгоритма. Это крайне важно при обработке больших массивов информации, особенно в задачах сортировки и поиска, рассмотренных далее.
Функция сложности 0(1). В алгоритмах константной сложности большинство операций в программе выполняются один или несколько раз. Любой алгоритм, всегда требующий (независимо от размера данных) одного и того же времени, имеет константную сложность.
Функция сложности 0(N). Время работы программы обычно линейно, когда каждый элемент входных данных требуется обработать лишь линейное число раз. Эта функция сложности характеризует простой цикл.
Функция сложности 0(N 2), 0(N 3), 0(№) - полиномиальная функция сложности: число операций растет пропорционально квадрату N. В общем случае может быть О(Л^) в зависимости от сложности задачи. Эта функция сложности характеризует сложный цикл.
Функция сложности O(Log 2 (A0), 0(N log 2 (A0). Такое время работают алгоритмы, которые делят большую проблему на множество небольших, а затем, решив их, объединяют решения.
Функция сложности 0(e N). Алгоритмы с экспоненциальной сложностью чаще всего возникают в результате подхода, именуемого методом грубой силы.
Функция сложности 0(М) - число операций растет пропорционально факториалу N.
Программист должен уметь проводить анализ алгоритмов и определять их сложность. Временная сложность алгоритма может быть подсчитана исходя из анализа его управляющих структур.
Алгоритмы без циклов и рекурсивных вызовов имеют константную сложность. Если нет рекурсии и циклов, все управляющие структуры могут быть сведены к структурам константной сложности. Следовательно, и весь алгоритм также характеризуется константной сложностью. Определение сложности алгоритма, в основном, сводится к анализу циклов и рекурсивных вызовов.
Например, рассмотрим алгоритм обработки элементов массива.
For /": = 1 to N do Begin
Сложность этого алгоритма О (А), так как тело цикла выполняется А раз, и сложность тела цикла равна 0(1). Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью.
For /: = 1 to N do For j: = 1 to N do Begin
Сложность этой программы 0(N 2).
Пример 1. Оценим сложность программы, вводящей с клавиатуры массив и находящей в нем наибольший элемент. Алгоритм состоит из следующих шагов:
- - ввод массива (надо прочесть А элементов);
- - поиск наибольшего элемента (надо сделать А - 1 сравнение);
- - вывод результата (надо вывести одно число или строку).
Сложим число операций А + (А - 1) + 1 = 2А, т.е. существует
такая константа, что при любом А число операций не превышает СА. Следовательно, сложность алгоритма равна 0(A).
Пример 2. Оценим сложность программы, вводящей с клавиатуры массив и находящей в нем элемент с заданным свойством (например, равный определенному значению). Алгоритм состоит из следующих шагов:
- - ввод массива (Аопераций ввода);
- - поиск элемента с заданным свойством (элемент может находиться как ближе к началу массива, так и в самом конце; если элемента не существует, то необходимо сделать все А сравнений, чтобы в этом убедиться);
- - вывод результата.
В лучшем случае указанный алгоритм потребует А + 2 операции (ввод всего массива, единственное сравнение, вывод), в худшем (когда такого элемента нет, 2А + 1 операцию). Если А будет большим числом, к примеру порядка 10 6 , то единицей можно пренебречь. Следовательно, сложность алгоритма равна 0(N).
Пример 3. Определим функцию сложности алгоритма шифрования слова длиной L методом подстановки. Пусть существует таблица, в которой для каждого символа алфавита записан символ, на который его надо заменить. Обозначим число букв алфавита S. Алгоритм состоит из следующих шагов:
- - ввод слова (одна операция);
- - организация цикла:
- 1) для каждого символа найти его замену в таблице (если таблица не упорядочена и не обладает какими-нибудь свойствами, облегчающими поиск, то в худшем случае потребуется S операций для одного символа, если искомый элемент находится в самом конце);
- 2) вывод найденного символа;
- - конец цикла.
Общее число операций 1 + (S +)L. В случае достаточно больших S и L единицами можно пренебречь, и получится, что функция сложности приведенного алгоритма есть O(S L).
Пример 4. Определим функцию сложности алгоритма перевода натурального числа 1 V в двоичную систему счисления (без операций ввода и вывода данных). Алгоритм состоит из следующих шагов:
- - цикл, пока результат деления числа на 2 не станет равным 0:
- - разделить число на 2 и запомнить остаток;
- - принять результат деления за новое число;
- - конец цикла.
Общее число операций не превышает 1 + log 2 A. Поэтому описанный алгоритм имеет сложность 0(og 2 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:
Часто бывает, что на время работы одного и того же алгоритма кроме размера задачи влияют другие параметры, вводимые пользователем.
В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма.
Трудоемкость" 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 можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.
Привет! Сегодняшняя лекция будет немного отличаться от остальных. Отличаться она будет тем, что имеет лишь косвенное отношение к Java. Тем не менее, эта тема очень важна для каждого программиста. Мы поговорим об алгоритмах . Что такое алгоритм? Говоря простым языком, это некоторая последовательность действий, которые необходимо совершить для достижения нужного результата . Мы часто используем алгоритмы в повседневной жизни. Например, каждое утро перед тобой стоит задача: прийти на учебу или работу, и быть при этом:
- Одетым
- Чистым
- Сытым
- Проснуться по будильнику.
- Принять душ, умыться.
- Приготовить завтрак, сварить кофе/заварить чай.
- Поесть.
- Если не погладил одежду с вечера - погладить.
- Одеться.
- Выйти из дома.
- Купить или скачать в Интернете “Словарь русских личных имен” 1966 года издания.
- Находить каждое имя из нашего списка в этом словаре.
- Записывать на бумажку, на какой странице словаря находится имя.
- Расставить имена по порядку, используя записи на бумажке.
В этом случае, самым эффективным алгоритмом будет передать файл через Интернет. Это займет максимум пару минут!
Итак, давай еще раз озвучим наш алгоритм:
“Если требуется передать информацию в виде файлов на расстояние 5000 километров, нужно использовать передачу данных через Интернет”.
Отлично. Теперь давай проанализируем его.
Решает ли он нашу задачу?
В общем-то да, вполне решает.
А вот что можно сказать насчет его сложности?
Хм, а вот тут уже все интереснее. Дело в том, что наш алгоритм очень сильно зависит от входящих данных, а именно - от размера файлов.
Сейчас у нас 10 мегабайт, и все в порядке.
А что, если нам нужно будет передать 500 мегабайт?
20 гигабайт?
500 терабайт?
30 петабайт?
Перестанет ли наш алгоритм работать? Нет, все эти объемы данных все равно можно передать.
Станет ли он выполняться дольше?
Да, станет!
Теперь нам известна важная особенность нашего алгоритма: чем больше размер данных для передачи, тем дольше времени займет выполнение алгоритма
.
Но нам хотелось бы более точно понимать, как выглядит эта зависимость (между размером данных и временем на их передачу).
В нашем случае сложность алгоритма будет линейной
.
“Линейная” означает, что при увеличении объема данных время на их передачу вырастет примерно пропорционально. Если данных станет в 2 раза больше, и времени на их передачу понадобится в 2 раза больше. Если данных станет больше в 10 раз, и время передачи увеличится в 10 раз.
Используя обозначение Big-O, сложность нашего алгоритма определяется как O(N)
. Это обозначение лучше всего запомнить на будущее - оно всегда используется для алгоритмов с линейной сложностью.
Обрати внимание: мы вообще не говорим здесь о разных “переменных” вещах: скорости интернета, мощности нашего компьютера и так далее. При оценке сложности алгоритма в этом просто нет смысла - мы в любом случае не можем это контролировать. Big-O оценивает именно сам алгоритм, независимо от “окружающей среды” в которой ему придется работать.
Продолжим работать с нашим примером. Допустим, в итоге выяснилось, что размер файлов для передачи составляет 800 терабайт.
Если мы будем передавать их через Интернет, задача, конечно, будет решена. Есть только одна проблема: передача по стандартному современному каналу (со скоростью 100 мегабит в секунду), который используется дома у большинства из нас, займет примерно 708 дней.
Почти 2 года! :O
Так, наш алгоритм тут явно не подходит. Нужно какое-то другое решение!
Неожиданно на помощь к нам приходит IT-гигант - компания Amazon! Ее сервис Amazon Snowmobile позволяет загрузить большой объем данных в передвижные хранилища и доставить по нужному адресу на грузовике!
Итак, у нас есть новый алгоритм!
“Если требуется передать информацию в виде файлов на расстояние 5000 километров и этот процесс займет больше 14 дней при передаче через Интернет, нужно использовать перевозку данных на грузовике Amazon”.
Цифра 14 дней здесь выбрана случайно: допустим, это максимальный срок, который мы можем себе позволить.
Давай проанализируем наш алгоритм. Что насчет скорости? Даже если грузовик поедет со скоростью всего 50 км/ч, он преодолеет 5000 километров всего за 100 часов. Это чуть больше четырех дней! Это намного лучше, чем вариант с передачей по интернету.
А что со сложностью этого алгоритма? Будет ли она тоже линейной, O(N)?
Нет, не будет. Ведь грузовику без разницы, как сильно ты его нагрузишь - он все равно поедет примерно с одной и той же скоростью и приедет в срок.
Будет ли у нас 800 терабайт, или в 10 раз больше данных, грузовик все равно доедет до места за 5 дней.
Иными словами, у алгоритма доставки данных через грузовик постоянная сложность
. “Постоянная” означает, что она не зависит от передаваемых в алгоритм данных.
Положи в грузовик флешку на 1Гб - он доедет за 5 дней. Положи туда диски с 800 терабайтами данных - он доедет за 5 дней.
При использовании Big-O постоянная сложность обозначается как O(1)
.
Раз уж мы познакомились с O(N)
и O(1)
, давай теперь рассмотрим более “программистские” примеры:)
Допустим, тебе дан массив из 100 чисел, и задача - вывести в консоль каждое из них.
Ты пишешь обычный цикл for , который выполняет эту задачу
int
numbers =
new
int
[
100
]
;
// ..заполняем массив числами
for
(int
i:
numbers)
{
System.
out.
println
(i)
;
}
Какая сложность у написанного алгоритма? Линейная, O(N).
Число действий, которые должна совершить программа, зависит от того, сколько именно чисел в нее передали.
Если в массиве будет 100 чисел, действий (выводов на экран) будет 100. Если чисел в массиве будет 10000, нужно будет совершить 10000 действий.
Можно ли улучшить наш алгоритм? Нет.
Нам в любом случае придется совершить N проходов по массиву
и выполнить N выводов в консоль.
Рассмотрим другой пример.
public
static
void
main
(String
args)
{
LinkedList<
Integer>
numbers =
new
LinkedList
<
>
()
;
numbers.
add
(0
,
20202
)
;
numbers.
add
(0
,
123
)
;
numbers.
add
(0
,
8283
)
;
}
У нас есть пустой LinkedList , в который мы вставляем несколько чисел. Нам нужно оценить сложность алгоритма вставки одного числа в LinkedList в нашем примере, и как она зависит от числа элементов, находящихся в списке.
Ответом будет O(1) - постоянная сложность
. Почему?
Обрати внимание: каждый раз мы вставляем число в начало списка. К тому же, как ты помнишь, при вставке числа в LinkedList элементы никуда не сдвигаются - происходит переопределение ссылок (если вдруг забыл, как работает LinkedList, загляни в одну из наших ).
Если сейчас первое число в нашем списке - число х, а мы вставляем в начало списка число y, все, что для этого нужно:
x.
previous =
y;
y.
previous =
null;
y.
next =
x;
Для этого переопределения ссылок нам неважно, сколько чисел сейчас в LinkedList
- хоть одно, хоть миллиард.
Сложность алгоритма будет постоянной - O(1).
Логарифмическая сложность
Без паники! :) Если при слове “логарифмический” тебе захотелось закрыть лекцию и не читать дальше - подожди пару минут. Никаких математических сложностей здесь не будет (таких объяснений полно и в других местах), а все примеры разберем “на пальцах”. Представь, что твоя задача - найти одно конкретное число в массиве из 100 чисел. Точнее, проверить, есть ли оно там вообще. Как только нужное число найдено, поиск нужно прекратить, а в консоль вывести запись “Нужное число обнаружено! Его индекс в массиве = ....” Как бы ты решил такую задачу? Здесь решение очевидно: нужно перебрать элементы массива по очереди начиная с первого (или с последнего) и проверять, совпадает ли текущее число с искомым. Соответственно, количество действий прямо зависит от числа элементов в массиве. Если у нас 100 чисел, значит, нам нужно 100 раз перейти к следующему элементу и 100 раз проверить число на совпадение. Если чисел будет 1000, значит и шагов-проверок будет 1000. Это очевидно линейная сложность, O(N) . А теперь мы добавим в наш пример одно уточнение: массив, в котором тебе нужно найти число, отсортирован по возрастанию . Меняет ли это что-то для нашей задачи? Мы по-прежнему можем искать нужное число перебором. Но вместо этого мы можем использовать известный алгоритм двоичного поиска .
В верхнем ряду на изображении мы видим отсортированный массив. В нем нам необходимо найти число 23.
Вместо того, чтобы перебирать числа, мы просто делим массив на 2 части и проверяем среднее число в массиве.
Находим число, которое располагается в ячейке 4 и проверяем его (второй ряд на картинке).
Это число равно 16, а мы ищем 23. Текущее число меньше. Что это означает? Что все предыдущие числа (которые расположены до числа 16) можно не проверять
: они точно будут меньше того, которое мы ищем, ведь наш массив отсортирован!
Продолжим поиск среди оставшихся 5 элементов.
Обрати внимание: мы сделали всего одну проверку, но уже отмели половину возможных вариантов.
У нас осталось всего 5 элементов. Мы повторим наш шаг - снова разделим оставшийся массив на 2 и снова возьмем средний элемент (строка 3 на рисунке). Это число 56, и оно больше того, которое мы ищем.
Что это означает? Что мы отметаем еще 3 варианта - само число 56, и два числа после него (они точно больше 23, ведь массив отсортирован).
У нас осталось всего 2 числа для проверки (последний ряд на рисунке) - числа с индексами массива 5 и 6.
Проверяем первое из них, и это то что мы искали - число 23! Его индекс = 5!
Давай рассмотрим результаты работы нашего алгоритма, а потом разберемся с его сложностью. (Кстати, теперь ты понимаешь, почему его называют двоичным: его суть заключается в постоянном делении данных на 2).
Результат впечатляет! Если бы мы искали нужное число линейным поиском, нам понадобилось бы 10 проверок, а с двоичным поиском мы уложились в 3!
В худшем случае их было бы 4, если бы на последнем шаге нужным нам числом оказалось второе, а не первое.
А что с его сложностью? Это очень интересный момент:)
Алгоритм двоичного поиска гораздо меньше зависит от числа элементов в массиве, чем алгоритм линейного поиска (то есть, простого перебора).
При 10
элементах в массиве линейному поиску понадобится максимум 10 проверок, а двоичному - максимум 4 проверки. Разница в 2,5 раза.
Но для массива в 1000 элементов
линейному поиску понадобится 1000 проверок, а двоичному - всего 10
! Разница уже в 100 раз!
Обрати внимание: число элементов в массиве увеличилось в 100 раз (с 10 до 1000), а количество необходимых проверок для двоичного поиска увеличилось всего в 2,5 раза - с 4 до 10.
Если мы дойдем до 10000 элементов
, разница будет еще более впечатляющей: 10000 проверок для линейного поиска, и всего 14 проверок
для двоичного.
И снова: число элементов увеличилось в 1000 раз (с 10 до 10000), а число проверок увеличилось всего в 3,5 раза (с 4 до 14).
Сложность алгоритма двоичного поиска логарифмическая
, или,если использовать обозначения Big-O, - O(log n)
. Почему она так называется?
Логарифм - это такая штуковина, обратная возведению в степень. Двоичный логарифм использует для подсчета степени числа 2.
Вот, например, у нас есть 10000 элементов, которые нам надо перебрать двоичным поиском.
Сейчас у тебя есть картинка перед глазами, и ты знаешь что для этого нужно максимум 14 проверок. Но что если картинки перед глазами не будет, а тебе нужно посчитать точное число необходимых проверок?
Достаточно ответить на простой вопрос: в какую степень надо возвести число 2, чтобы полученный результат был >= числу проверяемых элементов?
Для 10000 это будет 14 степень.
2 в 13 степени - это слишком мало (8192)
А вот 2 в 14 степени = 16384
, это число удовлетворяет нашему условию (оно >= числу элементов в массиве).
Мы нашли логарифм - 14. Столько проверок нам и нужно! :)
Алгоритмы и их сложность - тема слишком обширная, чтобы вместить ее в одну лекцию.
Но знать ее очень важно: на многих собеседованиях ты получишь алгоритмические задачи.
Для теории я могу порекомендовать тебе несколько книг.
Начать можно с “видео про Big-O на YouTube.
Увидимся на следующих лекциях! :)