Случайный массив
Cтраница 1
Случайный массив в целом представляет собой статистически однородное множество элементов, и поэтому мы можем разными способами сформировать в нем п / 2 пар для сравнения с информационной ценностью, равной единице. После выполнения всех п / 2 сравнений получаем два статистически однородных подмножества по п / 2 элементов в каждом: 1) подмножество элементов, оказавшихся большими, и 2) подмножество элементов, оказавшихся меньшими. [1]
Пусть задан случайный массив из п элементов. [2]
 |
Блок-схема оператора слияния. [3] |
Пусть в случайном массиве выделены два подмассива А и В. [4]
 |
Блок-схема алгоритма метода вставки ( вариант № 2. [5] |
Оценим величину пу для случайного массива. [6]
Как было отмечено в главе 2, из случайного массива можно выбрать лишь ( п / 2) Iog2n пар статистически эквивалентных элементов, обеспечивающих наибольшую информационную ценность результата сравнения. Рассмотрим случай, когда на выбор пар для сравнения наложено простое дополнительное условие: на любом этапе из каждой статистически однородной последовательности для сравнения выбираются элементы со смежными в этой последовательности номерами. [7]
 |
Характеристика изменения относительной эффективности оператора слияния в зависимости от числа объединяемых под-массивов k. [8] |
Последовательное использование процедуры слияния отдельных упорядоченных подмассивов для полного упорядочения случайного массива приводит к построению процедуры, состоящей из ряда отдельных этапов, причем для первого этапа исходные сливаемые подмасси-вы состоят из отдельных объектов, в то время как последний этап упорядочивает все объекты данного массива. [9]
Блок-схема данной процедуры приведена на рис. 3.9. В блоках 1, 2, 3, 4, 5 в цикле по номеру позиции исходного случайного массива i происходит образование упорядоченных пар элементов. Блок 1 задает начальное значение индексу i, параметру k и величине z, в блоке 2 производится проверка упорядоченности пар соседних элементов, а в блоке 3 производится их обмен при обнаружении инверсии. [10]
Для случайного массива из п элементов количество таких подмножеств равно п, а размер каждого подмножества равен одному элементу. Для упорядоченного массива количество таких подмножеств равно единице, а размер подмножества равен размеру всего массива. Отсюда следует, что упорядочение массива можно выполнить путем последовательного уменьшения количества внутренне упорядоченных подмножеств. Процедуры упорядочения, распадающиеся на отдельные этапы, целью которых является уменьшение количества внутренне упорядоченных подмножеств при соответствующем увеличении их размера, носят название процедур внутреннего упорядочения. [11]
Для случайного массива из п элементов количество таких подмножеств равно единице, а размер подмножества равен размеру всего массива. Для упорядоченного массива количество таких подмножеств равно п, а размер каждого из них равен единице. [12]
Наиболее проста организация процедуры при использовании двойного резерва памяти. В этом случае выделяют два поля позиций равного объема ( по п позиций каждое), на одном из которых размещается исходный случайный массив. Без ограничения общности будем считать, что есть некоторое общее поле позиций М, на котором, начиная с позиции А и кончая позицией А - - п - 1, располагается исходный случайный массив, а последовательность позиций, начинающаяся с позиции В и заканчивающаяся позицией В - - п - 1, представляет резервное поле, используемое в процессе упорядочения. Общая процедура в этом случае будет использовать оператор слияния двух упорядоченных подмассивов, аналогичный описанному выше. [13]
Так как все возможные значения признака равновероятны, то равновероятно и любое из двух возможных значений ( 0 или 1) каждого разряда в любом элементе случайного массива. [14]
Наиболее проста организация процедуры при использовании двойного резерва памяти. В этом случае выделяют два поля позиций равного объема ( по п позиций каждое), на одном из которых размещается исходный случайный массив. Без ограничения общности будем считать, что есть некоторое общее поле позиций М, на котором, начиная с позиции А и кончая позицией А - - п - 1, располагается исходный случайный массив, а последовательность позиций, начинающаяся с позиции В и заканчивающаяся позицией В - - п - 1, представляет резервное поле, используемое в процессе упорядочения. Общая процедура в этом случае будет использовать оператор слияния двух упорядоченных подмассивов, аналогичный описанному выше. [15]
Страницы: 1 2