Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 11

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

Текст из файла (страница 11)

Для любого алгоритма S внутренней сортировкисравнением массива из n элементов количество сравненийCS ≥ O(n⋅log2(n))Доказательство.Для любого алгоритма S внутреннейсортировки сравнением массива из n элементовколичество сравненийCS ≥ log2(n!).(1)(a)Алгоритм S можно представить в виде двоичногодерева сравнений.Так как любая перестановка индексоврассматриваемого массива может быть ответом валгоритме, она должна быть приписана хотя быодному листу дерева сравнений.Таким образом, дерево сравнений будетиметь не менее n! листьев.7СортировкаОценка сложности алгоритмов сортировки.Теорема. Для любого алгоритма S внутренней сортировкисравнением массива из n элементов количество сравненийCS ≥ O(n⋅log2(n))Доказательство.Для любого алгоритма S внутреннейсортировки сравнением массива из n элементовколичество сравненийCS ≥ log2(n!).(1)(б)(*)Для высоты hm двоичного дерева с m листьямиимеет место оценка:hm ≥ log2m.Любое двоичное дерево высоты h можно достроить дополного двоичного дерева высоты h, а у полногодвоичного дерева высоты h 2h листьев.Применив полученную оценку к деревусравнений, получим оценку (*)8СортировкаОценка сложности алгоритмов сортировки.Теорема.

