Понятие нижней границы сложности

Задачи

Ьaj

ветствующая этому размеру, совпадает с затратами: С_Е{а₀,а_г)). В си­лу формулы Бине (10.2) имеем

lim Щ^ = Ф,

при этом C _E(F_{n +1}, F J = n. Поэтому если функция вещественной пе­ременной f{x) такова, что C _E(a ₀, a _i) «S/f—1, то, в силу предложе-

ния 13.2, /(х) разрывна в точке ф. Мы воспользовались тем, что для любого е > 0 и любого натурального JV найдется рациональное число

u/v такое, что | ф - - | < е и С_Е{и, v) =г JV. v Можно доказать, что здесь дело не в числе ф —то же самое спра­ведливо для любого х₀ > 1. Пусть 0 < s < х₀ - 1. Докажем, что в раци­ональных точках е-окрестности V_Xot£ числа х₀ функция Г_Е(г) не явля­ется ограниченной. Предположим противное: пусть г = — е V_Xot£ —ра­циональное число, на котором достигается максимум. Пусть частные, возникающие в процессе применения алгоритма Евклида к щ, и_ъ равны q _ls q₂,---,q_n:

Щ-1 = Ч1Щ + Щ+ъ i = l,2, ...,п, и_п+1 = 0.

Выберем 5 > 0 столь малым, что V_r>5 с V_Xo>s, и возьмем любое s е Q \ Z

такое, что - - s < 5 (легко заметить, что - = q „sZ). Пусть
и_п и_п

I, т —такие целые, что s = —. Используя g-i,g?,...,о,,, найдем v _n, v -,,

, v_n gN⁺, для которых

v;-i =^aivi +vi+i, i = l,2,..., n,

и v_nx = 1, v_n = т. Индукцией по к легко доказать, что для к = 0,1,, _- - 1

< 5. (13.1)

" n -fc

В самом деле, для к = 0 это очевидно; остается показать, что при 0<к<п-1из (13.1) следует

" nk 1

< 5. (13.2)

§ 13. Нецелые размеры входа и непрерывные оценочные функции 99

Имеем

откуда

v n-k-2 Ч n-k- l v n-k- l +v n-k q, v n-k

---------- = ------------------------------------ = n - _k -i "!------------------- >

v n-k-1 v n-k v n-k-_t

---------- = ------------------------------------- = qn - k -i "!--------------------

u n - k -1 u n - k u n - k -1

v n - k -2 u n - k -2

v n - k -1 u n - k -1

n - k -l u n - k -1

l un - k - l vn - k - un - kvn - k - ll u n - k -l n - k -l

Неравенство (13.1) можно переписать в виде

l un - k - l vn - k - un - kvn - k - ll _;g. n - _v - k

это неравенство влечет

u n - k -l n - k -l

так как u_n-_k-₁v_n-_k-₁ > u_n-_kv_n-_k. Неравенство (13.2) доказано, и индук­ция завершена. Следовательно, -e V_{s j5} и, тем самым, -e V_{x £}. Но

Tv\ —) > n, так как s = - _{v -} ф Z. Это противоречит предположению
^hv1 vn

