10. Трудоемкость алгоритмов

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

Рассмотрим наглядный пример. Пусть требуется найти кратчайший путь на графе из 30 вершин, в котором каждая вершина связана со всеми другими. Как известно из начальной части курса [8], для решения этой задачи часто используют алгоритм Дейкстры, трудоемкость которого пропорциональна N², где N – количество вершин графа. В математике для этого случая принято обозначение O(N²).

Попробуем найти кратчайший путь перебором всевозможных путей, что проще всего реализуется поиском в глубину. Ограничимся для простоты только путями, включающими все вершины графа. Поскольку в промежутке между начальной и конечной вершинами могут в различном порядке находиться 28 вершин, то таких путей 28! Эта величина превышает 10²⁹. Будем считать, что мы в состоянии находить и оценивать 10⁹ путей в секунду (реально значительно меньше). Значит, нам потребуется 10²⁰ секунд для просмотра всех путей. В сутках менее 10⁵ секунд, а в году менее 500 суток, то есть поиск займет более 210¹² лет. И это при том, что мы рассматривали только самые длинные по числу вершин пути! Нас не спасет даже компьютер, работающий в 1000 раз быстрее.

Можно возразить, что кратчайший путь не должен включать так много промежуточных вершин. Но термин "длина” в задачах поиска путей на графе используется в обобщенном смысле. Например, речь может идти о стоимости самолетных сообщений. Легко вообразить, что перелеты на короткое расстояние совершают маленькие самолеты, билеты на которые обходятся дешевле.

В первую очередь оценивают зависимость трудоемкости вычислений от размерности исходных данных N. Переборные алгоритмы имеют обычно экспоненциальную трудоемкость, то есть объем вычислений оценивается как O(Exp(N)). Такие алгоритмы реализуемы только при ограниченных значениях N. Полиномиальные алгоритмы имеют оценку O(N^P), где P>0.

Величина коэффициента пропорциональности отступает на второй план в тех случаях, когда размерность велика. Сравним, например, два алгоритма с трудоемкостью 0.1N² и 100N. При N < 1000 первый алгоритм эффективнее. Но при N = 10⁵ второй алгоритм в 100 раз быстрее первого.

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

Часто высокая скорость работы достигается путем использования рациональных структур данных. Так быстрый поиск информации в современных системах управления базами данных основан на Б-деревьях и хеш-таблицах.

Рассмотрим разные подходы к решению задач, которые существенно отличаются по трудоемкости.

Гомер Симпсон. Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M (1 ≤ M, N, T ≤ 2×10⁹). Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше. Выдать остаток обеденного времени.

Максимальное число гамбургеров составляет K = T div N, а чизбургеров L = T div M. Двойной цикл до K и L по трудоемкости вычислений нас устроить не может.

В [2] указан следующий простой выход. Если съедается I гамбургеров, то число чизбургеров определяется как J = (T - I × N) div M. Значит, достаточно одинарного цикла.

Но и такой подход не годится для заданной размерности. Пусть, например, M ≤  N. Очевидно, что максимальное суммарное число гамбургеров и чизбургеров составляет P = T div M. Как минимизировать остаток времени? Нужно вместо части гамбургеров съесть чизбургеры. Каждый из них потребует N - M из остатка времени. Значит, их можно съесть Q = (T - P × M) div (N - M). Тогда число гамбургеров уменьшится и составит P- Q.

Окраска чисел. Профессор Психовецкий решил покрасить все числа от 1 до N (1 ≤ N ≤10⁶ так, чтобы каждые два числа A и B имели разный цвет, если A делится на B. Каким минимальным количеством цветов можно обойтись?

Ввод. В единственной строке задано число N.

Вывод. В единственную строку вывести минимальное количество цветов.

Примеры

Ввод 1 Ввод 2 Ввод 3

3 5 12

Вывод 1 Вывод 2 Вывод 3

2 3 4

Можно решать задачу перебором, рассматривая по возрастанию возможные делители чисел до N включительно. Такой способ реализуется следующим образом.

Program Paint;

Const Max=1000000;

Var

M,N,i,j: longint;

Color: array [1..Max] of byte; {номера цветов}

Fin,Fout: text;

begin

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,N);

Close(Fin);

For i:=1 to N do Color[i]:=1; {инициализация}

M:=1; {число цветов и максимальный номер цвета}

For i:=2 to N do {i-число для окраски}

For j:=1 to i div 2 do {j-предполагаемый делитель}

if (i mod j = 0) and (Color[i]=Color[j]) then

begin

Color[i]:=Color[i]+1;

if Color[i]>M then M:=M+1;

end;

Assign(Fout,'output.txt');

Rewrite(Fout);

WriteLn(Fout,M);

Close(Fout);

End.

Метод имеет квадратичную трудоемкость, поэтому непригоден при больших значениях N. Опишем другой подход.

