анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 4 из 26

Глава
3
Эффективность
Эффективность алгоритмов играет центральную роль в олимпиадном программировании. В этой главе мы будем изучать средства, упрощаю- щие проектирование эффективных алгоритмов.
В разделе 3.1 вводится понятие временной сложности, которое позво- ляет оценить время работы алгоритма, не реализуя его. Временная слож- ность описывает, как быстро время работы алгоритма увеличивается с рос том размера входных данных.
В разделе 3.2 приведены две задачи, которые можно решить многими способами. В обоих случаях легко спроектировать медленный алгоритм с полным перебором, но, как выясняется, можно создать гораздо более эф- фективные алгоритмы.
3.1. Временная сложность
Временная сложность алгоритма – это оценка того, сколько времени будет работать алгоритм при заданных входных данных. Зная временную слож- ность, мы зачастую можем сказать, достаточно ли алгоритм быстрый для решения задачи, даже не реализуя его.
Для описания временной сложности применяется нотация O(…), где многоточием представлена некоторая функция. Обычно буквой n обозна- чается размер входных данных. Например, если на вход подается массив чисел, то n – это размер массива, а если строка, то n – длина строки.
3.1.1. Правила вычисления
Если код включает только линейную последовательность команд, как, на- пример, показанный ниже, то его временная сложность равна O(1).
a++;
b++;
c = a+b;
Временная сложность цикла оценивает число выполненных итераций.
Например, временная сложность следующего кода равна O(n), поскольку

44 
Глава 3. Эффективность код внутри цикла выполняется n раз. При этом предполагается, что много- точием «…» обозначен код с временной сложностью O(1).
for (int i = 1; i <= n; i++) {
}
Временная сложность следующего кода равна O(n
2
):
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
Вообще, если имеется k вложенных циклов и в каждом цикле перебира- ется n значений, то временная сложность равна O(n
k
).
Временная сложность не сообщает, сколько точно раз выполняется код внутри цикла, она показывает лишь порядок величины, игнорируя посто- янные множители. В примерах ниже код внутри цикла выполняется 3n,
n + 5 и ⌈n/2⌉ раз, но временная сложность в каждом случае равна O(n).
for (int i = 1; i <= 3*n; i++) {
}
for (int i = 1; i <= n+5; i++) {
}
for (int i = 1; i <= n; i += 2) {
}
С другой стороны, временная сложность следующего кода равна O(n
2
), поскольку код внутри цикла выполняется 1 + 2 + … + n = ½(n
2
+ n)раз.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
}
}
Если алгоритм состоит из нескольких последовательных частей, то об- щая временная сложность равна максимуму из временных сложностей от- дельных частей, т. е. самая медленная часть является узким местом. Так,

3.1. Временная сложность

45
следующий код состоит из трех частей с временной сложностью O(n), O(n
2
) и O(n). Поэтому общая временная сложность равна O(n
2
).
for (int i = 1; i <= n; i++) {
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
for (int i = 1; i <= n; i++) {
}
Иногда временная сложность зависит от нескольких факторов, поэтому формула включает несколько переменных. Например, временная слож- ность следующего кода равна O(nm):
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
}
}
Временная сложность рекурсивной функции зависит от того, сколько раз она вызывается, и от временной сложности одного вызова. Общая временная сложность равна произведению того и другого. Рассмотрим, к примеру, следующую функцию:
void f(int n) {
if (n == 1) return;
f(n-1);
}
Вызов f(n)приводит к n вызовам функций, и временная сложность каждого вызова равна O(1), поэтому общая временная сложность рав- на O(n).
В качестве еще одного примера рассмотрим следующую функцию:
void g(int n) {
if (n == 1) return;
g(n-1);
g(n-1);
}

