Оценка сложности алгоритмов, или Что такое О(log n)
Если вы всё ещё не понимаете, что такое вычислительная сложность алгоритмов, и ждете простое и понятное объяснение, — эта статья для вас.
Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы хотите стать хорошим программистом, но так и не понимаете, что это значит, — данная статья для вас.
Оценка сложности
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.
Допустим, некоторому алгоритму нужно выполнить 4n3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n3) , т. е. зависит от размера входных данных кубически.
Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .
Примеры
O(n) — линейная сложность
Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
O(log n) — логарифмическая сложность
Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
O(n2) — квадратичная сложность
Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n2 .
Бывают и другие оценки по сложности, но все они основаны на том же принципе.
Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.
Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.
Наглядно
Время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при скорости 106 операций в секунду:
Тут можно посмотреть сложность основных алгоритмов сортировки и работы с данными.
Если хочется подробнее и сложнее, заглядывайте в нашу статью из серии «Алгоритмы и структуры данных для начинающих».
Следите за новыми постами по любимым темам
Подпишитесь на интересующие вас теги, чтобы следить за новыми постами и быть в курсе событий.
Теоретическая оценка вычислительной сложности алгоритма в среднем, лучшем и худшем случаях, оцените асимптотическую сложность
подскажите, пожалуйста, как оценить сложность этого алгоритма. Алгоритм заменяет нули на предыдущее не нулевое значение.
a = [3,1,4,0,0,0,0,0,5,0,4,0] b = [] for i in a: b.append(i if i else b[-1]) print (b) Я только третий день начала изучать питон, не очень понимаю.
Отслеживать
47.5k 17 17 золотых знаков 56 56 серебряных знаков 99 99 бронзовых знаков
задан 19 мая в 9:09
11 1 1 бронзовый знак
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Ваш вопрос к пайтону особо отношения не имеет. Это относится к теме о сложности алгоритмов. В данном случае у вас сложность О(n) — линейная сложность. Естественно, как определять сложность алгоритмов в рамках одного ответа, объяснить невозможно. Поэтому рекомендую почитать литературу или погуглить тему «Оценка сложности алгоритмов».
Отслеживать
ответ дан 19 мая в 9:17
1,537 2 2 золотых знака 4 4 серебряных знака 15 15 бронзовых знаков
Не совсем так. В зависимости от реализации list.append() сложность может меняться от линейной до квадратичной
19 мая в 9:27
Возможно, я не по пайтон, не в курсе как в пайтоне append реализовано, но подозреваю что реализовать должны были с линейной сложность по аналогии с остальными языками
19 мая в 9:34
@had0uken если у append линейная сложность, то в целом алгоритм будет иметь квадратичную сложность. Для python у append сложность примерно константная, «но не совсем» (при росте списка в какой-то момент возникнет необходимость перемещения его в больший блок памяти). В целом, если говорить про разные языки, то лучше не полагаться, что во всех языках сложность добавления элемента в конец константная.
19 мая в 10:30
Вот тут в исходниках есть пояснение, по какому принципу выполняется ресайз блока памяти списка (в том числе при append): github.com/python/cpython/blob/… . Я так сходу сложность с учетом необходимости перемещения данных не оценю, но она явно не константная, скорее линейная с довольно маленьким множителем, либо логарифмическая в лучшем случае. Нужно смотреть, по по какому принципу растет размер выделяемого блока, вроде бы не совсем линейно (4 — 8 — 16 — 24 в линию не ложатся).
Сложность алгоритмов
Для сравнения алгоритмов принято использовать обобщенную характеристику, называемую эффективностью. Говорят, что алгоритм Л, эффективнее алгоритма А2, если алгоритм Л, выполняется за меньшее время и (или) требует меньше компьютерных ресурсов (оперативной памяти, дискового пространства, сетевого трафика и т.п.).
Эффективный алгоритм должен удовлетворять требованиям приемлемого времени исполнения и разумной ресурсоемкое™, о чем уже упоминалось в параграфе 1.1. Совокупность этих характеристик составляет понятие сложности алгоритма. При увеличении времени исполнения алгоритма и (или) задействованных ресурсов сложность возрастает. Таким образом, понятия эффективности и сложности являются обратными один относительно другого.
Характеристика алгоритма, отражающая временные затраты на его реализацию, называется временной сложностью. Характеристика алгоритма, отражающая компьютерные ресурсные затраты на его реализацию, называется емкостной сложностью.
При количественной и качественной оценках алгоритма, связанных с определением сложности, используют два подхода — практический и теоретический.
Практический подход связан с реально выполняемыми алгоритмами на конкретных физических устройствах. Он характеризуется параметрами, которые можно измерить и зафиксировать. Временная сложность при таком подходе может выражаться во временных единицах (например, миллисекундах) или количестве тактов процессора, затрачиваемых на выполнение алгоритма. Емкостная сложность может выражается в битах (или других единицах измерения информации), минимальных аппаратных требованиях, необходимых для выполнения алгоритма, и пр.
Практическая оценка не является абсолютным показателем эффективности алгоритма. Количественные значения, получаемые при таком подходе, зависят от множества факторов, таких как:
- • технические характеристики компонент, составляющих вычислительную систему. Так, чем выше тактовая частота работы процессора, тем больше элементарных операций в единицу времени может быть выполнено;
- • характеристики программной среды (количество запущенных процессов, алгоритм работы планировщика заданий, особенностей работы операционной системы и т.д.);
- • выбранный язык программирования для реализации алгоритма. Программа, написанная на языке высокого уровня, скорее всего, будет выполняться медленнее и потребует больше ресурсов, нежели программа, написанная на низкоуровневых языках, имеющих непосредственный доступ к аппаратным ресурсам;
- • опыт программиста, реализовавшего алгоритм. Скорее всего, начинающий программист напишет менее эффективную программу, чем программист, имеющий опыт.
Таким образом, алгоритм, выполняемый в одной и той же вычислительной системе для одних и тех же входных данных, может иметь различные количественные оценки в различные моменты времени. Поэтому более важным оказывается теоретический подход к определению сложности.
Теоретическая сложность характеризует алгоритм без привязки к конкретному оборудованию, программному обеспечению и средствам реализации. В этом случае временная сложность выражается в количестве операций, тактах работы машины Тьюринга и т.д. Емкостная сложность определяется объемом данных (входных, промежуточных, выходных), числом задействованных ячеек на ленте машины Тыоринга и т.д.
При теоретическом подходе к оценке эффективности считается, что алгоритм выполняется на некотором идеализированном компьютере, для которого время выполнения каждого вида операций известно и постоянно. Также считается, что ресурсы такого компьютера бесконечны, поэтому емкостную сложность при теоретическом подходе обычно не определяют. В качестве временной характеристики сложности выбирают количество инструкций (операций), выполняемых на идеализированном компьютере.
Количественные оценки, получаемые при теоретическом подходе, также могут зависеть от ряда следующих факторов:
- • объем входных данных. Чем он больше, тем больше времени потребуется на выполнение алгоритма;
- • выбранный метод решения задачи. Например, для большого объема входных данных алгоритм быстрой сортировки эффективное, чем алгоритм пузырьковой сортировки, хотя и приводит к такому же результату.
Время выполнения алгоритма обычно зависит от объема входных данных (размер входа), под которым понимают размерность решаемой задачи. Так, при сортировке множества значений объем данных составляет количество элементов этого множества. При обработке строк объемом входных данных считается длина строки.
Пусть п — объем входных данных для некоторого алгоритма. Обозначим за Т(п) количество инструкций, выполняемых на идеализированном компьютере при исполнении алгоритма, причем оно определяется для «наихудшего случая», когда объем операций максимален.
Понятие «наихудшего случая» можно проиллюстрировать на примере. Пусть рассматривается алгоритм проверки наличия числового элемента в некотором множестве (массиве) чисел. Если это множество упорядочено по возрастанию, то, вообще говоря, нет смысла проверять элементы, расположенные после первого элемента, который больше искомого. В этом случае Т(п) п0 и имеет место неравенство Т(п) А + п 2 . Выбрав значения п0 = 0 и с = 5, для любого п > п0 имеем Т(п) = 2п А + п 2 4 , следовательно, Т(п) имеет порядок я 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(log2w), 0(nog2n). Иногда используются и другие основания логарифма;
- 4) полиномиальная сложность 0(я 2 ), 0(/г 3 ), 0(я 4 ). ;
- 5) экспоненциальная сложность 2 п , 3″.
При увеличении размера входа сложность каждого последующего типа функций растет быстрее, чем предыдущего (кроме 0(log2/?)). Для достаточно большого объема входных данных предпочтительнее использовать алгоритмы с меньшей сложностью.
При количественном подсчете сложности первоначально выбирают операцию или группу операций, которая значима для этого алгоритма (составляет его основу). В их качестве обычно выступают операции сравнения и арифметические операции. К операциям сравнения относят проверку значений двух величин (меньше, больше, равно, меньше или равно, больше или равно, не равно). Они считаются эквивалентными по времени выполнения. Арифметические операции, в свою очередь, делят на аддитивные и мультипликативные. К первым (часто называемым просто сложением) относят сложение, вычитание, уменьшение или уменьшение значения счетчика. Ко вторым (называемым просто умножением) относят умножение, деление, взятие остатка по модулю.
Операции сложения выполняются быстрее, чем операции умножения, поэтому алгоритмы с меньшим количеством умножений являются предпочтительными, даже если количество сложений растет пропорционально количеству уменьшения умножений.
Операции целочисленного умножения или деления па степень числа 2 относят к аддитивным операциям, так как при работе с ячейками памяти они сводятся к сдвигу, который эквивалентен операции сложения.
После выбора значимых операций они делятся на две категории:
- 1) операции, непосредственно влияющие на сложность алгоритма;
- 2) операции, составляющие «накладные расходы» при выполнении алгоритма (например, выделение памяти для хранения промежуточных данных).
Непосредственный подсчет или оценка количества выполняемых операций позволяет оценить Т(п).
Для оценки порядка сложности можно использовать анализ программного кода, реализующего алгоритм. При этом:
- • алгоритмы без циклов и рекурсивных вызовов имеют сложность порядка 0(1). Таким образом, операции присваивания, ввода и вывода данных, условные конструкции имеют константную сложность;
- • если две части программного кода имеют сложности 0(J(ri)) и 0(J2(n)), то последовательное выполнение имеет сложность
- • если тело цикла выполняется один раз для каждого элемента входных данных, то сложность выполнения цикла имеет порядок 0(п)0( 1) = 0(п);
- • порядок сложности выполнения вложенных циклов вычисляется по правилу произведения 0(Jx(n)f2(n)) = 0(/,(/?))- 0(J2(ri)). Если каждый из них имеет сложность порядка 0(п), выполнение вложенных циклов имеет сложность порядка 0(п 2 ).
Определить порядок сложности алгоритма программы на языке
Pascal, приведенного в листинге 1.2. Строки программы пронумерованы в виде комментариев (см. параграф 2.6).
for i:=l to n do
write(‘Введите элемент массива
с индексом ‘,i,’: ‘);
Readln(MyArray[i]);
for i:=l to n do
for j:=1 to n do
write(‘Введите элемент массива
с индексами ‘, i, ‘,’, j, ‘ : ‘ );
Readln(МуDArray[i,j]);
Строки 02, 05, 08, 11 не содержат исполняемых операторов, поэтому при определении порядка они не учитываются.
Строки 03 и 04 имеют порядок 0(1). Последовательное их выполнение имеет порядок 0(1) + 0(1) = 0(1). Аналогично, последовательное выполнение строк 09 и 10 имеет сложность 0(1).
Цикл в строках 01—05 имеет сложность порядка О(п), вложенные циклы в строках 06—11 — порядка 0(п 2 ). Итоговая сложность алгоритма имеет порядок
Оценка сложности алгоритма, как временной, так и ресурсной, позволяет определить максимальное и среднее время исполнения алгоритма. Это крайне важно при обработке больших массивов информации, особенно в задачах сортировки и поиска, рассмотренных далее.
Алгоритмы и их сложности
Если дана задача, как найти для ее решения эффективный алгоритм? А если алгоритм найден, как сравнить его с другими алгоритмами, решающими ту же задачу? Как оценить его качество? Вопросы такого рода интересуют и программистов, и тех, кто занимается теоретическим исследованием вычислений.
Для оценки алгоритмов существует много критериев. Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении входных данных. Нам хотелось бы связать с каждой конкретной задачей некоторое число, называемое ее размером, которое выражало бы меру количества входных данных. Например, размером задачи умножения матриц может быть наибольший размер матриц — сомножителей.
Время, затрачиваемое алгоритмом, как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью. Аналогично можно определить емкостную сложность и асимптотическую емкостную сложность.
Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера n за время c*n 2 , где c — некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n 2 ) (читается «порядка эн квадрат»).
Можно было бы подумать, что колоссальный рост скорости вычислений, вызванный появлением нынешнего поколения цифровых вычислительных машин, уменьшит значение эффективных алгоритмов. Однако происходит противоположное. Так как вычислительные машины работают все быстрее и быстрее, и мы можем решать большие по размеру задачи, именно сложность алгоритма определяет то увеличение размера задачи, которое можно достичь с увеличением скорости машины.
Допустим, у нас есть пять алгоритмов A1,A2,…,A5 со следующими временными сложностями:
| Алгоритм | Временная сложность |
| A1 | n |
| A2 | n*log(n) |
| A3 | n 2 |
| A4 | n 3 |
| A5 | 2 n |
Здесь временная сложность — это число единиц времени, требуемого для обработки входа размера n. Пусть единицей времени будет одна миллисекунда (1сек=1000 милисекунд). Тогда алгоритм A1 может обработать за одну секунду вход размера 1000, в то время как A5 — вход размера не более 9. В следующей таблице приведены размеры задач, которые можно решить за одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.
| Алгоритм | Временная сложность | Максимальный размер задачи | ||
| 1 сек | 1 мин | 1 час | ||
| A1 | n | 1000 | 6*10 4 | 3,6*10 6 |
| A2 | n*log(n) | 140 | 4893 | 2*10 4 |
| A3 | n 2 | 31 | 244 | 1897 |
| A4 | n 3 | 10 | 39 | 153 |
| A5 | 2 n | 9 | 15 | 21 |
Предположим, что следующее поколение вычислительных машин будет в 10 раз быстрее нынешнего. В следующей таблице показано, как возрастут размеры задач, которые мы сможем решить благодаря этому увеличению скорости. Заметим, что для алгоритма A5 десятикратное увеличение скорости увеличивает размер задачи, которую можно решить, только на три единицы (см. последнюю строку в таб.), тогда как для алгоритма A3 размер задачи более чем утраивается.
| Алгоритм | Временная сложность | Максимальный размер задачи | |
| до ускорения | после ускорения | ||
| A1 | n | S1 | 10 S1 |
| A2 | n*log(n) | S2 | Примерно 10 S2 для больших S2. |
| A3 | n 2 | S3 | 3,165 S3 |
| A4 | n 3 | S4 | 2,155 S4 |
| A5 | 2 n | S5 | S5+3,3 |
Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более действенного алгоритма. Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм A4 алгоритмом A3, можно решить задачу, в 6 раз большую, а заменяя A4 на A2, можно решить задачу, большую в 125 раз. Эти результаты производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая сложность алгоритма служит важной мерой качественности алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений.
Несмотря на то что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную постоянную (постоянная c в определении О(f(x))), чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером — возможно, даже для всех задач, которые нас интересуют. Например, предположим, что временные сложности алгоритмов A1, A2, A3, A4, A5 в действительности равны соответственно 1000n, 100n*log(n), 10n 2 , n 3 и 2 n . Тогда A5 будет наилучшим для задач размера 2≤n≤9, A2 — для задач размера 10≤n≤58, A1 — при 59≤n≤1024, а A1 — при n>1024.