последовательный поиск

Question

Я читаю алгоритмы на С ++ Роберта Седвика, это было упомянуто следующим образом

Последовательный поиск в упорядоченной таблице проверяет N чисел для каждого поиска в худшем случае и около N / 2 чисел для каждого поиска в среднем.

Этот результат следует из предположения, что поиск с одинаковой вероятностью завершится через любой из N + 1 интервалов, определенных N числами в таблице, что сразу приводит к выражению (1 + 2 + 3 +4 + ... + N + N) / N = (N + 3) / 2.

Может ли кто-нибудь помочь мне понять, как мы пришли к вышеприведенному выражению, т. Е. Как получается N + 3/2?

Answer 1

Сумма первых N целых чисел (1 + 2 + 3 + ... + N) = (N + 1) N / 2

Простой способ убедиться в этом - выписать сумму вперед ив обратном направлении:

1 + 2 + 3 + ... + (N-2) + (N-1) + N

N + (N-1) + (N-2)+ ... + 3 + 2 + 1

и затем суммируем соответствующие термины:

(N + 1) + (N + 1) + (N + 1) + ... +(N + 1) = N (N + 1)

разделить на 2, чтобы получить результат (N + 1) N / 2

Затем (1 + 2 + 3 + ...+ N + N) / N = ((N + 1) N / 2 + N) / N = (N + 3) / 2

Примечание : Существует история ознаменитый гениальный математик Карл Фридрих Гаусс (1777-1855), когда он был мальчиком.Его школьный учитель поставил перед классом задачу сложения чисел от 1 до 100, полагая, что это займет их некоторое время.Но Гаусс нашел сумму 5050 всего через несколько минут, используя рассуждения выше.Примечание: Гаусс был настоящим гением, но большая часть истории жизни Гаусса была написана Гауссом!

Answer 2

1 + 2 + ... + N + N = N(N+1)/2 + N = N((N+1)/2+1) = N(N + 3)/2