46 
Глава 3. Эффективность
Что происходит, когда эта функция вызывается с параметром n? Сна- чала она будет дважды вызвана с параметром n − 1, затем четыре раза с параметром n − 2, потом восемь раз с параметром n − 3 и т. д. Вообще, будет
2
k
вызовов с параметром n – k, где k = 0, 1, …, n − 1. Таким образом, общая временная сложность равна
1 + 2 + 4 + … + 2
n
−1
= 2
n
− 1 = O(2
n
).
3.1.2. Часто встречающиеся оценки временной сложности
Ниже перечислены часто встречающиеся оценки временной сложности алгоритмов.
O(1) Время работы алгоритма с постоянным временем не зависит от размера входных данных. Типичным примером может служить яв- ная формула, по которой вычисляется ответ.
O(log n)В логарифмическом алгоритме размер входных данных на каж дом шаге обычно уменьшается вдвое. Время работы зависит от размера входных данных логарифмически, поскольку log
2
n – это сколько раз нужно разделить n на 2, чтобы получить 1. Отметим, что основание логарифма во временной сложности не указывается.
O(√n
) Алгоритм с временной сложностью O(√n) медленнее, чем O(log n), но быстрее, чем O(n). Специальное свойство квадратного корня за- ключается в том, что √n = n/√n, т. е. n элементов можно разбить на
O(√n)порций по O(√n)элементов.
O(n) Линейный алгоритм перебирает входные данные постоянное чис- ло раз. Зачастую это наилучшая возможная временная сложность, потому что обычно, чтобы получить ответ, необходимо обратиться к каждому элементу хотя бы один раз.
O(n log n) Такая временная сложность часто означает, что алгоритм сортирует входные данные, поскольку временная сложность эффек- тивных алгоритмов сортировки равна O(n log n). Есть и другая воз- можность – в алгоритме используется структура данных, для кото- рой каждая операция занимает время O(log n).
O(n
2
) Квадратичный алгоритм нередко содержит два вложенных цикла.
Перебрать все пары входных элементов можно за время O(n
2
).
O(n
3
) Кубический алгоритм часто содержит три вложенных цикла. Все тройки входных элементов можно перебрать за время O(n
3
).
O(2
n
) Такая временная сложность нередко указывает на то, что алго- ритм перебирает все подмножества множества входных данных. На- пример, подмножествами множества {1, 2, 3} являются ∅, {1}, {2}, {3},
{1, 2}, {1, 3}, {2, 3} и {1, 2, 3}.

3.1. Временная сложность

47
O(n!)Такая временная сложность часто означает, что алгоритм пере- бирает все перестановки входных элементов. Например, переста- новками множества {1, 2, 3} являются (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1),
(3, 1, 2) и (3, 2, 1).
Алгоритм называется полиномиальным, если его временная сложность не выше O(n
k
), где k – константа. Все приведенные выше оценки временной сложности, кроме O(2
n
)и O(n!),полиномиальные. На практике константа k
обычно мала, поэтому полиномиальная временная сложность, грубо гово- ря, означает, что алгоритм может обрабатывать большие входные данные.
Большинство алгоритмов в этой книге полиномиальные. Однако сущест- вует много важных задач, для которых полиномиальный алгоритм неиз- вестен, т. е. никто не знает, как решить их эффективно. Важным классом задач, для которых неизвестен полиномиальный алгоритм, являются
NP-трудные задачи.
3.1.3. Оценка эффективности
Вычислив временную сложность алгоритма, мы можем еще до его реа- лизации проверить, будет ли он достаточно эффективен для решения за- дачи. Отправной точкой для оценки является тот факт, что современный компьютер может выполнить несколько сотен миллионов простых опера- ций в секунду.
Например, предположим, что для задачи установлено временное огра- ничение – не более одной секунды – и что размер входных данных равен
n = 10 5
. Если временная сложность алгоритма равна O(n
2
), то он должен бу- дет выполнить порядка (10 5
)
2
= 10 10
операций. Это займет, по меньшей мере, несколько десятков секунд, поэтому такой алгоритм слишком медленный для решения задачи. Но если временная сложность равна O(n log n), то ко- личество операций будет равно всего 10 5
log 10 5
≈ 1.6 · 10 6
, так что алгоритм гарантированно укладывается в отведенные рамки.
С другой стороны, зная размер входных данных, мы можем попытаться угадать временную сложность алгоритма, требуемую для решения задачи.
В табл. 3.1 приведены некоторые полезные оценки в предположении, что временное ограничение равно 1 секунде.
Например, если размер входных данных n = 10 5
, то, вероятно, можно ожидать, что временная сложность алгоритма равна O(n)или O(n log n).
Обладание этой информацией упрощает проектирование алгоритма, по- скольку сразу исключает подходы, приводящие к алгоритму с худшей вре- менной сложностью.
При всем при том важно помнить, что временная сложность – всего лишь оценка эффективности, поскольку она скрывает постоянные мно- жители. Например, алгоритм с временной сложностью может выполнять

