Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике Как упорядочить выборку?Нас в дальнейшем будут интересовать выборки, упорядоченные по значениям их элементов. Условимся для определенности считать все элементы выборки сравнимыми между собой попарно, но несовпадающими по значениям. Это даст возможность говорить о совершенном строгом порядке. Для нумерации упорядоченных элементов будем использовать числа натурального ряда Как мы действуем, упорядочивая последовательность чисел? Такой вопрос может поставить человека в тупик, во всяком случае, не подумав, не перечислишь операции, которые приходится проделать, превращая ряд чисел 2, 5, 1, 4, 3, 8 в ранжированную последовательность 1, 2, 3, 4, 5, 8. Да и нужно ли Формализовать процедуру упорядочения, однако, необходимо, если мы хотим, чтобы эту работу выполняла Сортировка выбором. Сортировка попарной перестановкой. При первом просмотре каждое значение х, сравнивается с наибольший элемент попадает в положение Сортировка объединением именно это и использует. Элементы выборки соединяются попарно, причем меньший элемент ставится на первое место. Затем эти упорядоченные пары объединяются в четверки, четверки ранжируются и объединяются в восьмерки и т. д. Метод наиболее эффективен, когда объем выборки равен степени двойки: При Чем оплачивается такая экономия? Метод сортировки объединением требует запоминания промежуточных групп элементов — нужно Эти же алгоритмы или их модификации используются, когда над выборкой требуется совершить какую-либо иную, связанную с упорядочиванием операцию — выбор наименьшего или наибольшего ее члена, элемента, занимающего среднее положение или имеющего определенный номер в упорядоченном ряду. Нужно сказать, что в попытках формализовать процедуру упорядочения были перепробованы различные методы. Так, например, если смотреть на логическую операцию дизъюнкцию как на выбор максимального значения, а конъюнкции придать смысл выбора минимального значения, то при помощи логических дизъюнктивно-конъюнктивных форм можно описать и процесс ранжирования, и другие процедуры сортировки [4]. Покажем это «а примере выбора срединного значения — медианы выборки, предположив для простоты, что число членов выборки нечетио и что равных значений в выборке нет. Итак, если объем выборки нечетен,
Здесь Величины Количество Пусть
Или так:
В рассмотренных алгоритмах сортировки мы оперировали с выборками значений А как производить ранжирование выборки, состоящей не из чиаел, а из объектов Очевидный путь — измерить Возможен и другой случай, когда параметр объекта нечем измерить из-за отсутствия измерительного прибора. Так обстоит дело, например, с определением интенсивности аапаха. Однако мы видели, что алгоритмы сортировки используют значения Действительно, если речь идет о «силе игры» — параметре неизмеримом, то процедура типа турнира, основанная на парных взаимодействиях участников, дает материал именно для ранжирования их по значениям неизмеримого параметра. Другой способ упорядочения — экспертные оценки — особенно эффективен при вынесении решений о парных соотношениях. Наконец, для непосредственного сравнения объектов могут быть использованы специальные устройства сравнения — компараторы. Так, при ранжировании по весу компараторами могут быть рычажные весы без гирь. Электрические сигналы могут сравниваться между собой, например, на мостовых схемах и т. д.
|
1 |
Оглавление
|