Случайная переменная, область значений которой состоит из счетного числа возможных значений, называется дискретной. Если случайная переменная Y должна принимать одно из значений уй у, . . . , то

Р{У=Уг)> при t=l, 2, . . . ; P{Y=y)=Q для всех остальных значений у. Дискретные распределения этого вида называются массовыми функциями вероятности. Так как переменная Y должна принимать в эксперименте одно из значений у и массовая функция должна удовлетворять отношению

Иначе говоря, с вероятностью 1 (т. е. уверенностью) переменная Y должна равняться одному из допустимых значений (заметим, что Y не может равняться двум разным значениям одновременно). Легко проверить, что данная массовая функция вероятности случайной величины удовлетворяет этому условию.

Математическое ожидание, или среднее значение, или среднее, случайной переменной Y определяется как

Согласно частотной интерпретации вероятности, среднее есть среднее значение случайной величины, во время наблюдения за которой было проведено большое число испытаний. В нашем примере

Я() = Г2(0) + Г2(») + ё(2) + (3)+Й(4)+(5)== = 2.5.

Отметим, что среднее не обязательно принадлежит области значений случайной переменной. Любая функция от случайной переменной G{Y) также является случайной переменной (почему?), математическое ожидание которой задается формулой

E\G{y)\ = G{y)P{Y = y,Y). (1)

Пусть опять переменная X обозначает число свободных процессоров. Если случайная переменная G характеризует дефицит процессоров, т. е. равна числу процессоров, которых нам не хватает для того, чтобы запустить нашу программу, то

3, если Х = 0,

G{X) = <

2, если Х=1, 1, если Х = 2, О, если Х = 3.

Эту формулу часто называют «законом стихийного статистика», так какова нередко вводится как определение (как сделали и мы) «стихийным» статистиком, забывающим, что эта формула может быть выведена.

Согласно равенству (1), получаем

Е [G (X)] = 3 [Р (G = 3)] + 2 [Р (G = 2)] + 1 [Р (G = I)] + О [Р (G = 0)] = : 3 [Р(Х = 0)] + 2 [Р (X = 1)] + 1 [Р (X = 2)] + О [Р (Х3)]=

= 3(i)+2(i) + .(i)

23 32

Польза понятия математического ожидания увеличивается, когда фактическое значение, принимаемое случайной переменной, как правило, мало отличается от среднего. Одной из мер этого отличия является так называемая дисперсия случайной переменной. Пусть Y - случайная переменная со средним [i-E{Y). Тогда дисперсия У, обозначаемая как var [Y], определяется следующим образом:

var [У] = Е [{Y-ir] = 2 (У; -iiY Р (У = f/,-)- (2)

Здесь мы воспользовались формулой математического ожидания для функции от случайной переменной. Стандартное отклонение случайной переменной определяется как

a[F] = Kvar[r]. Для случайной переменной X в нашем примере var [X] = (О- 2.5) (i) + (1 - 2.5)= () + (2 ~ 2.5) (g) +

+ (3 - 2.5) (I) + (4 - 2.5)= (I) + (5 - 2.5)= () = = 1.25. и а[Х]=1.12.

Сортировка методом прямого включения

Этот раздел мы завершим анализом математического ожидания, или среднего, для трудоемкости одного простого алгоритма сортировки.

Сортировка методом прямого включения работает со списком неупорядоченных положительных целых чисел (обычно называемых ключами), сортируя их в порядке возрастания. Это делается примерно так же, как большинство игроков упорядочивают сданные им карты, поднимая каждый раз по одной карте. Покажем работу общей процедуры на примере следующего неотсортированного списка из восьми целых чисел:

27 412 71 81 59 14 273 87.

Отсортированный список создается заново; вначале он пуст. На каждой итерации первое число неотсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список просматривается, начиная с наименьшего числа, до тех пор, пока не находят соответствующее

место для нового числа, т. е. пока все отсортированные числа с меньшими значениями не окажутся впереди него, а все числа с большими значениями - после «его. Следующ,ая последовательность списков показывает, как это делается:

Итерация О Неотсортированный 412 71 81 59 14 273 87

Отсортированный 27 Итерация 7 Неотсортированный 412 71 81 59 14 273 87

Отсортированный 27 4J2 Итерация 2 Неотсортированный 71 81 59 14 273 87

Отсортированный 27 7J 412 Итерация 3 Неотсортированный 81 59 14 273 87

Отсортированный 27 71 S/ 412 Итерация 4 Неотсортированный 59 14 273 87

Отсортированный 27 59 71 81 412

Итерация 5 Неотсортированный 14 273 87

Отсортированный 14 27 59 71 81 412 Итерация 6 Неотсортированный 273 87

* Отсортированный 14 27 59 71 81 273 412 Итерация 7 Неотсортированный S7

Отсортированный 14 27 59 71 81 57 273 412

В следующем алгоритме заводится только один список, и переорганизация чисел производится в старом списке.

Algorithm SIS (Сортировка Прямым ек/гтениелг).Отсортировать на старом месте последовательность целых чисел /(1), /(2), . . . , I {N) в порядке возрастания. ,

Шаг 1. [Основная итерация]

For J -е- 2 to Л? do through шаг 4 od; and STOP. Шаг 2. [Выбор следующего целого] Set K-I{J)\ and L <- J-1.

Шаг 3. [Сравнение с отсортированными целыми] While К<. <1{Ц AND L>1 do set /(L+1)/(L); and L-e-L-l od.

Шаг 4. [Включение] Set /(1+1)ч-/С.

Блок-схема алгоритма SIS приводится на рис. 2.4.1.

Оценим теперь среднее число сравнений необходимых для сортировки случайных данных методом прямого включения. В качестве упражнения мы оставляем определение максимального и минимального числа требуемых сравнений.

Пусть N - число подлежащих сортировке ключей. Рассмотрим i-й проход по циклу на шаге 1. В начале этого прохода первые i ключей неотсортированного списка ранее были правильно упорядочены, и теперь мы собираемся включить (t+l)-H ключ в список из i отсортированных ключей. Имеется i-1 «промежутков» между отсортированными ключами и еще две позиции на концах списка, что в сумме дает