48 
Глава 3. Эффективность как n/2, так и 5n операций, а это существенно влияет на фактическое время работы.
Таблица 3.1. Оценка временной сложности по размеру входных данных
Размер входных данных
Ожидаемая временная сложность
n
≤ 10
O
(n!)
n
≤ 20
O
(2
n
)
n
≤ 500
O
(n
3
)
n
≤ 5000
O
(n
2
)
n
≤ 10 6
O
(n
log n) или O(n)
n
велико
O
(1) или O(log n)
3.1.4. Формальные определения
Что в действительности означают слова «время работы алгоритма со- ставляет O(f (n))»? Что существуют такие константы c и n
0
, что алгоритм выполняет не более cf (n) операций при любых входных данных размера
n ≥ n
0
. Таким образом, нотация O дает верхнюю границу времени работы алгоритма при достаточно объемных входных данных.
Например, технически правильно будет сказать, что временная слож- ность следующего алгоритма равна O(n
2
).
for (int i = 1; i <= n; i++) {
}
Однако оценка O(n) лучше, поэтому давать в этом случае оценку O(n
2
) – значит вводить в заблуждение читателя, т. к. любой человек предполагает, что нотация O служит для точной оценки временной сложности.
На практике часто применяются еще два варианта нотации. Буквой Ω
обозначается нижняя граница времени работы алгоритма. Временная сложность алгоритма равна Ω(f (n)), если существуют константы c и n
0
– та- кие, что алгоритм выполняет не менее cf (n) операций при любых входных данных размера n ≥ n
0
. Наконец, буквой Θ обозначается точная граница: временная сложность алгоритма равна Θ(f (n)), если она одновременно равна O(f (n))и Ω(f (n)). Так, временная сложность приведенного выше ал- горитма одновременно равна O(n)и Ω(n), поэтому она также равна Θ(n).
Описанная нотация используется во многих ситуациях, а не только в контексте временной сложности алгоритмов. Например, можно сказать, что массив содержит O(n) элементов или что алгоритм состоит из O(log n)
раундов.

3.2. Примеры проектирования алгоритмов

49
3.2. Примеры проектирования алгоритмов
В этом разделе мы обсудим две задачи проектирования алгоритмов, кото- рые можно решить несколькими способами. Начнем с простых алгорит- мов с полным перебором, а затем предложим более эффективные реше- ния, основанные на различных идеях.
3.2.1. Максимальная сумма подмассивов
Пусть дан массив n чисел; наша первая задача заключается в том, чтобы вычислить максимальную сумму подмассивов, т. е. наибольшую возможную сумму последовательных элементов. Задача приобретает интерес, когда в массиве встречаются элементы с отрицательными значениями. На рис. 3.1 показаны массив и его подмассив с максимальной суммой.
Рис. 3.1. Подмассивом с максимальной суммой является [2,4,–3,5,2]. Его сумма равна 10
Решение со сложностью O(n
3
). Задачу можно решить в лоб: перебрать все возможные подмассивы, вычислить сумму элементов в каждом под- массиве и запомнить максимальную сумму. Этот алгоритм реализован в следующем коде:
int best = 0;
for (int a = 0; a < n; a++) {
for (int b = a; b < n; b++) {
int sum = 0;
for (int k = a; k <= b; k++) {
sum += array[k];
}
best = max(best,sum);
}
}
cout << best << "\n";
В переменных a
и b
хранятся первый и последний индекс подмассива, а в переменную sum записывается сумма его элементов. В переменной best хранится максимальная сумма, найденная в процессе просмотра. Времен- ная сложность этого алгоритма равна O(n
3
), поскольку налицо три вложен- ных цикла, в которых перебираются входные данные.

50 
Глава 3. Эффективность
Решение со сложностью O(n
2
). Алгоритм легко сделать более эффек- тивным, исключив один цикл. Для этого будем вычислять сумму одно- временно со сдвигом правого конца подмассива. В результате получается такой код:
int best = 0;
for (int a = 0; a < n; a++) {
int sum = 0;
for (int b = a; b < n; b++) {
sum += array[b];
best = max(best,sum);
}
}
cout << best << "\n";
После подобного изменения временная сложность становится равна
O(n
2
).
Решение со сложностью O(n). Оказывается, что задачу можно решить и за время O(n), т. е. достаточно и одного цикла. Идея в том, чтобы для каждой позиции массива вычислять максимальную сумму подмассива, заканчивающегося в этой позиции. Тогда для получения окончательного ответа достаточно будет взять максимум из этих сумм.
Рассмотрим подзадачу нахождения подмассива с максимальной сум- мой, заканчивающегося в позиции k. Есть две возможности:
1. Подмассив состоит из единственного элемента в позиции k.
2. Подмассив состоит из подмассива, заканчивающегося в позиции
k − 1, за которым следует элемент в позиции k.
Во втором случае, поскольку мы ищем подмассив с максимальной сум- мой, сумма подмассива, заканчивающегося в позиции k – 1, также должна быть максимальной. Таким образом, задачу можно решить эффективно, если вычислять сумму максимального подмассива для каждой позиции последнего элемента слева направо.
Алгоритм реализуется следующей программой:
int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
sum = max(array[k],sum+array[k]);
best = max(best,sum);
}
cout << best << "\n";
В этом алгоритме только один цикл, в котором перебираются входные данные, поэтому его временная сложность равна O(n). Лучшей сложности

