Как вы определяете сложность задачи, порожденную случайным броском костей, в лучшем, худшем и среднем случае?

Question

Есть книжка с картинками на 100 страниц. Если кости выбрасываются случайным образом, чтобы выбрать одну из страниц, а затем перебираются, чтобы найти определенное изображение в книге, - как определить сложность этой задачи в лучшем, худшем и среднем случаях?

Предложенный ответ:

лучший случай: изображение найдено в первом броске костей

наихудший случай: изображение найдено на сотом броске костей или изображение не существует

средний случай: изображение найдено после 50 бросков костей (= 100/2)

Допущение: поиск неправильных изображений осуществляется не более одного раза

Answer 1

Учитывая ваше описание проблемы, я не думаю, что ваше предположение (о том, что неправильные изображения только "ищутся" один раз) звучит правильно. Если вы не сделаете это предположение, то ответ будет таким, как показано ниже. Вы увидите, что ответы несколько отличаются от того, что вы предложили.

1. Возможно, вы добились успеха с первой попытки. Поэтому первый ответ: 1.
2. Если бы вам не повезло, вы могли бы продолжать крутить неправильный номер навсегда. Итак, второй ответ - бесконечность.
3. Третий вопрос менее очевиден.

Какое среднее количество рулонов? Вы должны быть знакомы с Geometric Distribution : количеством испытаний, необходимых для достижения одного успеха.

• Определите p как вероятность успешного испытания; р = 0,01.
• Пусть Pr ( x = k ) будет вероятностью того, что первым успешным испытанием будет k th. Тогда у нас будет ( k -1) сбоев и один успех. Так Pr (x = k) = (1- p ) ^ ( k -1) * p. Убедитесь, что это «функция вероятности массы» на вики-странице (левый столбец).
• Среднее геометрическое распределение равно 1 / p , что, следовательно, равно 100. Это среднее количество рулонов, необходимое для поиска конкретной картины.

(Примечание. Нам нужно рассматривать 1 как наименьшее возможное значение, а не 0, поэтому используйте левый столбец таблицы на странице Википедии.)

Answer 2

В худшем случае это не страница, найденная после броска 100 кубиков. Это было бы, если бы ваши кости всегда возвращали разные числа. В худшем случае вы никогда не найдете страницу (так, как вы заявили о проблеме).

К счастью, средний случай не является средним из лучших и худших случаев.

Средний случай:

  1 * (probability of finding page on the first dice roll)
+ 2 * (probability of finding page on the second dice roll)
+ ...

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

Вероятность найти страницу с первой попытки 1/100. Какова вероятность найти его во втором броске костей?

Answer 3

Чтобы проанализировать это, подумайте о том, каковы на самом деле лучшие, худшие и средние случаи. Вам нужно ответить на три вопроса, чтобы найти эти три случая:

1. Какое наименьшее количество рулонов, чтобы найти нужную страницу?
2. Какое наибольшее количество рулонов для поиска нужной страницы?
3. Какое среднее количество рулонов, чтобы найти нужную страницу?

Как только вы найдете первые два, третий должен быть менее хитрым. Если вам нужна асимптотическая запись, а не просто число бросков, подумайте, как изменится ответ на каждый вопрос, если вы измените количество страниц в книге (например, 200 страниц против 100 страниц против 50 страниц).

Answer 4

Вы почти на месте, но (1 + 2 + ... + 100) / 100 не 50.

Может быть полезно заметить, что ваш метод случайного выбора эквивалентен случайному перемешиваниюцелая колода, а затем поиск по ней для вашей цели.Каждая позиция одинаково вероятна, поэтому среднее значение легко вычислить.За исключением того, что вы не выполняете всю эту работу заранее, столько, сколько необходимо для генерации каждого случайного числа и доступа к соответствующему элементу.

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

1006 * Для этого вопроса, есть более чем один способ выбора случайных чисел без повторови не все из них имеют одинаковое время выполнения.

Таким образом, вам потребуется больше подробностей для анализа алгоритма в терминах чего-либо, кроме «количества посещенных страниц».