Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций

Подождите немного. Документ загружается.

свойствами, когда оптимальное решение можно легко вывести из оптимальных решений подзадач, обычно хорошо ре-

шаются так называемыми «жадными алгоритмами», примером которого, может служить алгоритм 7 «Алг. Дейкстры»

(алгоритм Дейкстры

) для задачи 4 «Shortest Path». В алгоритме 7 «Алг. Дейкстры», мы, итерационно поддерживаем

два множества вершин:

• V isited — множество вершин, до которых мы уже нашли кратчайший путь, ассоциированных со стоимостями

кратчайших путей от стартовой вершины до них.

• T oV isit — множество вершин, которые достижимы одним ребром из множества вершин V isited, ассоциирован-

ных с верхними оценками стоимости пути до них.

На каждой итерации, мы выбираем из достижимых вершин вершину v, самую ближайшую к стартовой вершине s, и

переносим ее из множества T oV isit в множество V isited, увеличиваем множество «кандидатов» T oV isit ее соседями,

и пересчитываем верхнюю оценку удаленности вершин из T oV isit до вершины s.

В иллюстрации выполнения алгоритма 7 «Алг. Дейкстры», мы показываем изменение на каждой итерации хэш-

таблиц V isited и T oV isit, а в конце изображен входной граф, где сплошными линиями нарисованы имеющиеся ребра

с ассоциированными длинами, а пунктиром — найденные кратчайшие пути.

Лемма 4 Алгоритм 7 «Алг. Дейкстры» корректен, и все найденные им пути оптимальны.

Доказательство Обозначим через δ(v, w) длину оптимального пути из v в w. Допустим, алгоритм некорректен — это

означает, что алгоритм построит неоптимальный путь до какой-то вершины. Пусть вершина u будет первой вершиной

до которой «неоптимально» доберется наш алгоритм, построив путь (s → u)

∗

, т.е. V isited[u] > δ(s, u), но все его

подпути (s → w) еще будут оптимальными (V isited[w] = δ(s, w)). Далее, будем рассматривать действия алгоритма в

той итерации, в которой он выбирает u.

Рассмотрим оптимальный путь (s → u)

, не совпадающий с (s → u)

∗

, он должен содержать в себе некоторую

вершину y /∈ V isited, т.к. если бы предпоследняя вершина z из (s → u)

в момент выбора u принадлежала V isited (т.е.

был бы построен оптимальный кратчайший путь, и V isited[z] = δ(s, y)), то по определению алгоритма T oV isit[u] ≤

V isited[z] + δ(z, u) = δ(s, u) — противоречие.

Значит, в момент выбора алгоритмом вершины u, должны существовать вершины x, y, идущие подряд в оптималь-

ном пути (s → u)

, причем y /∈ V isited, x ∈ V isited, и следовательно y ∈ T oV isit, причем

T oV isit[y] ≤ V isited[x] + δ(x, y) = δ(s, y) + δ(x, y) = δ(s, y).

Следовательно, из

• δ(s, y) < δ(s, u) (в силу положительности весов).

• V isited[u] ≤ T oV isit[y] = δ(s, y) (т.к. алгоритм выбрал на этой итерации вершину u, а не y)

следует V isited[u] < δ(s, u). Противоречие. 2

Лемма 5 Трудоемкость алгоритма 7 «Алг. Дейкстры» составляет O(n

) операций, где n — число вершин.

Доказательство Внешний цикл по вершинам дает множитель n. Внутренний цикл содержит выбор минимального

элемента — O(n) + пересчет оценок длин для соседей выбранного узла — O(n). Итого — O(n

). 2

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

биться стоимости O(V log V + E).

Упражнение 1 Приведите пример графа с отрицательными весами, для которого алгоритм Дейкстры даст

неправильный ответ.

Упражнение 2 Неориентированный граф G = (V, E) представляет телекоммуникационную сеть, причем с

