2
Может ли кто-нибудь объяснить, почему среднее число шагов для поиска элемента в структуре данных несортированного массива составляет N/2?Почему среднее количество шагов для поиска элемента в массиве N/2?
A
ответ
0
Вопрос как указано просто неправильно. Linear search may perform better.
3
Это действительно зависит от того, что вы знаете о числах в массиве. Если они все вычеркнуты из распределения, где вся масса вероятности находится на одном значении, то при ожидании это займет у вас ровно 1 шаг, чтобы найти значение, которое вы ищете, поскольку каждое значение является таким же, например.
Давайте теперь сделаем довольно сильное предположение, что массив заполнен случайной перестановкой различных значений. Вы можете думать об этом как о выборе произвольного отсортированного списка отдельных элементов, а затем произвольно переставляя его. В этом случае предположим, что вы ищете какой-либо элемент в массиве, который фактически существует (это доказательство ломается, если элемент отсутствует). Затем количество шагов, которые вам нужно предпринять, задается X, где 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
Какой, я думаю, ответ, который вы ищете.
+0
Хороший ответ. Я думал о случае, когда сортировка ведра запускалась изначально, и у вас достаточно памяти для хранения всех предметов по порядку, и это займет один шаг. Я не думал о дельте Дирака. –
+0
Если вам нужно более слабое условие, вам просто нужно, чтобы вероятности, что X лежит в [0, N/2) и X, находятся в [N/2, N) равными. –
+0
@ GregS- Это действительно достаточно сильное состояние? Почему эта раскол работает по сравнению с любым другим разделом, который вы могли бы сделать? – templatetypedef
0
Рассмотрим простой переформулировать вопрос:
Что бы предел
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.
1
Возможно, более простой пример, который показывает, почему среднее значение 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 шага», традиционная мудрость делает ряд предположений.Двумя самыми большими являются:
Элемент, который вы ищете, находится в массиве. Если элемент не находится в массиве, то для его определения требуется N шагов. Поэтому, если вы часто ищете предметы, которых там нет, ваше среднее число шагов для каждого поиска будет намного выше, чем N/2.
В среднем каждый элемент выполняется примерно так же часто, как и любой другой предмет. То есть вы ищите «6» так часто, как вы ищите «0» и т. Д. Если некоторые предметы просматриваются значительно чаще, чем другие, тогда среднее количество шагов для поиска будет искажено в пользу которые чаще просматриваются. Число будет выше или ниже N/2, в зависимости от позиций наиболее часто выглядящих предметов.
+0
Но почему среднее значение равно N/2, а не (N + 1)/2? В вашем примере вы суммировали 1 + ... + 10 и делили на число 10, которое 55/10 = 5.5. Предыдущий результат может быть определен (N + 1)/2 = 5,5 ** не ** N/2. – CroCo
+0
@CroCo: Прочитать «N/2» как «приблизительно N/2». Когда мы делаем этот тип вычислений, идея состоит в том, чтобы приблизиться к числу шагов, а не к точному числу.Или см. Ответ Рэйфа, который объясняет это несколько иначе. –
1
Хотя я думаю, что templatetypedef имеет самый поучительный ответ, в этом случае есть гораздо более простой.
Рассмотрим перестановки множества {x1, x2, ..., xn}, где n = 2m. Теперь возьмите некоторый элемент xi, который вы хотите найти. Для каждой перестановки, где xi встречается при индексе m - k, имеется соответствующая перестановка зеркального отображения, где xi встречается при индексе m + k. Среднее значение этих возможных индексов является просто [(m - k) + (m + k)]/2 = m = n/2. Поэтому среднее всех всех возможных перестановок множества равно n/2.
Ну, это на самом деле зависит от алгоритма, который вы будете выполнять, для поиска вашего массива. Пожалуйста, укажите, какой алгоритм вы используете. – deadlock
Мне не хватает очевидного, но если вы проверяете каждый элемент один за другим, пока не найдете тот, который вы ищете, вы, очевидно, проверили N/2 элементов в среднем. (При условии, что вы ищете случайный элемент.) – biziclop
Это удивительно хороший вопрос - я не могу показать, что это правда, поскольку, если вы выберете элементы массива из какого-то странного дистрибутива, это не обязательно даст вам N/2 шага в среднем. – templatetypedef