Почему среднее число шагов для поиска элемента в массиве N / 2?

Question

Может ли кто-нибудь объяснить, почему среднее число шагов для поиска элемента в несортированной структуре данных массива равно N / 2?

Answer 1

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

Давайте теперь сделаем довольно сильное предположение, что массив заполнен случайной перестановкой различных значений . Вы можете думать об этом как о выборе произвольного отсортированного списка отдельных элементов, а затем о случайной перестановке. В этом случае предположим, что вы ищете какой-то элемент в массиве, который действительно существует (это доказательство нарушается, если элемент отсутствует). Тогда количество шагов, которое вам нужно сделать, определяется как X, где X - позиция элемента в массиве. Среднее число шагов тогда E [X], которое задается как

E[X] = 1 Pr[X = 1] + 2 Pr[X = 2] + ... + n Pr[X = n]

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

Pr[X = 1] = Pr[X = 2] = ... = Pr[X = n] = 1/n

Так что это выражение задается

E[X] = sum (i = 1 to n) i / n = (1 / n) sum (i = 1 to n) i = (1 / n) (n)(n + 1) / 2
     = (n + 1) / 2

Который, я думаю, является ответом, который вы ищете.

Answer 2

Хотя я думаю, что templatetypedef дает наиболее поучительный ответ, в этом случае есть гораздо более простой.

Рассмотрим перестановки множества {x1, x2, ..., xn}, где n = 2m. Теперь возьмите элемент xi, который вы хотите найти. Для каждой перестановки, где xi встречается с индексом m - k, существует соответствующая перестановка зеркального отображения, где xi встречается с индексом m + k. Среднее из этих возможных индексов просто [(m - k) + (m + k)] / 2 = m = n / 2. Следовательно, среднее значение всех возможных перестановок множества равно n / 2.

Answer 3

Возможно, более простой пример, показывающий, почему среднее значение равно N / 2, таков:

Предположим, у вас есть несортированный массив из 10 элементов: [5, 0, 9, 8, 1, 2, 7, 3, 4, 6]. Это все цифры [0..9].

Поскольку массив не отсортирован (т. Е. Вы ничего не знаете о порядке элементов), единственный способ найти определенный элемент в массиве - выполнить линейный поиск: начать с первого элемента и идти до тех пор, пока вы не найдете что вы ищете, или вы достигли конца.

Итак, давайте посчитаем, сколько операций требуется, чтобы найти каждый элемент. Поиск первого элемента (5) занимает всего одну операцию. Нахождение второго предмета (0) занимает два. Поиск последнего предмета (6) занимает 10 операций. Общее количество операций, необходимых для поиска всех 10 предметов, составляет 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 или 55. Среднее значение равно 55/10 или 5,5.

В «линейном поиске в среднем N / 2 шага» принято считать, что существует ряд предположений. Два самых больших:

1. Элемент, который вы ищете, находится в массиве. Если элемент отсутствует в массиве, то для его определения требуется N шагов. Так что если вы часто ищете элементы, которых там нет, то среднее количество шагов в поиске будет намного выше, чем N / 2.

2. В среднем каждый предмет ищется примерно так же часто, как и любой другой предмет. То есть, вы ищете «6» так же часто, как и «0» и т. Д. Если некоторые элементы просматриваются значительно чаще, чем другие, то среднее число шагов в поиске будет искажено в пользу предметы, которые ищут чаще. Число будет больше или меньше, чем N / 2, в зависимости от расположения наиболее часто просматриваемых элементов.

Answer 4

Рассмотрим простую переформулировку вопроса:

Каким будет предел

lim (i->inf) of (sum(from 1 to i of random(n)) /i)

Или в C:

int sum = 0, i;
for (i = 0; i < LARGE_NUM; i++) sum += random(n);
sum /= LARGE_NUM;

Если мы предположим, что нашrandom имеет равномерное распределение значений (каждое значение от 1 до n с равной вероятностью будет получено), тогда ожидаемый результат будет (1+n)/2.

Answer 5

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