STL中常用容器操作时间复杂度小结
map, set, multimap, and multiset采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:
- 插入: O(logN)
- 查看:O(logN)
- 删除:O(logN)
hash_map, hash_set, hash_multimap, and hash_multiset采用哈希表实现，不同操作的时间复杂度为：
- 插入:O(1)，最坏情况O(N)。
- 查看:O(1)，最坏情况O(N)。
- 删除:O(1)，最坏情况O(N)。
vector从名字看，随机访问的复杂度应该是O(1)
- 插入 insert vector O（n）
- 插入 push_back vector O（1）
- 删除 pop_back vector O（1）
- 删除 erase vector O（n）
- 查找特点元素的时间复杂度 O（n）
LinkedList 底层是双链表
- get() 获取第几个元素，依次遍历，复杂度O(n)
- add(E) 添加到末尾，复杂度O(1)
- add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)
- remove（）删除元素，直接指针指向操作，复杂度O(1)
说明：
STL中vector，push_back的时间复杂度为常数
因为：假定有 n 个元素,倍增因子为 m。那么完成这 n 个元素往一个 vector 中的push_back操作，需要重新分配内存的次数大约为 logm(n)，第 i 次重新分配将会导致复制 m^i (也就是当前的vector.size() 大小)个旧空间中元素，因此 n 次 push_back操作所花费的总时间约为 n*m/(m - 1):
那么 n 个元素，n 次操作，每一次操作需要花费时间为 m / (m - 1)，这是一个常量.
た 入场券
小鱼儿
太过爱你忘了你带给我的痛
还没有评论，来说两句吧...