Меню
ГлавнаяТелефон

Временная сложность алгоритма. Оценка сложности алгоритмов, или Что такое О(log n)

Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.
Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

Оценка порядка

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A находит максимальный элемент в каждой строке.
for i:=1 to N do
begin
max:=A;
for j:=1 to N do
begin
if A>max then
max:=A
end;
writeln(max);
end;
В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2).
Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.
Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2)*O(N^3)=O(N^5).
Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2)+O(N^3)=O(N^3). Следующий фрагмент имеет именно такую сложность:
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
{какое-то действие}
end;
procedure Both;
begin
Fast;
Slow;
end;
Сложность рекурсивных алгоритмов
Простая рекурсия
Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.
Рассмотрим рекурсивную реализацию вычисления факториала:
function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).
Многократная рекурсия
Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.
Рассмотрим такую процедуру:
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.
Объёмная сложность рекурсивных алгоритмов
Для всех рекурсивных алгоритмов очень важно понятие объёмной сложности. При каждом вызове процедура запрашивает небольшой объём памяти, но этот объём может значительно увеличиваться в процессе рекурсивных вызовов. По этой причине всегда необходимо проводить хотя бы поверхностный анализ объёмной сложности рекурсивных процедур.
Средний и наихудший случай
Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.
function Locate(data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl:=false; i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true
else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.
С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).
Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).
В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.
Общие функции оценки сложности
Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.
1. C – константа
2. log(log(N))
3. log(N)
4. N^C, 0 5. N
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.

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

Время работы алгоритма удобно выражать в виде функции от одной переменной, характеризующей «размер» конкретной задачи, т.е. объем входных данных, необходимых для ее решения. Такой подход удобен, поскольку сравнительная сложность задач может оцениваться через ее размер. Поскольку описание задачи, предназначенной для решения посредством вычислительного устройства, можно рассматривать в виде слова конечной длины, представленной символами конечного алфавита, в качестве формальной характеристики размера задачи можно принять длину входного слова. Например, если стоит задача определения максимального числа в некоторой последовательности из n элементов, то и размер задачи будет n , поскольку любой вариант входной последовательности можно задать словом из п символов.

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

При этом, безусловно, предполагается, что во всех задачах используется одинаковая схема кодирования входных слов.

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

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

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

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

Из приведенных данных видно, что, во-первых, время обработки экспоненциальных алгоритмов при одинаковых размерах задач (превышающих 20) намного выше, чем у полиномиальных; во-вторых, скорость нарастания времени обработки с увеличением размера задачи у экспоненциальных алгоритмов значительно выше, чем у полиномиальных.

Различие между обоими типами алгоритмов проявляются еще более убедительно, если проанализировать влияние увеличения быстродействия компьютера на время исполнения алгоритма. В табл. 7.3 показано, насколько возрастают размеры наибольшей задачи, решаемой за единицу машинного времени, если быстродействие компьютера вырастет в 100 и 1000 раз.

Из табл. 7.3 видно, что, например, для экспоненциального алгоритма с функцией сложности f(n) = 2 n рост скорости вычислений в 1000 раз приводит лишь к тому, что размер наибольшей задачи возрастает всего на 10 единиц, в то время как для функции f(n) = п 5 она возрастает почти в 4 раза.

Таблица 7.2.

Таблица 7.3.

Приведенные примеры призваны показать, что подобно тому, как существуют алгоритмически неразрешимые задачи, существуют и задачи объективно сложные, т.е. такие, трудоемкость которых невозможно уменьшить совершенствованием компьютера. Задача считается труднорешаемой, если для нее не удается построить полиномиального алгоритма. Это утверждение не является категорическим, поскольку известны задачи, в которых достаточно эффективно работают и экспоненциальные алгоритмы. Примером может служить симплекс-метод, который успешно используется при решении задач линейного программирования, имея функцию сложности f(n) = 2 n . Однако подобных примеров не очень много, и общей следует признать ситуацию, что эффективно исполняемыми можно считать полиномиальные алгоритмы с функциями сложности п, n 2 или п 3 . Например, при решении задачи поиска нужного данного из п имеющихся в худшем варианте сложность равна п ; если же оценить среднюю трудоемкость (продолжительность поиска), то она составит (п + 1)/2 - в обоих случаях функция сложности оказывается линейной п. Задача ранжирования, т.е. расстановки в заданном порядке п однотипных данных приводит к полиному 2-й степени; сложность задачи вычисления определителя системы п линейных уравнений с п неизвестными характеризуется полиномом 3-й степени. Повышение быстродействия элементов компьютера уменьшает время исполнения алгоритма, но не уменьшает степень полинома сложности. Следовательно, решению практической задачи на компьютере должна предшествовать оценка ее сложности и доказательство того, что задача решаема за приемлемое время.

Обозначение Интуитивное объяснение Определение
f ограничена сверху функцией g src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
f ограничена снизу и сверху функцией g асимптотически 0), n_0: \forall (n>n_0) \; |Cg(n)|
g доминирует над f асимптотически src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
f доминирует над g асимптотически src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
f эквивалентна g асимптотически

