What is time complexity for find method in a set in c++?(c++ 中查找方法的时间复杂度是多少?)
本文介绍了c++ 中查找方法的时间复杂度是多少?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
set<int> s;
s.insert(1);
s.insert(2);
...
s.insert(n);
我想知道 s.find(k)
需要多少时间,其中 k
是 1..n 中的数字?我假设它是 log(n).这是正确的吗?
I wonder how much time it takes for s.find(k)
where k
is a number from 1..n?
I assume it is log(n). Is it correct?
推荐答案
O( log N ) 来搜索单个元素.
O( log N ) to search for an individual element.
§23.1.2 表 69
§23.1.2 Table 69
expression return note complexity
a.find(k) iterator; returns an iterator pointing to an logarithmic
const_iterator element with the key equivalent to k,
for constant a or a.end() if such an element is not
found
这篇关于c++ 中查找方法的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
沃梦达教程
本文标题为:c++ 中查找方法的时间复杂度是多少?
基础教程推荐
猜你喜欢
- 如何使图像调整大小以在 Qt 中缩放? 2021-01-01
- 如何在不破坏 vtbl 的情况下做相当于 memset(this, ...) 的操作? 2022-01-01
- Windows Media Foundation 录制音频 2021-01-01
- 从 std::cin 读取密码 2021-01-01
- 使用从字符串中提取的参数调用函数 2022-01-01
- 如何“在 Finder 中显示"或“在资源管理器中显 2021-01-01
- 管理共享内存应该分配多少内存?(助推) 2022-12-07
- 在 C++ 中循环遍历所有 Lua 全局变量 2021-01-01
- 为 C/C++ 中的项目的 makefile 生成依赖项 2022-01-01
- 为什么语句不能出现在命名空间范围内? 2021-01-01