Для сравнения алгоритмов принято использовать обобщенную характеристику, называемую эффективностью. Говорят, что алгоритм Л, эффективнее алгоритма А 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). Итоговая сложность алгоритма имеет порядок

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

Наверняка вы не раз сталкивались с обозначениями вроде 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) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.

Глава 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 можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.

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

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

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

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

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

Задача 5.4 линейную сложность .

Вот решение этой задачи, в котором переменные j и k содержат значения двух последовательных чисел Фибоначчи.

Текст программы

public class FibIv1 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> < 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m > 0) { k = j; j += i; i = k; } Xterm.println(" = " + j); } } }

Следующий вопрос вполне естественен - а можно ли находить числа Фибоначчи еще быстрее?

После изучения определенных разделов математики совсем просто вывести следующую формулу для -ого числа Фибоначчи , которую легко проверить для небольших значений :

Может показаться, что основываясь на ней, легко написать программу со сложностью , не использующую итерации или рекурсии.

Текст программы

public class FibIv2 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5); Xterm.println("f(" + n + ") = " + j); } }

На самом деле эта программа использует вызов функции возведения в степень { Math.pow(f,n) }, которая не может быть реализована быстрее, чем за логарифмическое время (). Про алгоритмы, в которых количество операций примерно пропорционально (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность ().

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

Задача 5.5 . Напишите программу, печатающую -ое число Фибоначчи , которая имела бы логарифмическую сложность .

Текст программы

public class FibIv3 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> "); Xterm.print("f(" + n + ")"); if (n < 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) { if ((n&1) == 0) { n >>>= 1; c.square(); } else { n -= 1; b.mul(c); } } Xterm.println(" = " + b.fib()); } } } class Matrix { private long a, b, c, d; public Matrix(long a, long b, long c, long d) { this.a = a; this.b = b; this.c = c; this.d = d; } public void mul(Matrix m) { long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+d*m.c; long d1 = c*m.b+d*m.d; a = a1; b = b1; c = c1; d = d1; } public void square() { mul(this); } public long fib() { return b; } }

Если попробовать посчитать десятимиллионное число Фибоначчи с помощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности диапазона чисел типа long .

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

Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности , , и соответственно. Предположим, что второй из этих алгоритмов требует для своего выполнения на некотором компьютере при значении параметра ровно одну минуту времени. Тогда времена выполнения всех этих четырех алгоритмов на том же компьютере при различных значениях параметра будут примерно такими, как в 10 300000 лет

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

С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлемое время. Таким образом, увеличивается среднее значение величины , и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма !

Привет! Сегодняшняя лекция будет немного отличаться от остальных. Отличаться она будет тем, что имеет лишь косвенное отношение к Java. Тем не менее, эта тема очень важна для каждого программиста. Мы поговорим об алгоритмах . Что такое алгоритм? Говоря простым языком, это некоторая последовательность действий, которые необходимо совершить для достижения нужного результата . Мы часто используем алгоритмы в повседневной жизни. Например, каждое утро перед тобой стоит задача: прийти на учебу или работу, и быть при этом:

• Одетым
• Чистым
• Сытым

Какой алгоритм позволит тебе добиться этого результата?

1. Проснуться по будильнику.
2. Принять душ, умыться.
3. Приготовить завтрак, сварить кофе/заварить чай.
4. Поесть.
5. Если не погладил одежду с вечера - погладить.
6. Одеться.
7. Выйти из дома.

Эта последовательность действий точно позволит тебе получить необходимый результат. В программировании вся суть нашей работы заключается в постоянном решении задач. Значительную часть этих задач можно выполнить, используя уже известные алгоритмы. К примеру, перед тобой стоит задача: отсортировать список из 100 имен в массиве . Задача это довольно проста, но решить ее можно разными способами. Вот один из вариантов решения: Алгоритм сортировки имен по алфавиту:

1. Купить или скачать в Интернете “Словарь русских личных имен” 1966 года издания.
2. Находить каждое имя из нашего списка в этом словаре.
3. Записывать на бумажку, на какой странице словаря находится имя.
4. Расставить имена по порядку, используя записи на бумажке.

Позволит ли такая последовательность действий решить нашу задачу? Да, вполне позволит. Будет ли это решение эффективным ? Вряд ли. Здесь мы подошли к еще одному очень важному свойству алгоритмов - их эффективности . Решить задачу можно разными способами. Но и в программировании, и в обычной жизни мы выбираем способ, который будет наиболее эффективным. Если твоя задача - сделать бутерброд со сливочным маслом, ты, конечно, можешь начать с того, что посеешь пшеницу и подоишь корову. Но это будет неэффективное решение - оно займет очень много времени и будет стоить много денег. Для решения твоей простой задачи хлеб и масло можно просто купить. А алгоритм с пшеницей и коровой хоть и позволяет решить задачу, слишком сложный, чтобы применять его на практике. Для оценки сложности алгоритмов в программировании создали специальное обозначение под названием Big-O (“большая О”) . Big-O позволяет оценить, насколько время выполнения алгоритма зависит от переданных в него данных . Давай рассмотрим самый простой пример - передачу данных. Представь, что тебе нужно передать некоторую информацию в виде файла на большое расстояние (например, 5000 километров). Какой алгоритм будет наиболее эффективным? Это зависит от тех данных, с которыми ему предстоит работать. К примеру, у нас есть аудиофайл размером 10 мегабайт.
В этом случае, самым эффективным алгоритмом будет передать файл через Интернет. Это займет максимум пару минут! Итак, давай еще раз озвучим наш алгоритм: “Если требуется передать информацию в виде файлов на расстояние 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. Увидимся на следующих лекциях! :)