, (_uЛ

о максимальности значения T _Р —.

В силу предложения 13.2 мы получаем следующее:

Пусть размер каждого входа (a ₀, a_г) алгоритма Евклида определен как r = a₀/a₁ (рациональное число ^ 1), ив соответствии с этим рас­сматривается сложность T g(r) этого алгоритма по числу делений. Пусть функция f (x) вещественной переменной, определенная всюду на бесконечном полуинтервале I =[1, оо), такова, что T _Е'(r) <f (r) при всех рациональных r ^ 1. Тогда f (x) является разрывной в любой при­надлежащей I точке.

Нелишне заметить, что при целочисленном размере входа условие предложения 13.1 может выполняться, если только для некоторого це­лого n, c_г^n^c₂, сложность T_A(n) бесконечна.

Приводившиеся ранее оценки (9.15), (9.16) для числа итераций ме­тодов деления пополам и касательных используют, фактически, неце­лый размер 1 / е. Положение спасается тем, что при малом измене­нии е не происходит катастрофического увеличения числа итераций. Эту ситуацию можно было бы считать типичной, а пример 13.1 ис­кусственным, если бы упомянутые возможные трудности не приво­дили бы иногда к реальным ошибкам. В приложении C рассмотрена известная алгоритмическая проблема, связанная с алгебраическими

100 Глава 3. Оценивание числа шагов (итераций) алгоритма

числами («проблема орбит»), для которой в свое время было пред­ложено и опубликовано неверное решение, и причина ошибки была в том, что авторы проглядели ту негативную возможность, которая показана в примере 13.1.

В ситуациях, подобных описанной в примере 13.1, мы не можем использовать в оценках вида T_A (x) < f (x), T_A (x) = O (f (x)), T_A (x) = = Θ(f (x)) в качестве функции f (x), скажем, логарифм, степенную и показательную функции, полиномы и т.д. Во многих случаях это означает, что размер как функция входа выбран неудачно. В качестве размера входа алгоритма надо, по возможности, выбирать такие вели­чины, исходя из которых сложность алгоритма может быть выражена или оценена с помощью простых аналитических функций. Это позво­лит составить представление об изменении сложности при возраста­нии размера входа. Появление функций, поведение которых трудно себе вообразить, лишает возможности получения такой информации.

48. Функцию L(s) не обязательно выбирать целочисленной. До­статочно, чтобы ее значения были неотрицательными и каждый шаг алгоритма понижал ее значение на величину, ограниченную снизу некоторым положительным числом d. Как с помощью такой функ­ции оценить число шагов?

49. При использовании m = Х{a_г) в качестве размера входа алго­ритма Евклида и его расширенного варианта для соответствующих мультипликативных сложностей справедливы верхние оценки 2m - 1 и, соответственно, вm + 3.

50. Бинарный алгоритм Евклида основан на том, что если a₀ и a_г

четны, то нод(a ₀, a_г) = 2нод(-у, -у ]; если a ₀ четно, но a_г нечет­но, то нод(a ₀, a_г) = нод(-^,a_г 1; если a ₀ нечетно, но a_г четно,

то нор,{a₀,a_г) = нод(a ₀, -у- 1; если a ₀ и a_г нечетны, то можно пе­рейти к вычислению нод(a ₀ - a_г,a_г) при a ₀ ^ a_г и к вычислению нод(a ₀, a_г - a ₀) при a₀<a_г. Вычисления заканчиваются, как только на некотором этапе вычитание даст нуль. Выполнение этого алгорит­ма завершается для любых исходных a₀, a_г, для которых a ₀ ^ a_г> 0. Для числа шагов алгоритма как функции от a₀, a_г справедлива оцен­ка O (log a ₀).

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

Задачи

51. Пусть в ходе применения алгоритма Евклида к числам а₀,а₁, а₀>а₁, возникают ненулевые остатки а₂, а₃,..., а_п, и а_п+1 = 0. Тогда a_n-_t ^ F_t+2, t = 0,1,..., п - 1. Отсюда следует справедливость следую­щего предложения, обычно именуемого в литературе теоремой Ламе. Пусть в ходе применения алгоритма Евклида к числам а₀,а₁, а₀>а₁, возникают ненулевые остатки а₂,а₃,...,а_п. Тогда а_г^Р_п+1.

52. (Продолжение задачи 51.) Пусть в ходе применения алгорит­ма Евклида к числам а₀,а_г, а₀>а₁, возникают ненулевые остатки а₂, а₃,...,а_п. Тогда п < log_(#)(a ₁ + 1) + log^ л/5-1, и, как следствие, п < log^ а_г + с для некоторой константы с.

53. Привести доказательство равенства (10.6).

54. Доказать оценку (10.8).

Указание. В § 10 при рассмотрении примера 13.1 уже доказано, что если

— е Ф_п, п > 2, то выполнены неравенства (10.7). Вывести отсюда, что ^^- ^

a-i Р2п-з

^^,т.е.£1_еФп-₁,_П > 2.
а3 F 2n-2 а3

55. Разработать алгоритм, распознающий существование у урав­
нения

ах + Ъу = с, а, Ъ, с е Z, (13.3)

решения в неотрицательных целых числах, и исследовать мультипли­кативную сложность этого алгоритма.

Указание. Уравнение (13.3) тогда и только тогда имеет решение в целых числах, когда d \ с, где d = нод(а, Ъ).

56. Если х₀, Jo — одно из целочисленных решений уравнения
(13.3), то все решения описываются формулами

x = _Xo + kt_{> J} = _Jo-£ t ₎ t = 0,±l,±2,...,

d = HOfl(a, b).

Указание. Если х₀, у₀ и x_t,y_t —два различных решения уравнения (13.3), то х₀ - x_lt у₀ - у_г — решение уравнения —х + —у = 0.

57. Числа S;, t j, получаемые в ходе выполнения расширенного ал­
горитма Евклида, являются взаимно простыми при i = 0,1,..., п + 1.

Указание. Индукцией по i доказать равенство

1 O ••• 1 O ~ Si 5;_-J

для i = 2, 3,..., п - 1 и рассмотреть определители обеих его частей.

102 Глава 3. Оценивание числа шагов (итераций) алгоритма

58. При некоторых значениях п число сравнений, затрачиваемых при бинарном поиске, не определяется однозначно исходя лишь из значения п (например, зная лишь, что п = 6, мы не можем указать точное число сравнений). Но существует бесконечно много п таких, для которых это значение определяется единственным образом и рав­но Llog₂ n J+l.

59. Бинарный поиск места элемента у в упорядоченном массиве х_г < х₂ <... < х_п требует Llog₂(n + 1)J сравнений в лучшем случае. Как следствие, для значений п вида 2^к - 1, к = 1, 2,..., и только для них число сравнений однозначно определено.

Указание. Пусть м(Ю — минимум числа сравнений при бинарном поиске места элемента. Имеем /i(l) = 1, и по индукции можно доказать, что при

п > 2 выполнено /Дп) > /Дп -1)и мОО =м([^^J) + ^L Отсюда следует, что (к(п) равно числу положительных элементов последовательности

п, п-1

I " -1 I 2

(13.4)

L 2 J' 2

Заметим, что λ

^4^ =Я(п)-1, если n ^2^fc, и a^"=^aW-2, если п = 2^к, к > 0. Если n = 2^fc - 1, fc > 0, то число положительных элемен­тов (13.4) равно А(п); в остальных случаях в последовательности (13.4) име­ется в точности один элемент вида 2^к, к> 0, и число положительных элемен­тов рассматриваемой последовательности равно А(п) - 1.

60. Опорная прямая к многоугольнику Р, проходящая через точ­ку Q, внешнюю по отношению к многоугольнику, — это прямая, ко­торой принадлежит по крайней мере одна вершина многоугольни­ка Р, и при этом все вершины этого многоугольника лежат в одной

полуплоскости по отношению к этой
прямой (рис. 16). Предложить имею­
щий сложность в 0{п) по общему чис­
лу операций алгоритм проведения двух
опорных прямых к данному выпуклому
q \ / n -угольнику из данной точки.

Рис. 16. Опорные прямые к многоугольнику.

Указание. Сначала найдем сторону n -угольника, которая видна из точки Q (см. пример 9.2). Это даст две соседние вер­шины n -угольника. Через точку Q и каждую из этих вершин проведем прямые. Затем сдвигаемся от каждой из этих двух вершин в сторону, противоположную другой вершине, пока увеличивается угол с вершиной Q.

Задачи

61. Сложность алгоритма, схематически описанного в указании к предыдущей задаче, есть в(п). (Вместе с тем, возможно построение опорных прямых со сложностью G(log n)—для этого надо применить некий вариант бинарного поиска для нахождения каждой из тех двух вершин, через которые проходят искомые опорные прямые.)

62. Предложить имеющий сложность 0{п_г + п₂) по общему чис­лу операций алгоритм построения выпуклой оболочки объединения двух выпуклых многоугольников, имеющих, соответственно, п_г и п₂ вершин, считая п_г + п₂ размером входа.

Указание. Один из известных алгоритмов этого построения основывается на том, что, взяв некоторую точку Q, принадлежащую первому многоугольни­ку, мы, в том случае, когда эта точка принадлежит и второму многоугольни­ку, можем путем слияния двух упорядоченных последовательностей получить последовательность всех вершин обоих многоугольников, упорядоченных по величине углов, под которыми видны эти вершины по отношению к какой-ни­будь фиксированной прямой, проходящей через Q. После этого, как в алгорит­ме Грэхема (см. пример 3.1), можно удалить вдавленные вершины. Если Q не принадлежит второму многоугольнику, то проведем из Q две опорные прямые ко второму многоугольнику. Пусть S и Г — вершины второго многоугольни­ка, через которые проходят опорные прямые (если опорная прямая проходит через несколько вершин, то из них выбирается наиболее удаленная от Q). Ис­ключим из рассмотрения все принадлежащие треугольнику QST вершины вто­рого многоугольника, кроме вершин S и Г (рис. 17). Оставшиеся вершины рас­сматриваем в порядке возрастания углов; сливаем, как и в первом случае, две упорядоченные последовательности, а затем удаляем вдавленные вершины.

Рис. 17. Этапы построения выпуклой оболочки объединения двух выпуклых многоугольников.

63. Верно ли, что сложность по числу сравнений сортировки мас­сива из п элементов бинарными вставками есть n log₂ n + 0(l)?

64. Обратимся к известной школьной задаче: имеются З^т монет, из которых одна фальшивая (более легкая); с помощью чашечных весов без гирь надо за т взвешиваний определить фальшивую мо-

104 Глава 3. Оценивание числа шагов (итераций) алгоритма

нету. Сравнение по весу двух групп по З^{т г} монет сужает диапазон последующего поиска до 3 ^{m _1} монет, поэтому в итоге будет затра­чено т взвешиваний, как и требуется. Для числа монет п = З^т мы имеем алгоритм, использующий log₃ п взвешиваний. (Здесь мы рас­сматриваем п в качестве размера исходной группы монет.) Можно обобщить этот алгоритм на произвольное число монет п так, что число взвешиваний будет ограничено близкой к log₃ п функцией: сравниваем по весу две группы, в каждой из которых по [п / 3] мо­нет, это сужает диапазон дальнейшего поиска до не превосходящего Гп / 31 числа монет; затем действуем тем же способом. Получить верх­нюю границу [log₃ и] для числа взвешиваний сопоставлением разме­ров групп с элементами последовательности 1,3,9,... подобно то­му, как при анализе сортировки фон Неймана количество упорядо­ченных сегментов сопоставлялось с элементами последовательности 1,2,4,...

65. Изменим алгоритм поиска фальшивой монеты (задача 64): бу­
дем сравнивать по весу две группы, в каждой из которых по [п/3\
монет, и т.д.

а) Показать, что этому алгоритму может потребоваться число
взвешиваний, которое превосходит [log₃ n l.

б) Получить верхнюю границу Llog₃ n j + 2 для числа взвешива­
ний сопоставлением размеров групп с элементами последовательно­
сти 1 + 2, 3 + 2, 9 + 2,... подобно тому, как в при анализе бинарного
поиска размеры сегментов сопоставлялись с элементами последова­
тельности 1, 2, 4,...

66. Вернемся к начальному варианту алгоритма определения фаль­шивой монеты (задача 64). При некоторых значениях п количество взвешиваний не определяется однозначно исходя лишь из значения п (например, при п = 10), хотя и существует бесконечно много п таких, для которых это значение определяется единственным образом.

67. Каждый день бизнесмен дает черту одну монету, и в обмен получает любой набор монет по своему выбору, но меньшего досто­инства. Видов монет конечное число; менять или получать деньги в другом месте бизнесмен по условиям сделки не может. Если у биз­несмена не остается монет достоинством выше минимального, он проигрывает. На таких условиях рано или поздно бизнесмен терпит поражение, каков бы ни был первоначальный запас его монет.

68. Имеется конечная последовательность нулей и единиц. Раз­
решается найти в ней группу 01 и заменить на 100...00 (при этом
можно написать сколько угодно нулей). Доказать, что это преобразо­
вание не может быть произведено бесконечно много раз.

Задачи

69. Алгоритм, приведенный в примере 11.1, затрачивает O (log n) шагов.

70. Вернемся к алгоритму кратных карт (пример 11.5). Если изна­чально все вопросы имели большие единицы кратности и обучаемому удалось дать ряд правильных ответов на один из вопросов, понизив его кратность до единицы, причем этого ему удалось добиться на фоне плохих ответов на все остальные вопросы, то дальнейшее рас­смотрение этого вопроса будет как бы отложено до тех пор, пока обучаемый не усвоит еще по крайней мере один вопрос, сведя и его кратность к единице. Алгоритм препятствует слишком быстрому изъ­ятию из рассмотрения отдельных вопросов.

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

г:=0;

for i = l to n do

for j = i + 1 to n do

for k = i+j- 1 to n do r:= r + l od

od od

(иначе: определить, чему равно г). Формальное построение и после­дующее столь же формальное вычисление суммы по аналогии с про­деланными в примере 12.1 привело бы к неправильному ответу (при­чина указывалась в § 12 в замечании к примеру 12.1).

72. Исследовать зависимость от целого п > 0 общего числа ариф­
метических операций, требуемых алгоритмом

Z:=0;

for i = l to n do

for j = l to Llog₂ i J do Z:=Z + i + j od od

73. Исследовать зависимость от n > 0 общего числа арифметиче­
ских операций, требуемых алгоритмом

Z:=0;

for i = l to La/hJ do

z:=i;

while z > 1 do Z:= Z + 1; z:= | od od

(значения z не обязательно целые).

Глава 4

Нижняя граница сложности алгоритмов некоторого класса. Оптимальные алгоритмы

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

Пример 14.1. Рассмотрим задачу поиска наименьшего элемента с помощью сравнений в массиве длины п. Для того чтобы иметь основания отсеять элемент массива как заведомо не являющийся наименьшим, необходимо, чтобы этот элемент участвовал хотя бы в одном сравнении и оказался большим. Мы должны отсеять п — 1 элемент, а в каждом сравнении ровно один элемент оказывается большим. Это означает, что потребуется не менее п — 1 сравнения.

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

Определение 14.1. Пусть.s4 — класс алгоритмов решения неко­торой задачи. Пусть принято соглашение о том, в чем измеряются затраты алгоритмов и что считается размером входа, и пусть п —обо­значение размера входа. Функция f(n) называется нижней грани­цей сложности принадлежащих.s4 алгоритмов, если для сложности Т_А ( п ) любого Ае .s4 мы имеем Т_А (п ) ^ f(n) при всех допустимых зна­чениях размера входа п. (Если используются несколько параметров п₁,п₂,...,п_к размера входа, то нижняя граница — это, соответствен­но, функция аргументов п₁, п₂,..., п_к .)

Это определение имеет смысл как для сложности в худшем случае, так и для сложности в среднем. Далее в примерах этого и следующего параграфов мы рассматриваем сложность в худшем случае; к сложно­сти в среднем мы вернемся в § 17. Всюду будет рассматриваться вре-

§ 14. Понятие нижней границы сложности

менная сложность. Мы можем сформулировать обнаруженный при рассмотрении примера 14.1 факт следующим образом.

Предложение 14.1. Функция /(п) = п - 1 является нижней гра­ницей сложности алгоритмов поиска наименьшего элемента массива длины п с помощью сравнений.

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

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

Пример 14.2. Рассмотрим класс алгоритмов сортировки с помо­щью сравнений. Если алгоритм работает для массивов любой дли­ны, то, разумеется, можно рассмотреть этот алгоритм применитель­но к массивам некоторой фиксированной длины п. Любая сортировка с помощью сравнений может быть для каждого конкретного п изоб­ражена бинарным деревом. В корне и внутренних вершинах находят­ся выполняемые сравнения, в листьях выписаны результаты сортиров­ки. Априори в исходном массиве возможен любой порядок элемен­тов, поэтому дерево будет иметь п\ листьев. Если взять, например, сортировку простыми вставками, то при п = 2 ее можно изобразить деревом, представленным на рис. 18а. При п = 3 дерево принимает вид, показанный на рис. 18б. Сложность в худшем случае для каждо­го п равна высоте соответствующего дерева (напомним, что высотой листа называется число ребер в том единственном пути, который ве­дет от корня дерева к этому листу; высотой дерева называется мак­симум высот его листьев). Если высота некоторого бинарного дерева равна а, то, очевидно, оно содержит не более 2^h листьев (максималь­ное возможное число листьев достигается в случае полного бинарно­го дерева, которое имеет ровно 2^h листьев). Поэтому если Г(п)—это временная сложность некоторой сортировки сравнениями, то должно выполняться неравенство

2^г("^п!,

108 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

а) Гx-l <x₂Л 1/ \0

Сx₂ <x₃~Л 1/ \0

б) Г x _г <x₂^Л

x_ъ < x j J

1/ \0

x_ltx₂,x₃ Сx_г <x₃~Л

\/ \0

Сx₃ <x₂"\ x₂,x_t,x₃

1/ \0

x ₁, x ₃, x ₂ x₃,x_ltx₂ x₃,x₂,x_l x₂,x₃,x_l

Рис. 18. Дерево сортировки простыми вставками для случаев а) n = 2 и б) n = 3.

откуда T (n) ^log₂ n!; так как значение T (n)—целое число (мы изме­ряем сложность числом сравнений), то T{n) ^ [log₂ n\]. Доказанное можно сформулировать в виде предложения.

Предложение 14.2. Функция f (n) = [log₂ n\] является нижней гра­ницей сложности алгоритмов сортировки массивов длины n c помо­щью сравнений.

Отсюда можно вывести, например, следующее предложение.

Предложение 14.3. Пусть сложность T{n) некоторой сортиров­ки по числу сравнений не превосходит nlog₂n + cn, где c —некото­рая константа. Тогда T{n) = n log₂ n + O{n) и, как следствие, T{n)~ ~ n log₂ n.

Доказательство. В силу предложения 14.2 и формулы (10.12) для
всех достаточно больших n мы имеем T{n) ^ [log₂ n il > n log₂ n - 2 n,
и, следовательно, n log₂ n - 2 n < T{n) s= n log₂ n + cn. Отсюда следует
требуемое. □

Это позволяет, например, заключить, что для сложности по чис­лу сравнений сортировки фон Неймана имеет место оценка T _vN(n) = = n log₂ n + O{n) и асимптотическое равенство T _vN(n) ~ n log₂ n, — мы уже видели, что T_vN < n\log₂ n\<n log₂ n + n.

§ 15. Оптимальные алгоритмы

Добавим, что никакая сортировка не может иметь сложность T{n) по числу сравнений, допускающую оценку a n log₂ n + o (n log n), a < 1 (в частности, оценку a n log₂ n + O{n)), —это следует из того, что для всех достаточно больших n выполнено T{n)>n log₂ n - 2n.

Пример 14.3. Обратимся к задаче поиска места элемента в упо­рядоченном массиве длины n.

Предложение 14.4. Функция f (n) = [log₂(n + 1)1 является нижней границей сложности алгоритмов поиска места элемента в упорядо­ченном массиве длины n c помощью сравнений.

Доказательство. Любой алгоритм поиска места элемента в упо­
рядоченном массиве фиксированной длины n может быть изображен
бинарным деревом. Число листьев такого дерева есть n + 1. Далее
рассуждаем так же, как при доказательстве предложения 14.2. □

Пример 14.4. Рассмотрим задачу вычисления aⁿ с помощью умно­жений (пример 4.2). Будем считать n размером входа. Затраты будем измерять количеством умножений.

Предложение 14.5. Функция f (n) = [log₂ n ] является нижней гра­ницей сложности алгоритмов вычисления aⁿ с помощью умножений.

Доказательство. На каждом этапе алгоритма мы имеем вычис­ленный набор степеней

a^m\a^m\...,a^mk\ (14.1)

при этом на начальном этапе набор состоит из одного элемента a¹.
Выполнив одно умножение, мы, очевидно, не можем увеличить мак­
симальный показатель m = max{ m ₁, m ₂, ...,m_k} более чем вдвое. По­
этому если определить на наборах вида (14.1) функцию L, равную
log₂ n - log₂ m, то в результате одного шага (одного умножения) эта
функция не может уменьшиться больше чем на 1. В то же время зна­
чение этой функции на исходном наборе равно log₂ n, а на итоговом
наборе она заведомо неположительна. □

Дата добавления: 2014-01-11