В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 6
Текст из файла (страница 6)
В силу пирамидального свойства, вершина пирамидысодержит максимум массива. Поменяем местами его и последний элемент массива. Теперь мысленно исключимa015из дерева последний элемент массива (ведь он уже встал на своё законное место) и просеем вниз новый кореньнового дерева (т.
е. дерева без последнего элемента). Тогда наверх опять всплывёт максимум. Так будем делать,пока все элементы не встанут на своё место. Очевидно, этот процесс займёт не более n log2 n операций, посколькув худшем случае мы будем просеивать каждый из n элементов массива за log2 n операций.Подытожим сказанное. Построение пирамиды занимает не более O(n log2 n) операций, сортировка — тожене более O(n log2 n). Значит, и весь процесс займёт не более O(n log2 n), причём на многих массивах он будетработать ещё быстрее за счёт того, что просеивание не всегда занимает log2 n операций.Осталось показать, что всю древесную структуру можно поддерживать без всяких накладных расходов. Действительно, если родитель семьи имеет индекс i, то его дети имеют индексы 2i + 1 и 2i + 2. Отсюда следует,что вся древесная структура — лишь наглядное представление алгоритма: зная номер родителя, мы без труданаходим его детей, а зная индекс ребёнка i, по формуле i−1можно вычислить индекс родителя.
А посколь2ку никаких операций, кроме сравнения и обмена элементов в семье, нам по существу делать не нужно, весьалгоритм легко переписывается на языке указанных выше формул.3.5. Сортировки за линейное времяВ начале раздела об эффективных сортировках мы доказали теорему, которая показывает, что в общемслучае невозможно отсортировать массив быстрее, чем за O(n log2 n) операций. Однако, если наложить намассив некоторые ограничения, то можно построить более эффективные алгоритмы.3.5.1. Сортировка подсчётомПусть ai ∈ Z и 0 6 ai < p, где p ∈ N. Заведём массив b из p элементов, заполненный нулями, а затемвыполним следующую операцию:for (int i = 0; i < n; i++) b[a[i]]++;Тогда в массиве b элемент b[k] будет содержать количество элементов k в массиве a.
После этого можнозаполнить массив a отсортированным массивом:int pos = 0;for (int k = 0; k < p; i++)for (int i = 0; i < b[k]; i++, pos++) a[pos] = k;Ясно, что трудоёмкость такого алгоритма составляет O(n + p), правда, требуется дополнительная память.Существует модификация этого алгоритма, требующая ещё больше памяти. Она применяется, когда мыхотим сохранить порядок одинаковых элементов массива. Заведём массив c из n элементов и массив d из pkPэлементов. В массив d сложим частичные суммы массива b, т. е. dk =bi .
Далее выполним сортировку:i=0for (int i = 0; i < n; i++){int e = a[i];c[d[e]-b[e]] = e;b[e]--;}Легко видеть, что при такой сортировке одинаковые элементы перекладываются в массив c именно в томпорядке, в котором они были в массиве a. Фактически алгоритм вычисляет точную позицию для очередногоэлемента ai , используя количество элементов каждого сорта.Такая реализация алгоритма является избыточной с точки зрения памяти, и её можно оптимизировать.
Однако в ней гораздо лучше прослеживается логика работы. Заметим, что в алгоритме фактически используютсяk−1Pтолько числа вида sk = dk − bk и декремент bk . Но их можно получить и непосредственно: sk =bi , значит,i=0вычислив массив b, можно сразу «испортить» его, заполнив числами sk , а декремент bk заменить на инкремент sk . Тогда массив b будет содержать на k-м месте номер позиции, с которой в отсортированном массивеначинается серия чисел k.
Приведём оптимизированный вариант кода:int s = 0;for (int i = 0; i < p; i++){int t = b[i];b[i] = s;s += t;}for (int i = 0; i < n; i++)// интегрирование массива <b>// заполнение массива <c> отсортированными элементами <a>16{int e = a[i];c[b[e]] = e;b[e]++;}Такой алгоритм может быть применён для сортировки списка имён и фамилий сначала по фамилиям, затемпо именам: сначала сортируем любым алгоритмом по именам, а затем применяем наш алгоритм для сортировкипо фамилиям. При этом алфавитный порядок имён не изменится.Рассмотрим ещё один вариант сортировки, который при ограничениях на максимум элемента массива даётповышение эффективности.3.5.2. Поразрядная быстрая сортировкаПусть нам надо отсортировать неотрицательный массив целых чисел, не превосходящих p. Тогда их двоичнаязапись содержит d = ⌈log2 p⌉ цифр.
Применив сортировку к столбику из самых старших бит, мы приведём массивк виду0|X.....X|. . .0|X.....X|1|X.....X|. . .1|X.....X|Затем рекурсивно применим сортировку к блоку, в котором на первом месте стоят 0, и к блоку, в которомна первом месте стоят 1. Получим массив вида00|X....X|. . .00|X....X|01|X....X|. . .01|X....X|10|X....X|. . .10|X....X|11|X....X|.
. .11|X....X|Так будем сортировать, пока не дойдём до последнего разряда, и тогда массив станет упорядоченным повозрастанию. Ясно, что если на сортировку блока из n элементов тратить не более n операций, то за nd операцийможно отсортировать весь массив. Такой алгоритм может быть полезен, когда n ≫ d, поскольку тогда это будетбыстрее, чем, например, быстрая сортировка.4. Сжатие данныхТермин «сжатие данных» означает представление данных в более компактной форме. Сама постановка задачи предполагает, что либо данные сами по себе, либо имеющийся способ их представления, обладают определенной информационной избыточностью для конкретной решаемой задачи. Устранение этой избыточности ипозволяет сжать данные. Таким образом, идеология сжатия (и, следовательно, алгоритмы) существенно определяются тем, как мы трактуем понятие избыточности в том или ином случае. Обычно различают два подхода.Первый из них, называемый сжатием без потерь, предполагает, что данные некоторым образом закодированыи фактически представляют собой последовательность битов.
Целью сжатия является получение некоторойдругой, более короткой последовательности битов, по которой можно однозначно восстановить исходную.Другой подход — сжатие с потерями — принимает во внимание смысл данных и огрубляет эти данные дотого предела, который ещё имеет смысл для конкретной задачи обработки этих данных. Типичными примерами подобного подхода является сжатие изображений фотографического качества (где некоторое уменьшениеразрешающей способности практически не ухудшает качества картинки) или аппроксимация оцифрованныхсигналов приближающими функциями с некоторой погрешностью.Далее мы будем рассматривать только алгоритмы сжатия без потерь, поскольку они не носят в себе отпечаткаконкретного происхождения данных и могут применяться к данным любых типов. Как правило, мы будемсчитать, что биты данных можно объединить в группы некоторой фиксированной длины, следовательно, навход алгоритма сжатия подается некоторая последовательность таких групп.
Наиболее разумное значение длятакой группы — 8 бит, т. е. мы говорим о входной последовательности байтов.174.1. Алгоритм группового кодирования (RLE)Название алгоритма происходит от слов Run Length Encoding, что можно приблизительно перевести как«кодирование длин промежутков». Идея алгоритма чрезвычайно проста — вместо последовательности подрядидущих одинаковых байтов передавать на выход только длину последовательности и один такой байт. Если жево входном потоке нет постоянных повторяющихся цепочек, то кодирование не производится.
Более формальноеописание алгоритма может выглядеть так:Разобьём входной поток на цепочки байт по следующим критериям:• длина каждой цепочки не превосходит 127 байт;• цепочка целиком состоит из одинаковых байтов и имеет длину больше 1 либо не имеет в себе двух одинаковых соседних байтов.Каждой цепочке сопоставим выходной код по следующим правилам:• для постоянных цепочек длины n выходным кодом являются два байта, где старший бит первого байтаравен 0, а оставшиеся 7 бит кодируют число n, второй байт кода равен байту, составляющему даннуюцепочку;• для непостоянных цепочек длины n выходным кодом являются n + 1 байт, где старший бит первого байтаравен 1, а оставшиеся 7 бит кодируют число n, далее идут n байт исходной цепочки.Очевидно, что полученный код может быть легко преобразован обратно в исходную последовательность.Для этого нужно взять значение n, представленное в младших семи битах первого байта, проанализироватьстарший бит, и в зависимости от значения этого бита либо повторить n раз следующий байт, либо взять безизменения следующие n байт кода.Нетрудно оценить наилучшую и наихудшую степень сжатия.
В том случае, когда файл содержит повторяющиеся группы из 127 одинаковых байт, мы получаем максимальное сжатие с коэффициентом 127/2. Если вфайле нет ни одной повторяющейся группы, то на каждые 127 байт мы получаем один дополнительный байт,т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
