Вероятностнй анализ алгоритма с двумя переменными

Question

Столкнулся с проблемой при вероятностном анализе алгоритма, а именно с индикаторной функцией. Но, начну сначала: есть массив чисел A, все числа в нём разные и заданы случайно (интервал чисел неизвестен). Нужно написать алгоритм на псевдокоде, который будет возвращать все пары чисел A[i]+A[j] mod 2 = 0, при условии, что i<j. C алгоритмом у меня проблем не возникло, т.к. нет никаких ограничений на его эффективность, сделал такой вариант:

procedureDisjunktePaare(Array)%(Input - Array, Output - Array of Paars) 
Result = ([])
for i = 1 to Array.size-1 do
   while j=i+1 to Array.size do
       if Array.i+Array.j mod 2 == 0 then 
            append(Result, (Array.i, Array.j))
       j++  
   i=i++
return Result

Алгоритм простой как валенок: i начинается с первого элемента массива, заканчивается на предпоследнем. j начинается с i+1, заканчивается последним элементом. Во вложенном цикле проверяем условие и если оно выполняется - просто добавляем пару в список Result. Когда цикл For проходит полностью - возвращаем результат.

Очевидно, что в самом худшем случае у нас будет (n-1)(n-1) операций (в случае если все элементы в массиве отсортированы по возрастающей и все они удовлетворяют условию для попадания в список. В данном случае мы делаем n-1 итераций в цикле for, а в цикле While мы делаем в первый раз n-1 поторений, затем n-2 итд вплоть до одной единственной итерации для последней итерации цила for). Но вероятность такого исхода не очень велика. Поэтому для ожидаемого времени надо применить вероятностный анализ. С этим чуть сложнее.

Я понимаю, что надо использовать как советует Кормен индикаторную функцию. Но я не очень понимаю, как задать её для условия, что одна переменная будет меньше другой. Но каково тогда E[Xi]? Насколько я понимаю, я должен отталкиваться от следующего: Xi=1, если A[i]+A[j] mod 2 = 0; 0 - во всех остальных случаях. Для этого либо оба элемента должны быть чётные, либо оба элемента должны быть нечётные. Т.к. у нас предполагается полный рандом, то вероятность любого из этих событий 1/4, что делает суммарную вероятность 0.5. Но мне кажется, что такой подход абсолютно наивен и ошибочен.

Answer 1

Вообще ваш алгоритм при любых входных данных сделает ~n^2/2 сравнений (1+2+ ... +(n - 1)). Но кажется вы спрашиваете, какая средняя величина результирующего массива в конце алгоритма.

Пусть F(n, k) - количество пар в результирующем массиве, если во входных данных k четных чисел и n - k нечетных чисел. Очевидно, что F(x) = k * (k - 1) / 2 + (n - k) * (n - k - 1) / 2. Тогда мат. ожидание размера результирующего массива будет выражаться следующей функцией:

И если вы верите вольфраму, то результат будет следующим:

Это, конечно, не вероятностный анализ, но как мне кажется, мой способ даже проще и точнее.

Answer 2

Немного посидев и подумав, я нашёл то, что искал. Оставлю отмеченным верным ответ от EzikBro, но искомое решение было следующим:
Пусть индикаторная переменная Х будет следующей:

Тогда:

Как я уже писал в вопросе, наше условие работает когда оба сверяемых числа чётные или оба нечётные. Вероятность каждого из этих событий 1/4. Вероятность, что выпадет одно из этих событий - 1/2. В этом случае

Моей ошибкой было то, что я забыл, что в случае ряда, если у нас константа под знаком, то мы всё равно можем применить формулу (см последнее изображение).

БЛОГ НА HUSL

Вероятностнй анализ алгоритма с двумя переменными

Ответы (2 шт):