Среднее количество проверок

Question

Рассмотрим набор n элементов, ключевые значения, чьи значения $$ 0, 1, ..., N-1. $$ Пусть $ p (i) (0 ≤ i ≤ n - 1) $ Будьте вероятностью того, что элемент с ключом I искал. Предположим, следующее распределение $ p (i) s $ :

$$ p (i)= \ начать {случаи} 1/2 ^ {N-1}, & \ Text {Если i= 0} \\ 1/2 ^ I, & \ Text {В противном случае} \ end {Cass} $$

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

Каково среднее количество узлов, проверенных для поиска в случайных случаях (элементы в связанном списке, хранятся в случайном порядке) организации), и каковы среднее количество узлов, если отсортировано на основе их уменьшения вероятности (т. Е. С элементом «1», за которым следует элемент «2», то «3» и т. Д., С последним узлом, содержащим элемент «0».) Для больших значений N?

Я знаю, что ответ на первую часть, безусловно, не $ n / 2 $ (поскольку вероятность не то же самое для всех элементов), но я делаю Не совсем знаю гораздо больше, чем это ... но когда сортировалось, я подозреваю, что это должно быть что-то близко к $$ \ sum_ {i= 1} ^ {n - 1} i * { 1/2 ^ {i}} + n * 1/2 ^ {n-1} $$ потому что требуется одно сравнение, чтобы добраться до первого элемента, два ко второму и т. Д., И последний берет Сравнение времен вероятность 0. Я также нашел $$ \ sum_ {i= o} ^ {∞} A * b ^ a= b / (1-b) ^ 2 $ $ Что в этом случае будет равным 2 (b= 1/2), но я понятия не имею, как решать краевые чехол - '0'. : (

Я также в курсе Эта тема У каждого из чисел имели ту же вероятность, и это не совсем одинаково.

Я надеюсь найти ответ на это, так как оно беспокоит меня на некоторое время, и я действительно интересуюсь результатом.
Любой подсказку будет высоко оценен!

Answer 1

Ну давайте посмотрим. Пожалуйста, укажите, если я понял модель проблем неправильно.

Предположим, у нас есть $ n= 5 $ Элементы. Предположим, это отсортировано в пути $ s= [1, 3, 4, 0, 2] $ . Затем используя линейный поиск, мы собираемся с вероятностью $ (1/2) ^ 3 $ имеют 2 шага в нашем поискоре и с вероятностью $ S $ ? Допустим, $ x $ - Количество шагов, необходимых в нашем поисках. Вероятность получить $ x= i $ Шаги эквивалентны запросу поиска элемента $ k \ in \ {0, 1,2, .., N-1 \} $ Давая У нас есть его на $ i $ th. Это $$ p (x= i)=sum_ {k= 0} ^ {n - 1} p (поиск \ для \ k \ | \ \ rement \ k \ \ at \ it \ position) p (\ Element \ k \ is \ at \ it \ position) $$ Тогда мы замечаем, что $ P (элемент \ Element \ k \ is \ at \ aTh \ position)=frac {(n - 1)!} {n!}=frac {1} {n} $ потому что у нас есть элемент в фиксированном положении и $ (N-1)! $ Возможные перестановки для других элементов из общего количества от общего количества $ n! $ возможно Перестановки нашего $ n $ Элементы. Затем мы замечаем, что $ \ sum_ {k= 0} ^ {n-1} p (поиск \ k \ k \ | \ \ rement \ k \ is \ at \ \ положение)= 1 $ . Это означает, что $ p (x= i)=frac {1} {n} $ . Итак, ожидание просто $ \ SUM_ {k= 1} ^ {n} \ frac {k} {n}=frac {n + 1} {2} $ .

Конечно, вторая часть гораздо проще вытекает, это просто $$ e (x | Сортировка \ in \ Уменьшение \ Вероятность)=sum_ {k= 1} ^ {N-1} \ frac {k} {2 ^ {k} {2 ^ {k}} + \ frac {n} {2 ^ {n - 1}} $$ (просто обратите внимание, что элементы будут из < SPAN CLASS= «Математический контейнер»> $ 1 $ $ n - 1 $ а затем элемент $ 0 $ , однако, $ 0 $ может быть предварительным элементом, потому что у него есть те же вероятность, что и $ N-1 $ ). Итак, мы просто рассчитываем ожидание распределения вероятностей, хотя на этот раз не для совместной вероятности, а условного.