哈希表链地址法插入平均时间复杂度：O(n/m+1)是否等价于O(n/m)？

是的，在大O表示法下，O(n/m + 1) 完全等价于 O(n/m)。

大O表示法的核心是描述算法复杂度的渐进增长趋势，只关注当输入规模（这里对应哈希表中的元素总数n）趋近于无穷时，主导复杂度增长的项，常数项和低阶项都会被忽略。

具体到这个场景：

• n/m 是哈希表的负载因子，当n不断增大时，这个项会持续增长，是复杂度的主导部分。
• +1 是哈希函数的固定开销，属于常数项，无论n多大，它的数值都不会变化，对整体复杂度的渐进增长没有影响。

从大O的严格定义来看：如果存在常数c和n₀，当n > n₀时，n/m + 1 ≤ c*(n/m)，那么O(n/m + 1)就等于O(n/m)。我们可以取c=2，当n ≥ m（也就是负载因子n/m ≥1）时，n/m +1 ≤ n/m + n/m = 2*(n/m)，完全满足定义要求。

所以不管是从大O的直观理解还是严格定义出发，这两个复杂度表示都是等价的。

内容的提问来源于stack exchange，提问作者SillySlimeSimon