3.2. Примеры проектирования алгоритмов

51
добиться нельзя, поскольку любой алгоритм решения этой задачи должен хотя бы один раз проанализировать каждый элемент.
Сравнение эффективности. Насколько приведенные выше алгоритмы эффективны на практике? В табл. 3.2 показано время выполнения этих ал- горитмов на современном компьютере для разных значений n. В каждом тесте входные данные генерировались случайным образом, и время чте- ния входных данных не учитывалось.
Сравнение показывает, что все алгоритмы работают быстро, если раз- мер входных данных мал, но по мере возрастания размера расхождение во времени становится очень заметным. Алгоритм со сложностью O(n
3
) замедляется, когда n = 10 4
, а алгоритм со сложностью O(n
2
)– при n = 10 5
И лишь алгоритм со сложностью O(n)даже самые большие входные дан- ные обрабатывает мгновенно.
Таблица 3.2. Сравнение времени выполнения различных алгоритмов вычисления максимальной суммы подмассивов
Размер массива n
O(n
3
) (с)
O(n
2
) (с)
O(n
) (с)
10 2
0.0 0.0 0.0 10 3
0.1 0.0 0.0 10 4
> 10.0 0.1 0.0 10 5
> 10.0 5.3 0.0 10 6
> 10.0
> 10.0 0.0 10 7
> 10.0
> 10.0 0.0
3.2.2. Задача о двух ферзях
Следующая наша задача будет такой: сколькими способами можно по- ставить на доску n×n двух ферзей, так чтобы они не били друг друга. На рис. 3.2 показано, что на доске 3×3 это можно сделать 8 способами. Обо- значим q(n)количество расстановок на доске n×n. Например, q(3)= 8, а в табл. 3.3 приведены значения q(n)для 1 ≤ n ≤ 10.
Рис. 3.2. Все возможные способы поставить двух ферзей на доску 3×3, так чтобы они не били друг друга

52 
Глава 3. Эффективность
Таблица 3.3. Значения q(n): число способов поставить двух ферзей на доску n×n, так чтобы они не били друг друга
Размер доски
Число расстановок q(n)
1 0
2 0
3 8
4 44 5
140 6
340 7
700 8
1288 9
2184 10 3480
Конечно, задачу можно решить по-простому: перебрать все возможные расстановки двух ферзей и подсчитать те, в которых ферзи не бьют друг друга. Временная сложность такого алгоритма O(n
4
), поскольку позицию первого ферзя можно выбрать n
2
способами, а затем поставить второго ферзя n
2
− 1 способами.
Так как число расстановок растет очень быстро, алгоритм их подсчета поодиночке будет работать слишком медленно для больших n. Следова- тельно, для создания эффективного алгоритма нужно придумать способ подсчета расстановок группами. Полезно отметить, что очень просто под- считать, сколько клеток бьет один ферзь (рис. 3.3). Во-первых, он всегда бьет n − 1 клеток по горизонтали и n − 1 клеток по вертикали. Далее по обе- им диагоналям ферзь бьет d − 1 клеток, где d – число клеток на диагонали.
С учетом всего этого для вычисления числа клеток, в которые можно по- ставить второго ферзя, нужно время O(1), так что мы получаем алгоритм с временной сложностью O(n
2
).
Рис. 3.3. Ферзь бьет все клетки, помеченные знаком
*

3.3. Оптимизация кода

