Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 7
Текст из файла (страница 7)
д.:l := cons(v, nil); i := v ;while not null(ai ) do i := car(ai ); l := cons(i, l); ai := cdr(ai ) odМы здесь использовали операции над списками, применяемые в языке Лисп: car — первый элемент списка, cdr — список после удаления первого его элемента, cons — вставка элемента в начало списка,null — предикат проверки пустоты списка, nil — обозначение пустогосписка.Затраты, связанные с удлинением пути на один шаг и с проверкой,не завершен ли вояж, ограничены сверху константой (эти затратысуть четыре операции над списками), длина всего пути не превосходит | E |, и затраты во всех случаях не превосходят произведениянекоторой константы на | E |.Список l содержит в обратном порядке все вершины, через которые последовательно проходит вояж.
Если желателен прямой порядок, то надо перевернуть l:l ′ := nil ;while not null(l) do l ′ := cons(car(l), l ′ ); l := cdr(l) odПостроение списка l ′ потребует некоторых дополнительных операций над списками, число этих операций не превзойдет произведениянекоторой константы c на длину списка l, но эта длина не превосходит | E |, следовательно, число операций на этом этапе не превзойдетc| E |.Естественно считать пространственные затраты на хранение списка с числовыми элементами пропорциональными длине списка.В случае, например, графа в виде кольца каждый из списков l и l ′имеет длину | E | + 1.Обозначим буквами VL описанный алгоритм построения вояжа,предполагая, что исходный ориентированный граф задается массивом списков смежных вершин.
Из сказанного следует, что для временных затрат алгоритма VL мы имеемTCVL(G, v) ¶ c| E |,(.) Глава . Сложности алгоритмов как функции числовых аргументовгде c — некоторая константа. Это неравенство выполнено для любогоимеющего | E | ребер графа. Поэтому если значение | E | принято заразмер входа (напомним, что сам вход — это граф и выделенная в немвершина), то из (.) будет следовать TVL (| E |) ¶ c| E |, откудаTVL (| E |) = O(| E |).(.)Вместе с указанной ранее оценкой Ω(| E |) оценка (.) даетTVL (| E |) = Θ(| E |).Нетрудно вывести аналогичную оценку и для пространственнойсложности.Если массивы списков смежных вершин используются в качествепредставления ориентированных графов, то построение начинающегося с заданной вершины v вояжа в графе G = (V, E) возможно с помощью алгоритма, который при выборе числа | E | ребер в качестверазмера входа имеет сложность Θ(| E |) по числу операций над списками.
Эта же оценка имеет место для пространственной сложности,если считать, что пространственные затраты на хранение спискас числовыми элементами пропорциональны длине этого списка.Если бы граф представлялся матрицей смежности, то мы для используемого алгоритма не смогли бы получить оценку сложностиΘ(| E |), так как при блуждании по графу вход в каждую вершинусопровождается проверкой, есть ли непройденное до сих пор ребро, выходящее из этой вершины.
Например, для графа в виде кольцапри | E | = | V | = n мы имеем матрицу смежности порядка n:0 1 0 ... 00 0 1 ... 0. . . . . . . . . . . . . . . . . . .0 0 0 ... 11 0 0 ... 0Начиная вояж из первой вершины, мы потратим 2 + 3 + ... + n + 1 == Ω(n2 ) сравнений элементов матрицы с единицей при поиске первыхподходящих вершин.Разумеется, базовые операции над списками и операции сравнения элементов матрицы смежности с единицей различаются по затратности (сравнение с единицей — это очень дешевая операция). Нокакими бы ни были положительные c′ и c′′ , отражающие затраты наоперацию сравнения с и, соответственно, на операцию над списком, неравенство c′ | E |2 > c′′ | E | будет иметь место для всех достаточно§ .
Длина числа как возможный размер входабольших | E |. Константы, скрытые в оценках Ω(| E |2 ) и O(| E |), найденных для сложностей алгоритма при использовании двух разныхспособов представления графа, различаются между собой. Но тем неменее мы можем сравнивать рост первой и второй сложностей на основе этих оценок. Этот пример показателен и в том отношении, что«дешевых» операций может быть слишком много (их число можетслишком быстро расти при увеличении размера входа) и их игнорирование может датьнеправильное представление о реальной временной сложности алгоритма.Если рассматривать два параметра | V |, | E |размера входа, то сложностью алгоритма VL′будет функция TVL(| V |, | E |) двух переменных.Для того чтобы устанавливать для нее асимптотические оценки, эта функция должна бытьопределена для всех (или, по крайней мере,всех достаточно больших) натуральных значеРис.
. Граф с однойний | V |, | L |. Это значит, что для всех такихвершиной и произ| V |, | E | должен существовать граф, имеющийвольным заданным| V | вершин и | E | ребер. Проблема будет снячислом ребер.та, если, например, допустить к рассмотрениюи такие ориентированные графы, которые′имеют кратные ребра.
Оценка TVL(| V |, | E |) = O(| E |) будет, очевидно,′выполняться. Можно обосновать и оценку TVL(| V |, | E |) = Ω(| E |): достаточно рассмотреть имеющий | E | ребер граф в виде цветка (рис. ),добавив к нему | V | − 1 изолированных вершин (подобных вершине 7на рис. ) и взяв в качестве v вершину в центре «цветка». В итоге′TVL(| V |, | E |) = Θ(| E |).§ . Длина числа как возможный размер входаЧасто, хотя и не всегда, для алгоритмов целочисленной арифметики,входом которых является целое неотрицательное число n, размеромвхода выбирают не само n, а его битовую длину, или, иными словами, количество λ(n) цифр в его двоичной записи:¨1,если n = 0,λ(n) =⌊log2 n⌋ + 1, если n > 0.Выражение ⌊log2 n⌋ + 1 во второй строчке этого определения можнозаменить на ⌈log2 (n + 1)⌉ — см.
задачу . Глава . Сложности алгоритмов как функции числовых аргументовПример .. Вернемся к алгоритму пробных делений (пример .).Наряду с его уже рассмотренной сложностью TTD (n) введем еще одну∗сложность (также по числу делений) TTD(m), m = λ(n). Легко обнаружить, что эта новая функция ведет себя не так, как функция TTD (n),для которой характерны резкие скачки. Для начальных значений mимеемm:n: — — — — — —n̂:∗TTD(m):(в строке m указывается битовая длина входа; в строке n указывается диапазон, в котором располагаются значения n, битовая длина mкоторых равна числу в предыдущей строке; в строке n̂ указываетсяодно из тех чисел этого диапазона, на которых достигается максимум числа делений; в последней строке указано значение сложности∗∗TTD(m)). В поведении TTD(m) не видно резких скачков. Переход отразмера knk = n к размеру knk∗ = m = λ(n) влечет более основательное преобразование функции T(n), чем простая замена переменной.Теперь одним и тем же размером m обладают несколько входов n,затраты для которых, вообще говоря, различны, и, в соответствиис определением сложности, мы должны брать максимум этих затрат.Данным размером m обладают все целые n такие, что2 m −1 ¶ n < 2 m .(.)Согласно постулату Бертрана, при m > 1 в таком диапазоне обязательно встретится простое число.Постулат Бертрана.
При любом целом N > 1 имеется простоечисло, принадлежащее интервалу (N, 2N).∗С помощью постулата Бертрана мы можем доказать, что TTD(m) =m/2= Θ(2 ). В самом деле, обозначим через pm наибольшее простоечисло битовой длины m. Количество делений, требующееся алгоpритму для работы с pm , будет равно ⌊ pm ⌋ − 1. В силу (.) имеемp⌊2(m−1)/2 ⌋ − 1 ¶ ⌊ pm ⌋ − 1. Таким образом,111∗TTD(m) ¾ ⌊2(m−1)/2 ⌋ − 1 > p 2m/2 − 2 = p − m/2−1 2m/2 ,222Сформулирован Ж.
Бертраном в г. и доказан П. Л. Чебышевым в г. Обсуждение доказательства выходит за рамки этого курса, доказательство Чебышевасм. в [] (статья «О простых числах»). Доказательства, использующее лишь элементарные средства, можно найти в [] (приложение «Доказательство постулата Бертрана(теоремы Чебышева)») и в [, § ].§ . Длина числа как возможный размер входаи при m ¾ 4 имеем1 m/21∗TTD(m) > p −2 .22В то же время, в силу (.) очевидно, что для всех m∗TTD(m) < 2m/2 − 1 < 2m/2 .Отсюда следует требуемое.Исследуем общий вопрос о возможности перехода от оценок TA∗ (m)к оценкам TA (n) и наоборот для какого-либо алгоритма A, считая,что эти две сложности соответствуют одному и тому же способуучета затрат, но разным размерам входа — k · k и k · k∗ , принимающим значения в N+ , причем если k x k = n для некоторого входа x, тоk x k∗ = m = λ(n) = ⌊log2 n⌋ + 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
