Нахождение среднего случая сложности алгоритма

У меня есть алгоритм последовательного поиска несортированному массива:Нахождение среднего случая сложности алгоритма

SequentialSearch(A[0..n-1],K) 

i=0 
while i < n and A[i] != K do 
    i = i+1 
if i < n then return i 
else return -1

Где мы имеем входной массив A[0...n-1] и поиск ключа K

Я знаю, что худший случай - n, потому что нам нужно будет искать весь массив, следовательно, n пунктов O(n)

Я знаю, что лучший случай - 1, поскольку это будет означать первый предмет, ch - тот, который мы хотим, или массив имеет все те же элементы, в любом случае это O (1)

Но я понятия не имею, как рассчитать средний случай. Ответ мой учебник дает это:

= (p/n)[1+2+...+i+...+n] + n(1-p)

есть общая формула, я могу следовать, когда я вижу алгоритм, как этот, чтобы вычислить его?

ИЗОБРАЖЕНИЯ НИЖЕ Textbook example

источник

2017-02-17 o4o42o3k2o

EDIT: Проверьте изображение я добавил который показывает решение, я просто не знаю, как они получают его. – o4o42o3k2o

https://en.wikipedia.org/wiki/Linear_search –

@mitch пшеница, точно. Мой ответ ниже соответствует записи, с которой вы связались. Видимо, кто-то импульсивно проголосовал за это, потому что это перевернулось. –

Вы должны были бы рассмотреть случаи ввода, то, как классы эквивалентности ввода, которая зависит от контекста алгоритма. Если ни одна из этих вещей не известна, то, предполагая, что вход представляет собой массив случайных чисел, средний случай, вероятно, будет O (n). Это потому, что, грубо говоря, вы не можете доказать, насколько часто ваш запрос будет найден в массиве из N целочисленных значений в диапазоне от ~ -32k до ~ 32k.

источник

2017-02-17 01:34:23

Я добавил картинку, она не может быть O (n), я думаю, я просто не уверен в процессе получения среднего случая. – o4o42o3k2o

Правильно, но как учебник получает этот ответ? Я не понимаю всех этих сумм, откуда они берутся? Если и когда я пройду проверку на что-то подобное, мне нужно будет воспроизвести все, что они там делают .. и я не знаю, как это сделать. – o4o42o3k2o

Это путаное обозначение наверняка. Я хотел бы взглянуть на другие источники, чтобы понять, как это связано с вероятностью, а затем попытаться разобрать текстовую нотацию. –

= (p/n)[1+2+...+i+...+n] + n(1-p)

p здесь есть вероятность ключа поиска, найденный в массиве, так как у нас есть n элементов, мы имеем p/n как вероятность нахождения ключа на конкретном индексе в n. Мы по существу делаем средневзвешенное значение, как на каждой итерации, мы верим в 1 сравнение, 2 сравнения и до n сравнения. Поскольку мы должны учитывать все входы, вторая часть n(1-p) сообщает нам вероятность ввода, которая не существует в массиве 1-p. и при поиске по всему массиву он принимает n.

источник

2017-02-17 02:40:15

Более формально, пусть X - дискретная случайная величина, обозначающая количество элементов массива A, которые необходимо отсканировать. Элементы n и так как все позиции одинаково вероятны для генерируемых случайных входов, X ~ Uniform(1,n), где X = 1,..,n, учитывая, что ключ поиска находится в массиве (с вероятностью p), в противном случае все элементы должны быть отсканированы, с X=n (с вероятностью 1-p).

Следовательно, P(X=x)=(1/n).p.I{x<n}+((1/n).p+(1-p)).I{x=n} для x = 1,..,n, где I{x=n} функция индикатора и будет иметь значение 1 тогда и только тогда x=n иначе 0.

Средняя временная сложность алгоритма - это ожидаемое время выполнения алгоритма, когда вход представляет собой произвольную последовательность.По определению,