53
К задаче можно подойти и по-другому, попытавшись найти рекуррент- ную формулу для подсчета расстановок, т. е. ответить на вопрос: как, зная
q
(n), вычислить q(n + 1)?
Чтобы получить рекурсивное решение, обратим внимание на последние горизонталь и вертикаль доски n×n (рис. 3.4). Во-первых, число расстано- вок, в которых на последней горизонтали и на последней вертикали нет ферзей, равно q(n − 1). Во-вторых, общее число позиций ферзя на послед- ней горизонтали и на последней вертикали равно 2n − 1. Находящийся в этих позициях ферзь бьет 3(n − 1)клеток, поэтому для второго ферзя оста- ется n
2
− 3(n − 1)– 1 позиций. Наконец, существует (n − 1)(n − 2)расста- новок, в которых оба ферзя находятся на последней горизонтали или на последней вертикали. Поскольку эти расстановки посчитаны дважды, их количество надо вычесть. Объединив все вместе, получаем рекуррентную формулу
q
(n) = q(n − 1)+ (2n − 1)(n
2
− 3(n − 1) − 1) − (n − 1)(n − 2)
= q(n − 1)+ 2(n − 1)
2
(n − 2)
и вместе с ней решение сложности O(n).
Рис. 3.4. Возможные позиции ферзей на последней горизонтали и вертикали
Однако же существует и замкнутая формула для этой функции:
4 3
2 5
3
( )
,
2 3
2 3
n
n
n
n
q n
=
−
+
−
которую можно доказать по индукции, пользуясь рекуррентной форму- лой. А раз так, то задачу можно решить за время O(1).
3.3. Оптимизация кода
Временная сложность алгоритма может многое сказать о его эффектив- ности – это правда, но важны и детали реализации. Вот, к примеру, два фрагмента кода, в которых проверяется, есть ли в массиве элемент x:
bool ok = false;
for (int i = 0; i < n; i++) {

54 
Глава 3. Эффективность
if (a[i] == x) ok = true;
}
bool ok = false;
for (int i = 0; i < n; i++) {
if (a[i] == x) {ok = true; break;}
}
Оба фрагмента работают за время O(n), однако на практике второй может оказаться значительно эффективнее, потому что прекращает работу, как только элемент x найден. Это полезная оптимизация, потому что она дейст- вительно повышает производительность кода и к тому же легко реали зуется.
Можно ли еще улучшить этот код? Существует классический прием, ко- торый можно попробовать: воспользоваться сторожевым значением, т. е. добавить в конец массива новый элемент со значением x. Тогда не нужно будет проверять условие i < n в цикле:
a[n] = x;
int i;
bool ok = false;
for (i = 0; a[i] != x; i++);
if (i < n) ok = true;
Прием изящный, но на практике не особенно полезен: «затык» не в проверке условия i < n, поскольку доступ к элементам массива занимает гораздо больше времени. Таким образом, не все оптимизации полезны, некоторые лишь затрудняют понимание кода.
3.3.1. Результат работы компилятора
Компилятор C++ преобразует написанный на C++ код в машинный, исполняемый процессором. Важная задача компилятора – оптимизация кода. Результирующий код должен быть эквивалентен коду на C++, но при этом работать как можно быстрее. Часто количество возможных оптими- заций велико.
Мы можем получить машинный код (в формате ассемблера), порожден- ный компилятором g++
, задав флаг
-S
:
g++ -S test.cpp -o test.out
Эта команда создает файл test.out
, содержащий код на языке ассембле- ра. Существует также полезный онлайновый инструмент Compiler Explorer
1
, которым можно воспользоваться для исследования результатов работы различных компиляторов, включая g++
1
https://godbolt.org/

3.3. Оптимизация кода

55
Оптимизации компилятора. Например, рассмотрим следующий код на C++:
int collatz(int n) {
if (n%2 == 0) return n/2;
else return 3*n+1;
}
Ассемблерный код, порожденный g++
(с флагом оптимизации
-O2
), мо- жет выглядеть так:
test dil, 1
jne .L2
mov eax, edi shr eax, 31
add eax, edi sar eax ret
.L2:
lea eax, [rdi+1+rdi*2]
ret
Даже в этом крохотном кусочке кода много оптимизаций. Команда test проверяет, равен ли 1 самый правый бит n, т. е. является ли число нечет- ным, и она быстрее, чем операция взятия остатка от деления. Затем ко- манда sar выполняет поразрядный сдвиг вправо на один бит, т. е. вычис- ляет значение n/2, причем быстрее, чем операция деления. Наконец, для вычисления значения 3n + 1 применяется еще один трюк: основная задача команды lea
– определить адрес элемента массива в памяти, но ее можно использовать и для простых вычислений.
Зачастую необязательно оптимизировать программу самостоятельно
(например, отдавать предпочтения побитовым операциям вместо деле- ния и взятия остатка), потому что компилятор C++ знает все эти приемы и умеет применять их. Кроме того, компилятор умеет находить и удалять ненужный код. Рассмотрим, например, следующую функцию:
void test(int n) {
int s = 0;
for (int i = 1; i <= n; i++) {
s += i;
}
}
Ей соответствует всего одна строка на ассемблере:
ret