Греческому математику Эратосфену, жившему до нашей эры, принадлежит алгоритм нахождения простых чисел в заданном диапазоне. Из всех чисел последовательно удаляются те, которые делятся на 2, на 3 и т. д. В итоге остаются только простые числа. Такой способ называют методом «решета» [4].

Вот и нам в соответствии с этим методом более рационально перекрашивать последовательно все числа, имеющие общий делитель. Для этого достаточно переписать цикл окраски в следующем виде.

For j:=2 to N div i do {j-второй сомножитель}

Begin

k:=i*j;

if Color[k]=Color[i] then Color[k]:=Color[i]+1;

if Color[k]>M then M:=Color[k];

end;

Пусть две подпоследовательности имеют одинаковую длину и их первые k элементов (k ≥ 0) совпадают. Будем считать лучшей ту из них, у которой больше k+1-й элемент. Эта подпоследовательность более перспективна для дополнения ее меньшими элементами.

Снова начнем с обратного прохода от X_N к X₁, но в отличие от прежнего будем для каждого значения i искать лучшую подпоследовательность среди всех возрастающих подпоследовательностей, начинающихся с X_j при j ≥ i.

Опишем массив XBeg размерности N. Величина XBeg[i] определяет значение первого элемента, которым начинается лучшая подпоследовательность длины i.

Пусть L – текущая максимальная длина всех возрастающих подпоследовательностей. Тогда

XBeg[1] > XBeg[2] > ...> XBeg[L]

Действительно, если есть лучшая возрастающая подпоследовательность длины M, начинающаяся с некоторого элемента, то после удаления ее первого элемента получим лучшую подпоследовательность длины M – 1, начинающуюся с большего элемента.

Пусть XBeg[j+1] ≤ X_i < XBeg[j]. Это означает, что X_i может предшествовать лучшей подпоследовательности S_j длины j, но не может предшествовать лучшей подпоследовательности S_j+1 длины j+1. Тогда S_j с добавленным в начале X_i по крайней мере не хуже S_j+1, а первый элемент из S_j станет вторым после X_i в новой лучшей подпоследовательности длины j+1. Следовательно, нужно изменить XBeg[j+1] на X_i. Если j = L, то дополнительно увеличивается максимальная текущая длина L.

При обратном проходе будут находиться подпоследовательности все большей длины, поэтому индекс начального элемента лучшей подпоследовательности длины M меньше индекса начального элемента лучшей подпоследовательности длины M - 1. Поэтому после завершения обратного прохода лучшую возрастающую подпоследовательность составят элементы XBeg[L], XBeg[L-1], ..., XBeg[1].

Источником ускорения работы является бинарный поиск номера j для каждого X_i. Трудоемкость бинарного поиска оценивается величиной O(Log L). Поскольку L ≤ N, то общая трудоемкость алгоритма составляет O(Nlog N).

Приведем текст программы, реализующей описанный алгоритм. В отличие от [3], описанная модификация алгоритма позволяет обойтись единственным дополнительным массивом XBeg размерности N вместо трех массивов. Это позволяет в частности увеличить размерность N при реализации в Турбо Паскале даже по сравнению с первоначальным вариантом программы.

Const

R=100000;

{максимальный размер последовательности для Turbo Pascal

около 16000 на числах типа word}

Var

N: LongInt; {заданный размер последовательности}

i,j,Max: LongInt;

{Max - текущая длина наилучшей подпоследовательности}

X: array[1..R] of LongInt;

XBeg: array[1.. R] of LongInt;

{XBeg[i] - значение начального элемента лучшей возрастающей

подпоследовательности, имеющей длину i:

XBeg[1] > XBeg[2] > ...> XBeg[Max] }

Left,Right,Mid: LongInt;

Fin,Fout: text;

Begin

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,N);

For i:=1 to N do Read(Fin,X[i]);

Close(Fin);

XBeg[1]:=X[N];

For i:=2 to N do XBeg[i]:=0;

Max:=1; {наибольшая длина среди всех подпоследовательностей}

For i:=N-1 downto 1 do

begin

Left:=0; Right:=Max+1;

{поиск j такого, что XBeg[j+1] <= X[i] < XBeg[j] }

While Right-Left > 1 do

begin

Mid:=(Right+Left) div 2;

if X[i] < XBeg[Mid] then Left:=Mid

else Right:=Mid;

end;

j:=Left;

if j=Max then {X[i] удлиняет максимальную подпоследовательность}

begin

Max:=Max+1;

XBeg[Max]:=X[i];

end

else {X[i] замещает начало максимальной подпоследовательности}

XBeg[j+1]:=X[i];

end;

Assign(Fout,'output.txt');

Rewrite(Fout);

WriteLn(Fout,Max);

For i:=Max downto 1 do