Примеры

Замечания

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

Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом - порядка n+n!/C, где C - постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй - нет, хотя, например, при С=10 (10 10) дело обстоит как раз наоборот.

  1. Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
  2. Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
  3. В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Классы сложности

Класс сложности - это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:

Класс P

Проблема равенства классов P и NP

Знаменитые ученые

  • Леонид Левин
  • Александр Разборов
  • Эди Шеймир

См. также

Ссылки

  • Юрий Лифшиц «Современные задачи теоретической информатики » . Курс лекций по алгоритмам для NP-трудных задач.
  • А. А. Разборов Theoretical Computer Science: взгляд математика // Компьютерра . - 2001. - № 2. (альтернативная ссылка)
  • А. А. Разборов О сложности вычислений // Математическое просвещение . - МЦНМО , 1999. - № 3. - С. 127-141.

Wikimedia Foundation . 2010 .

При проектировании алгоритмов, как правило, не представляет интереса точное число шагов, необходимых для решения задачи на конкретном наборе данных. Гораздо важнее знать, как будет изменяться время решения задачи T, если размер входа n растёт.

Класс алгоритмов, время работы которых растёт, по крайней мере, так же быстро, как некоторая функция f(n), обозначается как Ω(f(n)). Это означает, что при всех n, превышающих порог n 0 , T(n) ≥C . f(n) для некоторого положительного числаC. Оценка времени работы снизу может представлять интерес только как теоретическая нижняя граница эффективности любого алгоритма для некоторой задачи, которую преодолеть невозможно.

Класс алгоритмов, время работы которых растёт не быстрее функции f(n), обозначается O (f(n)), что означает существование положительных чисел n 0 и c таких, что при n > n 0 T(n) ≤C . f(n). Этот класс - важнейшая характеристика алгоритма, еговременная сложность . По скорости роста этого времени в зависимости от размера входа алгоритмы делятся на следующие классы временной сложности:

Алгоритмы константной сложности - T(n) ∈ O(1);

Логарифмической сложности - T(n) ∈ O(log n);

Линейной сложности - T(n) ∈ O(n);

Квадратичной сложности - T(n) ∈ O(n 2);

Кубической сложности - T(n) ∈ O(n 3);

Полиномиальной сложности - T(n) ∈ O(n k), где k = const; k = 0, 1, 2 или 3 - это частные случаи классов полиномиальной сложности;

Экспоненциальной сложности - T(n) ∈ O(a n).

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