каждым ребром e ∈ E ассоцирована «надежность», 0 ≤ p

≤ 1, т.е. вероятность благоприятного прохожде-

ния сигнала (в обе стороны) по ребру e. Считая события успешного или неуспешного прохождения сигнала

по различным ребрам независимыми, придумайте алгоритм, нахождения наиболее надежных маршрутов

между данным узлом и всеми остальными.

Различные варианты этого алгоритма реально используется при маршрутизации интернет-трафика. См. например стандарты OSPF, Open

Shortest Path First Routing Protocol, RFC 2740

Алгоритм 7 Алгоритм Дейкстры

Находит кратчайшие пути из одной вершины во все остальные.

def dijkstra (G, s):

print , s

хэш-таблица вершин, до которых построены кратчайшие пути, (узел:стоимость)

← {}

хэш-таблица вершин, до которых еще не построены кратчайшие пути, (узел:стоимость)

← {s: 0}

← {s: [s]} # хэш-таблица (узел:кратчайший путь)

while : # пока есть вершины, до которых не построен кратчайший путь

print , , ,

v ← argmin ( ) # выбираем ближайшую

[v] ← [v]; del [v]; # считаем, что до нее кратчайший путь найден

for w ∈ G.neighbors (v): # для всех соседей вершины v

if (w 6∈ ): # к которым еще не нашли кратчайший путь

← [v] + G.get_edge (v, w) # обновляем кратчайшие пути

if (w 6∈ ) ∨ ( < [w]) :

[w] ←

[w] ← [v] + [w]

print ,

return ( , )

NY(0)

Moscow(1)

$60

Berlin(3)

$50

Kiev(4)

$80 Minsk(2)

$15

$50

$10

Minsk-Moscow

Minsk-Berlin $20Minsk-NY

Minsk-Kiev$15

Minsk-NY

$30

Для поиска кратчайших путей между любыми двумя парами вершин можно использовать |V |запусков алгоритма 7 «Алг. Дейкс-

тры», что даст эффективное решение этой задачи алгоритмом со сложностью O(n

). Также, алгоритм 7 «Алг. Дейкст-

ры» будет работать на ориентированных графах с неотрицательными весами.

Однако такой подход не будет работать на задаче о кратчайших путях на ориентированном графе, ребра которого

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

наличии оптимального решения быть не может).

Задача 5 Задан ориентированный граф G = (V, E), и весовая функция на ребрах w

: e → Z, отображающая

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

между любой парой вершин.

Для решения этой задачи можно применять эффективный алгоритм 8 «Алг. Флойда-Уоршолла» (Алгоритм Флойда-

Уоршолла), использующий методы динамического программирования. В этом алгоритме последовательно выполня-

ются n = |V | итераций, улучшая матрицу D

минимальных стоимостей пути из вершины i в вершину j, с возмож-

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

очень легко, изначально она определяется весовой функцией ребер, D

= w

, для тех i и j, для которых есть реб-

ро (i, j), и +∞ для остальных. Обновление этой матрицы на k-той итерации происходит по очевидной формуле: D

min(D

k−1

, D

k−1

+ D

k−1

), где D

k−1

— значение этой матрицы на предыдущей итерации. Таким образом, очевидна и