Write(Fout,XBeg[i],' ');

Close(Fout);

End.

Премия. Жилищная контора решила наградить своего лучшего сантехника. Был составлен список балансовых сумм по N квартирам в виде целых чисел. Числа в списке пронумеровали от 1 до N. Известно, что должники имеют отрицательный баланс. Сантехник должен выбрать часть списка, указав начальный и конечный номера. Балансы, соответствующие этому диапазону номеров, суммируются. Полученное значение составляет величину премии сантехника. Требуется определить такие начальный и конечный номера, чтобы премия оказалась максимальной.

Ввод из файла INPUT.TXT. Первая строка содержит значение N (1 ≤ N ≤ 100000). Во второй строке задаются через пробел балансы жильцов X₁,…, X_N (-1000 ≤ X_i ≤ 1000).

Вывод в файл OUTPUT.TXT. В первой строке выводится максимальная сумма ожидаемой премии. Во второй строке выводятся начальный и конечный номера списка, соответствующие полученной сумме. Если ответов несколько, то указывается пара с минимальным начальным номером, а при одинаковых начальных номерах – пара с минимальным конечным номером.

Ограничения. Время счета не более 1 с.

Пример

Ввод

10

4 -19 -4 2 21 -23 15 6 -2 5

Вывод

24

4 10

Проще всего в двойном цикле перебирать все пары с начальным и конечным номерами и для каждого интервала находить сумму чисел. Максимальная сумма даст ответ задачи. Оценим трудоемкость такого подхода. Двойной цикл в общем случае приводит к трудоемкости O(N²), а общая трудоемкость составит O(N³), что абсолютно неприемлемо.

Более рационально при первом проходе накапливать в массиве S частичные суммы, то есть определять величины S_i = X₁+ X₂+…+ X_i. Тогда X_i+ X_i+1+…+ X_j = S_j - S_i-1. Такой подход обеспечивает трудоемкость O(N²), что также не может нас устроить.

Оказывается, что существует линейный алгоритм с трудоемкостью O(N), который позволяет обходиться даже без массива, обрабатывая данные за один проход напрямую из файла [7]. Будем сохранять лучшую сумму элементов R на каждом шаге и соответствующий ей интервал индексов, а также текущую сумму элементов S. Если на очередном i-ом шаге встречается положительный элемент X_i, а S<0, то начнем отсчет с начала, положив S = X_i. В противном случае прибавим значение X_i к текущей сумме S. Сравним значения R и S. Максимальную из этих величин сохраним как лучшую сумму элементов R на i-ом шаге и перейдем к следующему шагу. Ниже приводится текст программы, реализующей этот алгоритм.

Program BentFile; { линейный алгоритм }

Var

N,i,j,X,R,S,Res: LongInt;

{R- максимальная сумма на предыдущем шаге, S-текущая сумма} Fin,Fout: text;

Ra,Rb,Sa,Sb,a,b: LongInt;

{диапазоны индексов, обеспечивающие максимальные суммы для R,S и общую максимальную сумму }

Begin

Assign(Fin,'input.txt');

Reset(Fin); ReadLn(Fin,N);

R:=-MaxLongInt; S:=0;

Sa:=1; Sb:=1; Ra:=1; Rb:=1; a:=1; b:=1;

For i:=1 to N do

begin

Read(Fin,X);

if (S<0) and (X>=0) then

begin

Sa:=i; S:=X

end

else S:=S+X;

Sb:=i;

if X>R then

begin

Ra:=i; Rb:=i; R:=X

end;

if S>R then

begin

Res:=S; a:=Sa; b:=Sb;

Ra:=Sa; Rb:=Sb; R:=Res;

end

else

begin

a:=Ra; b:=Rb; Res:=R;

end;

end;

Close(Fin);

Assign(Fout,'output.txt'); Rewrite(Fout);

WriteLn(Fout,Res);

WriteLn(Fout,a,' ',b);

Close(Fout);

End.

Вернемся для примера к задаче о черепашке, рассмотренной в разделе динамического программирования. Она сводится к нахождению кратчайшего пути из левого верхнего угла матрицы C размерности M×N, заполненной числами, в правый нижний. Путь состоит из переходов по матрице направо либо вниз. Ограничимся нахождением минимальной стоимости пути без определения самого пути.

Очевидным решением является написание следующей рекурсивной функции, находящей минимальную стоимость пути от клетки матрицы с координатами (i, j) до конца.

Function F(i,j: integer): longint;

Begin

if (i=M) and (j=N) then F:=C[M,N]

else

if i=M then F:=C[i,j]+F(i,j+1)

else

if j=N then F:=C[i,j]+F(i+1,j)

else

if F(i+1,j)<F(i,j+1) then F:=C[i,j]+F(i+1,j)

else F:=C[i,j]+F(i,j+1);

End;

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