无哈希冲突时循环内哈希表插入操作的时间复杂度是多少

前置说明 #

所有结论均基于你给出的「哈希表不存在碰撞冲突」的前提假设，涉及的代码片段如下：

for(int i=0;i<jewels.length();i++) // 步骤1
        jewelSet.add(jewels.charAt(i)); // 步骤2

问题解答 #

• 问题1：结论正确。单步哈希表插入操作的时间复杂度为O(1)，循环总共执行n次（n为jewels字符串的长度），因此步骤2的总时间复杂度为n * O(1) = O(n)。
• 问题2：结论正确。步骤1的循环迭代、判断操作总复杂度为O(n)，步骤2的所有插入操作总复杂度为O(n)，两者相加得到总复杂度为O(2n)；大O时间复杂度表示法会忽略常数系数，因此最终简化得到O(n)。
• 问题3：结论正确。O(1)的含义是单步操作的耗时和输入规模无关，不会随n的增长而变化。但如果循环执行次数和输入规模n成正比，总耗时的增长速度就会和n正相关，因此总复杂度为n * O(1) = O(n)，不再是O(1)。

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