Алгоритм, для которого оценки Ω(f(n) и O (f(n)) совпадают, называетсяоптимальным . Так, очевидно, что алгоритм, имеющий на входе некоторое множество, будет оптимальным, если его временная сложностьO (1). Такой алгоритм можно попытаться найти, если задача не требует рассмотреть множество целиком. Если же требуется что-то сделать с каждым элементом множества мощностью n, оптимальный алгоритм будет иметь сложностьO (n). Если имеется два множества, и нужно обработать все возможные пары их элементов, можно ожидать сложностиO (n 2), для трёх множеств, если обрабатываются все тройки -O (n 3), и т. д.

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

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

Для самого неудобного набора данных - сложность «в худшем случае»;

Для типового набора данных - сложность «в среднем».

Тривиальные входные данные («лучший случай») обычно интереса не представляют.

Для оценки временной сложности по реализации алгоритма (тексту программы) можно руководствоваться следующими соображениями:

Операции присваивания (копирования) и проверки условия для базовых типов данных выполняются за константное время. Если при этом вызывается функция, сложность шага алгоритма определяется сложностью функции (в операциях с объектами функции могут вызываться неявно);

Сложность алгоритма, состоящего из последовательности шагов, определяется по самому сложному шагу;

Сложность выбора по условию определяется по самой сложной из альтернатив. В порядке исключения можно не принимать во внимание альтернативы, выбираемые очень редко. Можно учесть такие альтернативы, как «худший случай»;

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

Рекурсия рассматривается как тот же цикл. Её сложность определяется как произведение сложности одного вызова функции на количество вызовов.

Пример 1. Вычислить b = (a∈A), где множество A мощностью nA представлено массивом целых чисел.

Решение : b = false; for (i = 0; !b && (i < nA); i++) b |= (a == A[i]);

Временная сложность алгоритма - O (nA). Если элемент a найден, алгоритм прекращает работу, выполнив от 1 до nA шагов. В среднем количество шагов будет nA / 2, в худшем случае (a∉A) - nA.

Пример 2. Вычислить C = A⋂B для множеств, представленных неупорядоченными массивами.

Решение : проверяем все возможные пары элементов двух множеств и отбираем совпадения.

for (i = k = 0; i < nA; i++)

for (j = 0; j < nB; j++) if (A[ i ] == B[ j ]) C[ k++ ] = A[ i ];

Проверка на совпадение и присваивание выполняются за константное время, поэтому сложность алгоритма - O (nA × nB), илиO (n 2), где n - средняя мощность множеств.

Пример 3. Вычислить D = A⋂ B⋂ C.

Очевидное решение

for (i = k = 0; i < nA; i++)

for (j = 0; j < nB; j++)

for (r = 0; r

if ((A[ i ] == B[ j ]) && (A[ i ] == C[ r ])) D[ k++ ] = A[ i ];

имеет временную сложность O (n 3), поскольку перебираются все возможные тройки. Однако перебирать все тройки никакой необходимости нет.

Модифицируем алгоритм:

for(i=k= 0;i

for (j = 0; j < nB; j++)

if (A[i] == B[j]) for (r = 0; r

if (A[i] == C[r]) D = A[i];

В алгоритме по-прежнему три вложенных цикла, но внутренний цикл теперь зависит от условия A[ i ] == B[ j ], которое проверяется n 2 раз, но удовлетворяется не более чем n раз, т. е. рассматриваются только такие тройки, у которых первые два элемента совпадают. Проверка A[i] == C[r] выполняется, таким образом, не более n 2 раз, и общая сложность алгоритма - O (n 2).

Пример 4. Вычислить C = A⋂B для множеств, представленных строками символов.

Решение :

for(i = k = 0; i < strlen(A); i++)

for (j = 0; j < strlen(B); j++) if (A[ i ] == B[ j ]) C[ k++ ] = A[ i ];

По аналогии с примером 2 можно оценить сложность как O (n 2). Однако это неверно, так как в обоих циклах по n раз вычисляется функция определения длины строки strlen(), которая, очевидно, подсчитывает в строке количество символов до ближайшего нуля перебором, т. е. имеет линейную сложность. Вычисление этой функции - один из шагов внутренней части обоих циклов. Таким образом, внутренняя часть вложенного цикла состоит из трёх шагов, двух константных (проверка и присваивание) и линейного (вычисление функции). С учётом n повторений сложность всего цикла -O (n 2). Внешний цикл добавляет сюда ещё шаг вычисления функции сложностьюO (n). Сложность его внутренней части -O (n 2), а всего алгоритма -O (n 3)! Это - цена экономии двух целых переменных. На самом деле нужно вычислить nA = strlen(A); nB = strlen(B), а затем использовать алгоритм из примера 2.

Редактор Г. Г. Петров

Подписано в печать. Формат 60×84 1/16.

Бумага офсетная. Печать офсетная. Печ. л. 4,0.

Гарнитура «Times». Тираж экз. Заказ

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Издательство СПбГЭТУ «ЛЭТИ»

Также как из другими "навскидку" оценками (основанными на интуиции), суть в уже усвоенном опыте: в доступности строительных блоков, которыми вы можете оперировать бессознательно в выбранной области, благодаря целенаправленной практике.

Большинство кода имеет простую алгоритмическую структуру. И если знать оценку для распространённых блоков (алгоритмов и операций над структурами данных в вашей области), то сложность кода очевидна. В C++ сложность для стандартных алгоритмов явно указана. Знание только к какой из трёх категорий ввод относится (случайный доступ/ RandomAccessIterator, последовательный/ForwardIterator, однопроходной/InputIterator) уже достаточно во многих случаях, чтобы оценить сложность алгоритма.

Можно даже не знать как что-то конкретно реализовано. К примеру, если алгоритм на каком-то шаге требует сортировки случайных данных, то разумно предположить O(n log n) для алгоритма, основанного на сравнениях, вне зависимости от конкретной реализации. Или при поиске в таблице в базе данных, если строк много (когда о big O имеет смысл говорить), можно ожидать что добротная реализация индекс создаст (поиск из O(n) в O(log n) превращается). В случае сомнений, можно измерить .

Чтобы найти или проверить интуитивный ответ, можно рекуррентные выражения или частичные суммы построить, которые с помощью компьютера вычислить. Так как есть O(c*n) == O(n) и O(n*n + n) == O(n*n) и другие упрощающие преобразования, то многие алгоритмы можно свести к небольшому числу базовых случаев. Процесс требует внимательности, но достаточно прямолинеен (особенно если задействовать что-нибудь вроде wolframalpha, Maple, Maxima, sympy). How to find time complexity of an algorithm .

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

Посмотрите какие алгоритмы используются в задачах, которые вам интересны. Новые алгоритмы с лучшей сложностью не каждый день появляются.

Начните с самого простого кода на вашем языке, framework и узнайте его сложность (к примеру, "удаление по индексу элемента из массива"). Зная сложность для элементарных конструкций, найдите сложность для блоков кода (составленных из этих конструкций), с которыми вы часто встречаетесь.

Можно в обратную сторону: начать с более высокоуровневого кода и постепенно спускаться ниже по уровням абстракции, пока до известных блоков не дойдёте (сложение фиксированных чисел, которые в машинном слове помещаются: O(1). Если произвольное число n взять, то O(log n) - пропорционально количеству бит в числе). См. таблицу сложностей по времени .

Практикуйтесь, пока большинство повседневного интересного вам кода не сможете навскидку оценить.