56 
Глава 3. Эффективность означающая, что мы просто выходим из функции. Поскольку значение s нигде не используется, саму эту переменную и весь цикл можно удалить, и код будет работать за время O(1). Поэтому при измерении времени ра- боты кода важно следить за тем, чтобы его результат как-то использовался
(например, можно его напечатать), иначе компилятор может удалить код в процессе оптимизации.
Оптимизации, зависящие от оборудования. Флаг g++
-march=native включает оптимизации, зависящие от оборудования. Например, в некото- рых процессорах имеются специальные команды, отсутствующие в других процессорах. Слово native здесь означает, что компилятор автоматически определяет архитектуру процессора и применяет зависящие от нее опти- мизации там, где это возможно.
Например, рассмотрим следующий код, который вычисляет сумму еди- ничных битов с помощью встроенной в g++
функции
__builtin_popcount
:
c = 0;
for (int i = 1; i <= n; i++) {
c += __builtin_popcount(i);
}
Во многих процессорах имеется специальная команда popcnt
, которая эффективно выполняет операции подсчета битов. Во многих, но не во всех, поэтому g++
не использует ее автоматически, для этого нужно задать флаг
-march=native
. И в таком случае приведенный выше код будет рабо- тать в два-три раза быстрее.
Флаг
-march=native нечасто задается в олимпиадных системах, но мы можем сами указать архитектуру в своем коде с помощью директивы
#pragma
. Однако в этом контексте значение native не поддерживается, тре- буется задать имя архитектуры. Так, возможно, будет работать следующая директива (в предположении, что программа исполняется процессором с архитектурой Sandy Bridge):
#pragma GCC target ("arch=sandybridge")
3.3.2. Особенности процессора
Исполняя код, процессоры стараются делать это как можно быстрее. Су- ществуют кеши, ускоряющие доступ к памяти, а иногда несколько команд можно выполнять параллельно. Современные процессоры очень сложны, и мало кто понимает, как они в действительности работают.
Кеши. Поскольку доступ к основной памяти сравнительно медленный, в процессорах имеются кеши – участки небольшого объема памяти с бо- лее быстрым доступом. Кеши автоматически используются, когда чита- ется или записывается содержимое расположенных рядом ячеек памяти.

3.3. Оптимизация кода

57
В частности, просмотр элементов массива слева направо производится быстро, а в случайном порядке – медленно.
В качестве примера рассмотрим два таких фрагмента:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s += x[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s += x[j][i];
}
}
В обоих случаях вычисляется сумма элементов двумерного массива, но первый вариант работает намного эффективнее, потому что дружелюбен к
кешу. Элементы массива хранятся в памяти в таком порядке:
x
[0][0], x[0][1], ... , x[0][n − 1], x[1][0], x[1][1], ...
Поэтому лучше, когда во внешнем цикле изменяется первый индекс, а во внутреннем – второй.
Распараллеливание. Современные процессоры могут выполнять не- сколько команд одновременно, и во многих ситуациях это происходит ав- томатически. Вообще говоря, две соседние команды могут выполняться параллельно, если они не зависят друг от друга. Рассмотрим такой код:
ll f = 1;
for (int i = 1; i <= n; i++) {
f = (f*i)%M;
}
Здесь в цикле вычисляется факториал n по модулю M. Можно попро- бовать сделать этот код эффективнее, поступив следующим образом
(в предпо ложении, что n четно):
ll f1 = 1;
ll f2 = 1;
for (int i = 1; i <= n; i += 2) {
f1 = (f1*i)%M;
f2 = (f2*(i+1))%M;
}
ll f = f1*f2%M;

58 
Глава 3. Эффективность
Идея в том, чтобы использовать две независимые переменные: f
1
будет содержать произведение 1 · 3 · 5 · … · (n – 1), а f
2
– произведение 2 · 4 · 6 · … · n.
По завершении цикла оба результата объединяются. Этот код обычно ра- ботает в два раза быстрее первоначальной версии, потому что процессор может параллельно выполнять команды, изменяющие переменные f
1
и f
2
внутри цикла. Можно даже завести больше переменных (скажем, четыре или восемь) и тем самым еще увеличить скорость работы.