корректность алгоритма 8 «Алг. Флойда-Уоршолла», и его сложность, состовляющая O(n

В иллюстрации работы алгоритма 8 «Алг. Флойда-Уоршолла» приведен вывод промежуточных структур и изобра-

жен входной граф (пунктирные дуги между двумя вершинами показывают минимальную стоимость пути между этими

вершинами, если она не совпадает со «входной» стоимостью на дуге между ними).

Таким образом, методы «жадных алгоритмов» и «динамического программирования» (подробнее о них будет рас-

сказано в следующих лекциях), позволили построить эффективные (более детально о понятии эффективности тоже

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

мени.

Задача 3 «TSP» и задачи о кратчайших путях чрезвычайно похожи по своей структуре, и мы постарались подчерк-

нуть это сходство в их формулировках.

Таким образом, сравнительно успешно устранив перебор для задач о кратчайших путях, естественно задаться ана-

логичным вопросом для задачи 3 «TSP». Довольно быстро оказывается, впрочем, что ни один из «естественных» мето-

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

решить задачу 3 «TSP» с помощью точного алгоритма, существенно более эффективного, нежели переборный?

Одним из главных достижений теории сложности вычислений является стройная и элегантная теория NP-полноты,

позволяющая в 99% случаев дать вполне удовлетворительный ответ на этот вопрос.

Эта теория будет рассмотрена далее, пока же термин NP-полная задача можно понимать неформально в смысле

труднорешаемая переборная задача, для которой существование алгоритма намного более эффективного

нежели простой перебор вариантов, крайне маловероятно.

В частности, в одном из первых исследований было показано, что задача 3 «TSP» NP-полна, и тем самым на

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

Соответственно этому, следующий вопрос, на который пытается ответить теория сложности вычислений — это

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

результаты диагностики интересующей его задачи на существование для нее точных эффективных алгоритмов столь

же неутешительны, как в случае задачи 3 «TSP». Одна из таких рекомендаций состоит в следующем: попытаться про-

анализировать постановку задачи и понять, нельзя ли видоизменить ее формулировку так, чтобы с одной стороны новая

формулировка все еще была бы приемлема с точки зрения практических приложений, а с другой стороны — чтобы в

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

чаев такой сложностной анализ позволяет лучше понять природу задачи уже безотносительно к ее вычислительной

сложности.

Например, пусть некий начинающий проектировщик сетей задумал спроектировать оптимальную компьютерную

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

жить кольцевой сетевой маршрут через все корпуса общежитий. Стоимость прокладки кабеля между любыми двумя

корпусами известна (если между какими-то корпусами кабель проложить нельзя, например из-за постоянных работ

по ремонту теплотрасс, то стоимость полагается равной +∞). Формулировка этой задачи в чистом виде совпадает с

задачей 3 «TSP». Как мы уже видели раньше, если число корпусов больше 10, то проектировщику потребуется доступ

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

время жизни проектировщика.

Что же делать незадачливому проектировщику сети? Почитав дальше книгу по проектированию сетей, он решает

построить минимальную связную сеть, используя минимальные связные (из n − 1 дуги) подграфы исходного потен-

Алгоритм 8 Алгоритм Флойда-Уоршолла

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

для простоты.

def ﬂoyd_warshal (G) :

N ← G.number_of_nodes ()

Инициализируем матрицу D расстояниями, используем 777 как ∞.

D ← (ones ((N, N)) − identity (N)) ∗ 777

for e ∈ G.edges ():

D[e[0], e[1]] ← e[2]

print D

for k ∈ xrange (N):

print ; print , k

← array (D) # Сохраняем D

k−1

в D

old

for ∈ xrange (N):

D[ , ] ← min (D[ , ], [ , k] + [k, ])

if D 6= :

print D −

else:

print ; print ; print D

return D

NY(0)

Moscow(1)

$95

Minsk(2)

$90

Berlin(3)

$145

Kiev(4)

$80

$60

$-5

$50

$10

$70

$10

$60

$20

$50

$30

$20

$30

$75

$15

$15 $10

$65

циального графа связности общежитий, так называемые остовные деревья

Задача 6 «Минимальное остовное дерево»

Задан связный неориентированный граф G = (V, E), где V —множество вершин, |V | = n, E—множество

ребер между ними, и весовая функция w : E → Z+. Иными словами, есть n вершин v

, . . . , v

и положительные

целые веса дуг w

≡ w(v

, v

)

между ними.

Чему равен наименьший возможный вес остовного дерева? Т.е., требуется найти минимально возможное

значение суммы

(i,j)∈T

w(v

, v

), (1.3)

где минимум берется по всем остовным деревьям на n вершинах, т.е. по всем множествам T из (n − 1) дуг,

связывающим все n вершин в единую сеть.

На первый взгляд, переход от задачи 3 «TSP» к задаче 6 «Minimum Spanning Tree» только увеличивает трудности,

стоящие перед нашим проектировщиком: перебор по множеству всех замкнутых путей заменяется перебором по еще

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

ошибочна, также, как и в случае с кратчайшими путями, существуют эффективные алгоритмы для задачи 6 «Minimum

Spanning Tree».

Опишем один из них, так называемый алгоритм Прима(Prim)

. В этом алгоритме минимальный остов строится

постепенно: сначала выбирается произвольная вершина, которая включается в остов, затем, на каждой итерации, к

текущему остову добавляется наиболее дешевое ребро (u, v), соединяющее какую-либо вершину из остова u, с какой-

либо вершиной v не из остова.

Алгоритм Прима и иллюстрация его работы представлена как алгоритм 9 «MST Прима», видно, как он похож на

алгоритм 7 «Алг. Дейкстры».

Упражнение 3 Докажите корректность алгоритма 9 «MST Прима».

Видно, что сложность алгоритма 9 «MST Прима» равна O(n

), а не экспоненциальна, как в алгоритме для зада-

чи 3 «TSP».

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

Упражнение 4 Докажите, что жадный алгоритм в задаче TSP не гарантирует нахождения оптимального

решения.

Этот поучительный пример еще раз наглядно демонстрирует, что при устранении перебора внутренняя структура

задачи имеет гораздо большее значение, нежели размер последнего и что внешность задачи во многих случаях быва-

ет крайне обманчивой, и никакие правдоподобные рассуждения «по аналогии» не могут заменить настоящего слож-

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

обыкновенной интуиции.

Перечислим основные выводы из этой вводной лекции:

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

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

уже при сравнительно небольшом размере входных данных (см. таблицу 1.1).

• Теория сложности вычислений занимается построением и анализом эффективных алгоритмов — в данном слу-

чае алгоритмов, в которых перебор вариантов устранен или по крайней мере сокращен до приемлемого уровня.

• Основное внимание концентрируется на сравнительно небольшом числе «модельных», классических алгоритми-

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

• Наиболее предпочтительным решением является построение точного эффективного алгоритма для рассматрива-

емой задачи.

• Имеется обширный класс NP-полных задач, для которых существование точного эффективного алгоритма пред-

ставляется крайне маловероятным. Классификация переборных задач на NP-полные и тех, которые поддаются

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

давляющее большинство переборных задач.

В англоязычной литературе — spanning trees

В англоязычной литературе — Minimum Spanning Tree

Можно вводить веса на ребрах, как w

, e ∈ E

Существует еще алгоритм Краскала(Kruskal) [

Том99].

Алгоритм 9 Алгоритм Прима

Находит минимальное остовное дерево в графе G, со стартовой вершиной s

def mst_prim (G, s):

print , s

минимальное остовное дерево в виде хэш-таблицы (вершина:предшествующая вершина)

← {}

← {s: 0} # хэш-таблица вершин, граничащих с MST, узел:(стоимость)

← {s: s} # хэш, содержащий вершины из которых планируется включать другие вершины.

while : # пока есть вершины, до которых не построен кратчайший путь

print , , ,

v ← argmin ( ) # выбираем ближайшую достижимую вершину

[v] ← [v]; del [v]; del [v];

for w ∈ G.neighbors (v): # для всех соседей вершины v

if (w 6∈ ): # которые еще не в нашем остовном дереве

обновляем стоимость включения в MST

if (w 6∈ ) ∨ (G.get_edge (v, w) < [w]):

[w] ← G.get_edge (v, w)

[w] ← v

print , ,

return

NY(0)

Moscow(1)

$60

Berlin(3)

$50

Kiev(4)

$80Minsk(2)

$15

$50

$10 $20

$15

$30

• В тех случаях, когда интересующая разработчика практических алгоритмов задача оказывается NP-полной,

имеет смысл попробовать построить эффективный алгоритм для какой-либо ее модификации, приемлемой с

практической точки зрения.

• В тех случаях, когда такую модификацию найти не удается, имеет смысл попробовать построить для решения

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

оптимальному с некоторой наперед заданной точностью.

• Рекомендации, даваемые теорией сложности вычислений в чисто прагматических целях построения эффективных

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

1.1.4 Сортировка слиянием

Задача сортировки заключается в следующем. Имеется произвольный массив A : a

, . . . , a

. Tребуется путем сравне-

ний отсортировать этот массив таким образом, чтобы элементы расположились в порядке возрастания (или убывания),

то есть a

≤ a

≤ . . . ≤ a

Слияние — это объединение двух или более упорядоченных массивов в один упорядоченный. Пусть требуется упо-

рядочить массив по убыванию. Для этого сравниваются два наименьших элемента обоих массивов и наименьший из

них выводится как наименьший элемент суммарного массива, затем процедура повторяется (см. процедуру «merge» в

алгоритме 1.1.4 «Mergesort»). Нетрудно видеть, что слияние двух упорядоченных последовательностей A и B длин |A|

и |B| происходит за O(|A| + |B|) сравнений.

Упражнение 5 Найдите такие упорядоченные последовательности A и B, на которых процедура «merge» в

алгоритме 1.1.4 «Mergesort» выполнит |A| + 1 сравнений.

Упражнение 6 Найдите такие упорядоченные последовательности A и B, на которых процедура «merge» в

алгоритме 1.1.4 «Mergesort» выполнит |A| + |B| − 1 сравнений.

Теперь рассмотрим алгоритм сортировки слиянием (Алгоритм 1.1.4 «Mergesort»). Исходный массив A длины n

делится пополам. Затем производится рекурсивная сортировка каждой половинки и их слияние. Пусть T (n) — число

сравнений, достаточное для сортировки слиянием.

Можем записать рекуррентное соотношение:

T (n) ≤ 2T (n/2) + O(n).

Чтобы решить это неравенство, применим метод подстановки. Проверим, что T (n) = cn log

n является решением

при подходящей константе c. Имеем:

cn log

n ≤ cn log(n/2) + O(n) = cn log

n − cn + O(n),

и при достаточно большом значении c неравенство выполнено. Таким образом, для сортировки массива из n элементов

достаточно cn log n сравнений.

Несмотря на асимптотически оптимальное поведение алгоритма (алгоритм сортирует входной массив за время

O(n log n) для любых входных данных), алгоритм сортировки слиянием редко применяется на практике, т.к. в процессе

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

1.1.5 Быстрая сортировка. Анализ в среднем и вероятностная версия.

Алгоритм быстрой сортировки

в худшем случае (на некоторых входных массивах) использует время Ω(n

), что, на-

пример, хуже, чем сложность в наихудшем случае алгоритма 1.1.4 «Mergesort». Однако, он является очень популярным

алгоритмом, т.к. анализ «в среднем» и опыт реального использования показали его эффективность.

Ключевая идея алгоритма 11 «Quicksort» заключается в процедуре «partition», которая за линейное время от раз-

мера массива, осуществляет такую перестановку элементов, относительно некоторой «оси» — заданного значения,

равного одному из значений сортируемого интервала массива, что переставленный массив состоит из трех интервалов,

идущих по порядку:

1. Элементы меньшие «оси»

2. Элементы равные «оси»

3. Элементы большие «оси»

QuickSort, разработан C. A. R. Hoare

Алгоритм 10 Сортировка слиянием

def mergesort (L):

print funcname (), L

if len (L) < 2:

return L

return merge (mergesort (L[ : len (L)/2]), mergesort (L[len (L)/2: ]))

def merge (A, B):

print funcname (), A, B,

← [ ]

while len (A) + len (B) > 0 :

if len (B) = 0 ∨ (len (A) > 0 ∧ A[0] < B[0]) :

.append (A[0])

A ← A[1: ]

else:

.append (B[0])

B ← B[1: ]

print ,

return

Алгоритм 11 Быстрая сортировка с детерминированным выбором оси

def quicksort (A):

def swap (i, j): # Перестановка i-го и j-го элементов массива A

← A[i]; A[i] ← A[j]; A[j] ←

Перестановка элементов в интервале [left:right) массива А, таким образом, что, возникают три интервала: в первой

части массива все элементы < осевого значения pivotValue а во второй = осевому значению. а во третьей > осевого

значения.

def partition ( , , ):

print funcname (), A[ : ], ,

← i ← # Нижний и текущий индексы

← − 1 # Верхний индекс

while i ≤ : # Пока есть область не просмотренных элементов.

if A[i] < : # Если элемент меньше оси

swap (i, ) # гоним его в начало интервала

← + 1 # сужаем область слева

i ← i + 1

elif A[i] > : # Если элемент больше оси

swap (i, ) # гоним его в конец интервала

← − 1 # сужаем область справа

else: # A[i]=pivotValue

i ← i + 1 # сужаем область слева

print , A[ : ], A[ : + 1], A[ + 1: ]

return ( , )

def qsort_interval ( , ):

if > + 1: # Если в интервале [left:right) хотя бы два элемента

print funcname (), A[ : ]

( , ) ← partition ( , , A[ ])

qsort_interval ( , )

qsort_interval ( + 1, )

qsort_interval (0, len (A))

return A

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

руются процедурой «quicksort_interval».

Упражнение 7 Модифицируйте алгоритм 11 «Quicksort», чтобы остался только один рекурсивный вызов.

Эффективность алгоритма существенно зависит от выбора «оси». Например, если назначать «осью» значение, ко-

торое больше или меньше всех элементов, то алгоритм вовсе не будет работать — разбиение никак не будет умень-

шать сортируемый интервал и алгоритм зациклится. В алгоритме 11 «Quicksort» «осью» назначается первый элемент

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

когда при разбиении, один из крайних интервалов намного меньше другого, или вовсе пустой. Например, для алгорит-

ма 11 «Quicksort», такой «плохой» входной последовательностью будет следующая:

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

алгоритм

11 «Quicksort» на «плохих» входных данных выполняет Ω(N ) рекурсий, а общее количество операций (с

учетом операций в процедуре «partition») будет Ω(

i=1

i) = Ω(n

Упражнение 8 Сколько памяти может использовать алгоритм 11 «Quicksort» в наихудшем случае?

Осталось выяснить, часто ли встречаются наихудшие случаи на множестве входных данных.

Допустим, входные данные случайны, и их распределение таково, что в каждом интервале длины N попадаемом в

процедуру «partition», первый элемент с равной вероятностью может быть k-тым (1 ≤ k ≤ N ), по величине, «разби-

вая», тем самым входной интервал на интервалы длины k−1 и N −k−1. Тогда можно записать следующую рекурсивную

оценку матожидания сложности алгоритма:

T (N) ≤ O(N ) +

(

k=1

T (k − 1) + T (N − k − 1) (1.4)

≤ O(N) +

N−1

k=1

T (k) (1.5)

Проверим разумную гипотезу, что

T (N) = O(N log N ), (1.6)

т.е. ∃C, T (N) ≤ CN log N .

Докажем вспомогательное соотношение:

N−1

k=0

k log k =

dN/2e−1

k=0

k log k +

N−1

k=dN/2e

k log k

≤ log

dN/2e−1

k=1

k + log N

N−1

k=dN/2e

≤ log N

N−1

k=1

k −

dN/2e−1

k=1

N(N − 1) log N −

(

− 1)

≤

log N −

(1.7)