algorithm - 顺序搜索分析

Question

我正在阅读 Robert Sedwick 的 C++ 算法，其中提到如下

有序表中的顺序搜索在最坏情况下检查每次搜索的 N 个数字，平均每次搜索检查大约 N/2 个数字。

这个结果是假设搜索是平等的可能终止于由表中 N 个数字定义的 N+1 个间隔中的任何一个，该间隔立即导致表达式 (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

旁注:有一个关于著名天才数学家卡尔·弗里德里希·高斯(Karl Friedrich Gauss，1777-1855 年)小时候的故事。他的校长给全类同学布置了从 1 到 100 的数字相加问题，认为这会让他们忙上一段时间。但是高斯使用上面的推理，仅仅几分钟后就找到了总和 5050。注:高斯是一个真正的天才，但高斯的大部分生活史都是高斯写的!