Для любого алгоритма S внутренней сортировкисравнением массива из n элементов количество сравненийCS ≥O(n⋅log2(n))Доказательство.(2)К log2(n!) применим формулу Стирлингаn!= 2πn ⋅ n n e − n eϑ ( n )1| ϑ (n) |≤12n(**)Логарифмируя (**), получаем1log(n! ) = log(2πn ) + n ⋅ log(n ) − n + ϑ (n )2log(n! ) ≥ O (n ⋅ log(n ))9Быстрая сортировкаQuickSort – рекурсивная Си-функция следующего вида:/* Быстрая сортировка.

Предполагается, что left<right */static void QuickSort (int *a, int left, int right) {/* comp – компаранд, i, j – значения индексов */int comp, tmp, i, j;i = left; j = right;comp = a[(left + right)/2]; //можно a[left] или a[right]/* построение Partition – цикл do-while */do {while (a[i] < comp && i < right)i++;while (comp < a[j] && j > left)j--;if (i <= j) {tmp = a[i];a[i] = a[j];a[j] = tmp;i++, j--;}} while (i <= j);...}10Быстрая сортировкаQuickSort – рекурсивная Си-функция следующего вида:static void QuickSort (int *a, int left, int right) {.../* продолжение сортировки, если не все отсортировано */if (left < j)QuickSort (a, left, j);if (i < right)QuickSort (a, i, right);}Программа быстрой сортировки.void qsort (int *a, int n) {QuickSort (a, 0, n - 1);}Нужно, чтобы значение компаранда было таким, чтобы он попалв середину результирующей последовательности. Мы пытаемсяугадать, какой из элементов массива имеет такое значение.

Чем11лучше мы угадаем, тем быстрее выполнится алгоритмБыстрая сортировкаПокажем, что цикл do-while действительно строит нужное намразбиение массива a[].(1)В процессе работы цикла индексы i и j не выходят запределы отрезка [left, right], так как в циклах whileвыполняются соответствующие проверки.(2)В момент окончания работы циклаdo-while j ≤ right,так как части разбиения не могут быть пустыми: хотя быодин элемент массива a[] (в крайнем случае a[right])содержится в правой части разбиения.(3)Аналогично, в момент окончания работы циклаdo-while i ≥ left.(4)В момент окончания работы цикла do-while любойэлемент подмассива a[left..j] не больше любогоэлемента подмассива a[i..right], что очевидно.12Быстрая сортировкаРабота цикла do-while на примере: 5 3 2 6 4 1 3 7.Пусть в качестве первого компаранда выбран первыйэлемент массива – 5 (a[left]).Во время первого прохода цикла do-while послевыполнения обоих циклов while получим:(5) 3 2 6 4 1 {3} 7;(в круглых скобках элемент с индексом i,в фигурных – элемент с индексом j).Поскольку i < j, элементы, выделенные скобками,нужно поменять местами (оператор if):3 (3) 2 6 4 {1} 5 7;В результате второго прохода цикла do-while получим:до обмена 3 3 2 (6) 4 {1} 5 7;после обмена 3 3 2 1 ({4}) 6 5 7;Третий проход лишь увеличивает i.Теперь массив a состоит из двух подмассивов3 3 2 1 4 и 6 5 7причем i = 5, j = 4.и нужно рекурсивно применить метод к этим13подмассивам.Быстрая сортировкаПри выборе компаранда можно брать первый элемент, значениекоторого больше значения следующего элемента.

Длярезультирующих подмассивов из примера компарандызаключены в квадратные скобки:3 [3] 2 1 4;[6] 5 7.Если f(n) и g(n) – некоторые функции, то запись g(n) = Θ(f(n))означает, что найдутся такие константы c1, c2 >0 и такое n0,что для всех n ≥ n0 выполняются соотношения0 ≤ c1f(n) ≤ g(n) ≤ c2f(n).т.е. при больших nf(n) хорошо описывает поведение g(n).14Быстрая сортировкаОценка времени выполнения алгоритма QuickSort.(1)Время выполнения цикла do-whileΘ(n), где n = right – left +1.(2)для алгоритма QuickSort максимальное (наихудшее)время выполнения Tmax(n) = Θ(n2).Наихудшее время: при каждом Partition массив длины nразбивается на подмассивы длины 1 и n – 1.(2Д)Для Tmax(n) имеет место соотношениеTmax(n) = Tmax(n – 1) + Θ(n).Очевидно, что Tmax(1) = Θ(1).Следовательно,Tmax(n) = Tmax(n – 1) + Θ(n) =nn∑ Θ( k ) = Θ( ∑ k ) =k =1(3)k =1n⋅(n – 1)/2 = Θ(n2).Если исходный массив a отсортирован в порядкеубывания, время его сортировки в порядке возрастанияс помощью алгоритма QuickSort будет Θ(n2).15Быстрая сортировкаОценка времени выполнения алгоритма QuickSort.Минимальное и среднее время выполнения алгоритмаQuickSortTmean(n) = Θ(n⋅log n)с разными константами: чем ближе разбиение наподмассивы к сбалансированному, тем константыменьше.(4Д)Доказательство использует теорему о рекуррентныхоценках [1](5)Рекуррентное соотношение для минимального(наилучшего) времени сортировки Tmin(n) имеет видTmin(n) = 2⋅Tmin(n/2) + Θ(n),так как минимальное время получается тогда, когда накаждом шаге удается выбрать компаранд, который делитмассив на два подмассива одинаковой длины n/2.Применяя ту же теорему, получаем Tmin(n) = Θ(n⋅log n).[1] Т.

Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.М.: МЦНМО, 1999. ISBN 5-900916-37-5, с. 66 – 73.16(4)Быстрая сортировкаОценка времени выполнения алгоритма QuickSort.(6)Рекуррентное соотношение для T(n) в общем случае,когда на каждом шаге массив делится в отношенииq:(n – q), причем q равновероятно распределено между1 и n, также можно решить и установить, чтоT(n) = Θ(n⋅log n) (та же книга, с.160 – 164).17Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 181Формальная постановка задачи поиска по образцуДаны текст – массив T[N] длины N и образец – массив P[m]длины m ≤ N, где значениями элементов массивов T и Pявляются символы некоторого алфавита A.Говорят, что образец P входит в текст T со сдвигом s,если 0 ≤ s ≤ N – m и для всех i = 1, 2, …, m T[s + i] = P [i].Сдвиг s(T, P) называется допустимым, если P входит в T сосдвигом s = s(T, P) и недопустимым в противном случае.Задача поиска подстрок состоит в нахождении множествадопустимых сдвигов s(T, P) для заданного текста T и образца P.2Формальная постановка задачи поиска по образцуТерминология.

Пусть строки x, y, w ∈ A*, ε ∈ A* - пустая строка;|x| - длина строки x;xy – конкатенация строк x и y; |xy| = |x| + |y|;x = wy -> w – префикс (начало) x (обозначение w  x );x = yw -> w – суффикс (конец) x (обозначение w  x );если w – префикс или суффикс x, то |w| ≤ |x|;отношения префикса и суффикса транзитивны.Для любых x, y ∈ A* и любого a ∈ A соотношения x  yи xa  ya равносильны.Если S = S[r] – строка длины r, то ее префикс длины k, k ≤ r будетобозначаться Sk = S[k]; ясно, что S0 = ε, Sr = S.3Лемма (о двух суффиксах)Пусть x, y и z – строки, для которых x  z и y  z .Тогда если |x| ≤ |y|, то x  y , если |x| ≥ |y|, то y  x ,если |x| = |y|, то x = y .xxzxzzyyxyxxy|x| ≤ |y|y|x| ≥ |y|y|x| = |y|4Простой алгоритмПроверка совмещения двух строк: посимвольное сравнениеслева направо, которое прекращается (с отрицательнымрезультатом) при первом же расхождении.Оценка скорости сравнения строк x и y – Θ(t + 1), где t – длинанаибольшего общего префикса строк x и y.for (s = 0; s <= n – m; s++) {for (i = 0; i < m && P[i] == T[s + i]; i++);if (i == m)printf ("%d\n", s);}Время работы в худшем случае Θ((n – m + 1)⋅m) ~ Θ(nm).Причина: информация о тексте T, полученная при проверкеданного сдвига s, никак не используется при проверкеследующих сдвигов.

Например, если для образца dddcсдвиг s = 0 допустим, то сдвиги s = 1, 2, 3, недопустимы,так как T[3] == с.5Алгоритм Кнута – Морриса – Пратта. ИдеяПрефикс-функция, ассоциированная с образцом P, показывает,где в строке P повторно встречаются различные префиксы этойстроки. Если это известно, можно не проверять заведомонедопустимые сдвиги.Пример.

Пусть ищутся вхождения образца P = a b a b a c a втекст T. Пусть для некоторого сдвига s оказалось, что первые qсимволов образца совпадают с символами текста. Значит,символы текста от T[s+1] до T[s+q] известны, что позволяетзаключить, что некоторые сдвиги заведомо недопустимы.6Алгоритм Кнута – Морриса – Пратта. ИдеяПусть P[1..q] = T[s+1..s+q]; каково минимальное значение сдвигаs′ > s, для которого P[1..k] = T[s′+1..s′+k], где s′+k = s+q?Число s′ - минимальное значение сдвига, большего s,которое совместимо с тем, что T[s+1..s+q] = P[1..q].Следовательно, значения сдвигов, меньшие s′ ,проверять не нужно.Лучше всего, когда s′ = s+q, так как в этом случае ненужно рассматривать сдвиги s+q-1, s+q-2, …, s+1.Кроме того, при проверке нового сдвига s′ можно нерассматривать первые его k символов образца: онизаведомо совпадут.Чтобы найти s′, достаточно знать образец P и число q:T[s′+1..s′+k] – суффикс Pq, поэтому k – это наибольшее число,для которого Pk является суффиксом Pq.

Характеристики

Список файлов лекций