关于普通数组实现set的时间复杂度
来源：4-3 set和map不同底层实现的区别
软件工程小白菜
2019-03-06
老师您好。
在4.3小节中，您指出普通数组实现set的插入操作时间复杂度为O(1)，原因是只需要在数组末尾添加即可。
但是基于set的定义，每次插入一个元素是否应该遍历一遍数组检查是否已有重复元素？如果插入的元素在原数组中存在，则不进行添加。所以这个操作的时间复杂度也应该为O(n)。
多谢解释。
写回答
1回答
-
你是正确的，如果我们的set保证存储的元素不重复，插入操作是O(n)的。
但set本身是一个广义的概念，也可以用于存储重复的元素（或者更进一步，叫multiset），此时使用数组实现，插入操作是O(1)的：）
课程这也ppt不够严谨，感谢提醒：）
继续加油！：）
112019-03-06
相似问题