Блог

Нам дается двоичный массив, содержащий либо n нулей, либо нули пола(n/2) и потолка(n/2).

Мы хотим решить, включает ли массив единицы.

В. Предложите случайный алгоритм, который имеет временную сложность O(1) и дает правильный ответ с вероятностью не менее 3/4. Алгоритм может дать неправильный ответ, но не более чем для 1/4 возможных входных данных.

Я хотел бы получить некоторое представление о том, как решить этот вопрос.

Проверьте случайный элемент в массиве:

1. Если item == 0 вернуть первую возможность (n нулей)
2. Если item == 1 вернуть вторую возможность (n/2 нуля и n/2 единицы)

Давайте посмотрим, что происходит: единственная возможность дать неправильный ответ-это когда у нас есть вторая возможность, но мы получаем item == 0 и отвечаем на первую возможность. Условная (вторая возможность) вероятность равна

 p = 1/2  

Если мы проверим два случайных элемента

 p = 1/4 (two items are zeroes)  

Если мы проверим три случайных элемента

 p = 1/8 (three items are zeroes)  

Теперь давайте вычислим байесовскую вероятность неправильного ответа, пусть

 P0 - probability of the 1st (all zeroes) outcome P1 - probability of the 2nd (half zeroes, half ones) outcome  Perror = P1 * p / (P0   P1) lt;= 1/4  

Или

 P1 * p / (P0   P1) lt;= 1/4  p lt;= (P0   P1) / 4 / P1  p lt;= P0 / (4 * P1)   1/4  

Из наихудшего случая P0 = 0 ( P1 = 1 ) мы получаем условие для p :

 p lt;= 1/4  

Пока все хорошо, мы должны проверить два элемента случайного массива, а затем

• Если оба пункта 0 совпадают , мы отвечаем «Все нули».
• Если какой-либо пункт есть 1 , мы отвечаем «Половина нулей, половина единиц».