c++ std::set::lower_bound与std::lower_bound的时间效率问题
首先std::lower_bound()大家都知道，复杂度是o(log n)的，原理是二分查找。但如果用容器std::set加外置的std::lower_bound(),复杂度可不是简简单单的o(log n)的，貌似是o(log n)+n,原因是std::set自带红黑树，结构是一颗树形，然后普通二分查找方式可能会对这个结构里面的元素重复访问，以至于复杂度很高，所以用自带的std::set::lo
首先std::lower_bound()大家都知道，复杂度是o(log n)的，原理是二分查找。但如果用容器std::set加外置的std::lower_bound(),复杂度可不是简简单单的o(log n)的，貌似是o(log n)+n,原因是std::set自带红黑树，结构是一颗树形，然后普通二分查找方式可能会对这个结构里面的元素重复访问，以至于复杂度很高，所以用自带的std::set::lower_bound()查找，因为它是按照容器的结构进行查找，至于怎么进行的，我也不得而知。
这是stackoverflow上面的：
链接
翻译：std::set通常实现为自平衡树，其中一些列表结构与其相关联。了解这个结构，std::set::lower_bound将遍历树知道树结构的属性。这里的每一步都意味着遵循左或右子分支。
std::lower_bound需要运行类似于对数据进行二进制搜索的操作。然而，由于std::set::iterator是双向的，因此速度要慢得多，需要在已检查的元素之间进行大量增量。因此，元素之间的工作更加激烈。在这种情况下，算法将检查A和B之间的元素，然后调整A或B中的一个，找到它们之间的元素，并重复。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)