迭代std :: set/std :: map的时间复杂度是多少？
迭代std::set/std::map的时间复杂度是O(n)，其中n是容器中元素的数量。这是因为在迭代过程中，需要遍历整个容器中的所有元素，因此时间复杂度与元素数量成正比。
std::set和std::map是C++标准库中的关联容器，它们都是基于红黑树实现的。红黑树是一种自平衡的二叉查找树，它可以保证在最坏情况下的查找、插入和删除操作的时间复杂度为O(log n)。但是，在迭代过程中，需要遍历整个容器中的所有元素，因此时间复杂度为O(n)。
如果您需要在迭代过程中具有更高效的查找、插入和删除操作，可以考虑使用std::unordered_set/std::unordered_map，它们是基于哈希表实现的，平均情况下的时间复杂度为O(1)。但是，在迭代过程中，时间复杂度仍然为O(n)。
推荐的腾讯云相关产品：
- 腾讯云云服务器：提供高性能、高可用的云服务器，支持一键部署和扩展，满足各种应用场景的需求。
- 腾讯云数据库：提供多种数据库服务，包括关系型数据库、非关系型数据库和搜索引擎等，满足不同业务需求。
- 腾讯云容器服务：支持弹性伸缩、自动扩展和负载均衡等功能，帮助用户快速构建、部署和管理容器化应用。
产品介绍链接地址：
相关·内容
我试图在std::map中找到最大的值，这将是树中的最后一个节点(因为std::map键是排序的)。
Cppref说std::map.end()是恒定的时间。但是要获得最大的密钥，我必须得到这个迭代器的前一个值，即*std::prev(std::map.end())。
那次手术的时间复杂度是多少？
我知道这应该等同于--std::map.end()，但我也不知道操作的成本。
浏览 2提问于2018-11-02得票数 5
回答已采纳
下午好，我想知道std::multimap::equal_range的时间复杂度是多少？是Big-O(n)还是BIG-0(log )。我记得我读到过std::multimap::erase的时间复杂度是“被删除的序列的长度的对数加上线性时间。”
浏览 4提问于2011-05-13得票数 5
回答已采纳
2回答
我仍然对C++中的std::map的运行时复杂性感到有点困惑。我知道下面算法中的第一个for循环需要O(N)或线性运行时间。但是，第二个for循环有另一个在map上迭代的for循环。这会增加整体运行时的复杂性吗？换句话说，以下算法的整体运行时复杂度是多少？是O(N)还是O(Nlog(N))或者别的什么？ vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> result;
map<int, int&
浏览 248提问于2020-06-23得票数 1
回答已采纳
我对Java很陌生。我有一个关于java迭代器()的时间复杂性的问题。
Set<Integer> set = new HashSet<>();
Iterator<Integer> iter = set.iterator(); ==> (2)
我想知道第二步的时间复杂度是多少？它是连续时间O(1)还是取决于集合的大小？
谢谢
浏览 6提问于2016-11-02得票数 3
回答已采纳
对于像std::set和std::map这样的数据类型，在对数时间内进行查找，是否需要实现来维护begin和end迭代器？访问begin和end是否意味着可以在对数时间内进行查找？
我一直认为开始和结束总是发生在恒定的时间内，但是我在Josuttis中找不到任何证实这一点的地方。现在我正在做一些我需要对性能进行分析的事情，我想确保覆盖我的基础。
谢谢
浏览 4提问于2008-09-17得票数 8
回答已采纳
2回答
如果'a‘是n个整数的向量，假定'i’为0，那么这个函数的时间复杂度是多少？
for (auto x : {a[i], a[n - i - 1]})
{
auto b = a;
b.erase(std::remove(b.begin(), b.end(), x), b.end());
auto c = b;
std::reverse(c.begin(), c.end());
}
浏览 6提问于2022-01-11得票数 -7
2回答
Array.from()的时间复杂度是多少？例如： const set = new Set();
set.add('car');
set.add('cat');
set.add('dog');
console.log(Array.from(set)); // time complexity of making this convertion from Set to Array
浏览 22提问于2019-12-04得票数 4
回答已采纳
我使用std::map按排序顺序存储一组数字。我希望能够在O(1)时间内获得小于或等于某个目标数的计数器(不包括查找最大键( <= target)所需的时间)。有办法这样做吗？
举个例子，假设我有以下数字(副本可以存在)，(1,0,5,2,3,8)作为密钥存储在std::map中，并且我有一个target_key = 4。我想使用std::map给出解决方案4，因为数组<=4中有4个数字。
我不确定std::map是否准备这么做。我唯一能想到的就是使用std::upper_bound为我获取最大值<=4的迭代器，然后遍历迭代器并总结每个键的计数，但这是O(n)时间。
编辑1：
浏览 9提问于2020-03-05得票数 1
回答已采纳
在一些CP竞赛(很重要)中，我使用了两个版本的upper_bound在我的std::map中找到上限
算法上界(1)
auto itr = std::upper_bound(s.begin(),s.end(), somenumber);
if(itr == s.end() || *itr > somenumber2)
{
//dosth
} else
//dosth2
}
std::map::upper_bound (2)
auto itr = s.upper_bound(somenumber);
if(itr == s.end() || *itr > somenumber2)
浏览 1提问于2020-01-18得票数 3
回答已采纳
1回答
字符串连接时间复杂度c++
、、、、
我在C++中搜索了连接字符串的不同方法，发现std::stringstream和std::string是可能的选项。但是，我找不到stringstream和string的连接操作的时间复杂度。C++中字符串拼接的时间复杂度是多少？此外，在std::stringstream和C++中的std::string中转换为字符串的时间复杂度是多少。是否有可能在0(1)时间内在C++中追加字符串？谢谢您抽时间见我。
浏览 5提问于2017-07-30得票数 1
clear函数is std::map的时间复杂度是多少？
我说它是O(1)对吗？
浏览 0提问于2012-06-12得票数 2
2回答
LRU缓存算法的复杂性
、、、
我面前有一项任务，要实现LRU缓存。系统运行时间最长的应采用O(log (n))。作为我的缓存，我使用std :: MAP。我仍然需要第二个容器来存储键+创建时间-按时间排序。当我需要将地址更新到缓存时，它应该放在以下几个地方：
按键O(log (n))查找。
移至迭代器O(1)。
插入O(log (n))的新元素。
最古老的成员必须自然居住在container.begin()中。
我只能用STL。
名单-不适合我。
list.find() - O (n)
优先级队列-删除未实现的项。
我认为理想情况下，它可以存储在std::set中；
std::set<pair&l
浏览 2提问于2015-01-18得票数 1
回答已采纳
迭代std::set/std::multiset/std::map/std::multimap？的时间复杂度是多少？我相信它在集/图的大小上是线性的，但不是很确定。它是在语言标准中指定的吗？
浏览 3提问于2012-08-02得票数 32
回答已采纳
std::map的时间复杂度是多少？在最坏的情况下它会退化吗？或者它是由实现决定的，我们不能知道？
浏览 6提问于2014-02-12得票数 21
回答已采纳
2回答
__gcd(m，n)函数的时间复杂度是多少？另外，它是否使用欧几里德方法来计算gcd？
例如，代码
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cout << "gcd(10, 25) : " << __gcd(6, 20) << endl;
}
浏览 0提问于2019-06-11得票数 3
1回答
对于stl Tree(set还是map)，iterator++操作的复杂性是多少？我一直认为他们会使用索引，因此答案应该是O(1)，但最近我阅读了vc10实现，shockly发现它们没有。要在有序subtree中找到下一个元素，需要时间搜索右边子树中最小的元素，或者如果节点是一个左子并且没有右子节点，则搜索右边兄弟中最小的元素。这引入了一个递归过程，我相信++操作符花费了O(lgn)时间。我说的对吗？对于所有stl实现还是只适用于可视化C++，都是这样吗？
维持RB-树的指数真的很难吗？只要我看到，通过在节点结构中保持两个额外的指针，我们就可以维护一个双链接列表，就像RB一样。他们为什么不这么
浏览 5提问于2014-02-25得票数 6
回答已采纳
假设我使用了来自于N个元素的std::map (c++)的地图数据结构，如下所示：
map<int,bool>m;
这里的空间复杂性(对于N个元素)是多少？是因为
O(N*(sizeof(int)+sizeof(bool)))
或者其他的东西加在一起我错过了什么？
浏览 0提问于2020-05-13得票数 0
回答已采纳
1回答
对于给定的代码，bigO表示法的时间复杂度是多少：
for(i=n; i >= 1; i /=2)
for(j=i; j>=1; j/=2)
x = i+j;
第一个循环运行日志N次，第二个循环如何？是(原木N*原木N)吗？
我很困惑。
谢谢
浏览 0提问于2017-03-25得票数 1
回答已采纳
2回答
我知道迭代整个集合的时间复杂度需要O(n)时间，其中n是集合的大小。问题是，在两个迭代器itBegin和itEnd之间迭代的复杂度是多少？也许它有点像O(itEnd - itBegin + log n)，但我不能证明。
浏览 3提问于2015-07-15得票数 4
我有一个场景，我必须将BitSet索引的范围设置为1。
/*
*Code snippet
*/
BitSet myBitSet = new BitSet(100);
myBitSet.set(10, 50);
//**************************
上述代码的时间复杂度是多少？它会迭代40个元素，还是会执行某种位操作？
浏览 6提问于2016-02-26得票数 6
回答已采纳
1回答
For I=1 to n
For J=1 to n
k = b[I]
F = Linear_search(a,k)
Print F
J=J*2
上述算法的时间复杂度是多少？我原以为它是O(nlogn)，但在复杂度O(n).So的算法中也有线性搜索，复杂度O(nlogn)或O(n)是什么，还是O(n^2 logn)？
浏览 3提问于2021-09-22得票数 0
回答已采纳
1回答
A = [1,2,3] B = ["a","c","d"] zip(A，B)和list(zip(A，B))的时间复杂度是多少？
浏览 20提问于2021-04-08得票数 0
回答已采纳
1回答
对于如下所示的嵌套映射：
Map<String, Map<String, List<String>>> map = new HashMap<String, HashMap<String, ArrayList<String>>>();
像put，remove，containsKey这样的正常操作的时间复杂度是多少？
谢谢!
浏览 0提问于2017-11-15得票数 1
1回答
这个片段的时间复杂度是多少？
for(int i=0; i<n;i++){
for (int j=0; j<n/2;j++){
}
}
`
浏览 6提问于2022-11-29得票数 0
2回答
时间复杂度是多少？为什么？
(define (mult a b)
(define (internal a accum)
(if (= a 1) accum
(internal (- a 1) (+ accum b))))
(internal a b))
(define (to-the-power-of m n)
(define (internal x accum)
(if (= x 0) accum
(internal (- x 1) (mult accum m))))
(internal n 1
浏览 1提问于2008-10-30得票数 1
1回答
我已经开始学习Big O符号和分析时间复杂性，并尝试摆弄一些代码来尝试理解它的时间复杂性。这是我的其中一行代码，但我似乎不能计算出求和方法的时间复杂度是多少？我估计它是o(n^3)，但我的朋友说它应该是o(n^2)。关于正确答案是什么，有什么见解吗？ public static double sum(double[] array)
{
double sum = 0.0;
for(int k = 0; k < size(array); k++)
sum = sum + get(array, k);
return sum;
}
public static
浏览 63提问于2021-10-26得票数 0
4回答
获取最低n个元素的时间
、、、
正如我在文档中读到的那样，std::map应该使用二进制搜索树来实现，并且它也会对它们进行排序。
我需要快速插入和检索元素。我还需要时不时地获取前最低的N个元素。
我在考虑使用std::map，这是一个好的选择吗？如果是，检索最低的N个元素所需的时间是多少？O(n*logn)？
浏览 0提问于2013-01-21得票数 0
回答已采纳
1回答
当我读到有关量子算法的文章时，我遇到了Deutsch-Jozsa算法，我看到如果我们想用非量子算法来解决这个问题，我们的算法将具有指数时间复杂度。现在我想知道Deutsch-Jozsa算法作为量子计算机上的量子算法的时间复杂度是多少？
浏览 1提问于2011-08-20得票数 1
3回答
所以我有以下代码
def example(array):
count = 5
for _ in range(count):
array.remove(0)
array.append(0)
整体的时间复杂度是多少？for循环本身应该是O(1)，对吗？但我不确定'array.remove(0)‘行将如何影响整体时间复杂度。
浏览 0提问于2021-01-14得票数 0
在Java中实现math.sqrt的时间复杂度是多少？Java在某种技术中实现了时间复杂度，我正在尝试确定其时间复杂度。
浏览 2提问于2015-03-03得票数 3
我提出了以下算法来计算查找字符串中出现频率第二高的字符的时间复杂度。这个算法分为两个部分。第一部分，字符插入到O(n)中的映射中。我对第二部分有困难。迭代映射是O(n) push，pop是O(log(n))。第二部分的BigO复杂度是多少？最后，总体复杂度是多少？有没有人帮我理解这一点就太好了？
void findKthHighestChar(int k,std::string str)
{
std::unordered_map<char, int> map;
//Step 1: O(n)
for (int i = 0; i < str.si
浏览 0提问于2021-05-06得票数 0
#include <iostream>
using namespace std;
int main()
{
int a[100][100]={10};
cout<<a[0][0];
return 0;
}
上述程序的时间复杂度是多少？是O(1)还是O(100^2)?？
浏览 0提问于2015-02-06得票数 0
正如在新标准中引入的std::unordered_map/std::unordered_set一样，它使用散列函数并具有插入/删除/获取元素的平均恒定复杂性，如果我们不需要按特定顺序迭代集合，似乎没有理由使用“旧的”std::map/std::set？或者还有其他一些情况/原因，当std::map/std::set会是更好的选择？会不会是给前任的。更少的内存消耗，或者他们比“无序”版本唯一的优点是排序？
浏览 0提问于2021-03-01得票数 0
我在CodeChef上解决的问题，并通过。
下面是实现的不相交集合算法的伪代码：
Initialize parent[i] = i
Let S[i] denote the initial array.
int find(int i)
int j
if(parent[i]==i)
return i
else
j=find(parent[i])
//Path Compression Heuristics
parent[i]=j
return j
set_union(int
浏览 1提问于2015-12-25得票数 2
1回答
我在三个参数集上运行并计时了Weil配对的实现。一个数量级为512位，一个为256位，最后一个为161位。
我采用Miller的算法来计算Weil配对。我用于两点乘法的算法是双加加算法.如果我正确理解，这两种算法的时间复杂度都为$O(log (n))$。
我得到的时间是512位的10秒，256位的2，5秒，161位的1秒。当我看到我得到的时间时，似乎更像是$O(n^2)$或$O(n \cdot log (n))$的复杂性。
有人能告诉我基于我的结果的时间复杂度是多少吗？
浏览 0提问于2018-08-15得票数 1
回答已采纳
2回答
let array = [1,7,2,2,3,7,4];
while(array.length){
// get last item
let item = array.pop()
// remove duplicates
const filteredArray = array.filter(content => content!==item);
// if filteredArray had duplicate items then log the ite
浏览 0提问于2021-08-17得票数 -2
假设python中的heapq是python doc中指定的最小堆，假设我有一个包含m个元素的heapq，那么调用heap的时间复杂度是多少？我不认为复杂度是O(n*lg(m))，因为简单地弹出根并在min堆中再次堆只能得到最小的n？
浏览 2提问于2015-03-18得票数 6
2回答
以下代码的时间复杂度是多少？
a = 2;
while (a <= n)
{
for (k=1; k <= n; k++)
{
b = n;
while (b > 1)
b = b / 2;
}
a = a * a * a;
}
--我在和外循环做斗争，，也就是loglogn，我不明白为什么。如果最后一行是a = a * a * a * a;，时间复杂度会发生什么变化？
for循环是O(n)，内部循环是O(logn)。
所以总的来说，O(n*logn*loglogn)
浏览 4提问于2016-09-10得票数 1
回答已采纳
1回答
我有个问题。
在理论计算机科学方面，当我们分析一个算法时，如果一个算法初始化一个新的数据结构，那么我们就把这个数据结构看作是空间复杂性的一部分。
现在我对这部分还不太确定。
假设我有一个int数组，我想通过使用int指针的映射来映射它们。比如
std::map<int*,int*> mymap;
for (int i = 1; i < arraySize; i++) {
mymap[&arr[i-1]]=&arr[i];
}
如果这个算法没有使用指针，那么我们可以清楚地表明它正在初始化一个大小为n的映射，因此空间复杂度是O(n)，但是对于这个例子，如果我
浏览 1提问于2013-11-20得票数 2
回答已采纳
我正在尝试设计一种算法来查找数组中两个相同元素的索引。输入是一个数组，输出是两个索引i&j，使得arrayi=arrayj。时间复杂度必须为O(nlogn)。
这是我尝试过的
let i=0 to size_of_array{
let j=i+1 to size_of_array{
if array[j]=array[i]{
print(i, j)
}
}
}
嵌套循环是O(n^2)，但如果我尝试这样设计。时间复杂度是多少？
N是数组的大小，我的实现将运行O(n(n-1)+(n-2)+(n-3)....+1)次。它
浏览 1提问于2019-09-17得票数 0
使用std：：设置在std：：find_if中的std::find_if()函数的时间复杂度是多少？
假设我们有以下示例：
auto cmp = [&](const pair<int, set<int>>& a , const pair<int, set<int>>& b) -> bool {
if (a.second.size() == b.second.size()) {
return a.first < b.first;
}
return a.second.size
浏览 12提问于2022-11-09得票数 0
1回答
for(int i = 0; i < n; i++){
for( ; i < n; i++){
System.out.println(i);
}
}
这段代码的时间复杂度是多少？外循环运行了很多次，但我对内环不太确定。如果内环对i的每个值都是n，那么它能是O(n^2)吗？
浏览 2提问于2017-07-21得票数 1
回答已采纳
我最近玩了一台。我怀疑我的STL版本会跟踪一些文件数据结构中的非空桶(看起来像一个列表)。我认为这样做是为了提供完整std::unordered_set的std::unordered_set时间遍历(其中n表示unordered_set中有比n大得多的m桶和m中的元素数)。这改进了O(m)时间中所有桶的简单遍历。
我已经测试过，对大型和非常稀疏的unordered_set(使用begin - end)的遍历要比对所有桶的简单遍历要快得多。
问题：这个遍历运行时是否得到了标准的保证？或者这只是我特定标准库的一个特性？
下面是我要使用的测试代码：
#include <iostream>
浏览 1提问于2017-04-13得票数 7
回答已采纳
3回答
这个算法来自于破解编码面试，第五版，在这里找到：
孩子跑上有n个台阶的楼梯，一次可以跳1步、2步或3步。实现一个方法来计算孩子可以跑上楼梯的可能方式。算法：
public static int countWaysDP(int n, int[] map) {
if (n < 0) {
return 0;
} else if (n == 0) {
return 1;
} else if (map[n] > -1) {
return map[n];
} else {
map[n] = cou
浏览 2提问于2016-11-09得票数 4
回答已采纳
我知道C++中的映射是一个平衡的二进制搜索树。但是，当我迭代嵌套的for循环中的map时，我想知道时间复杂度是多少 for (auto x : mp) {
for (auto y : mp) {
//
//
}
}
浏览 48提问于2021-02-10得票数 0
1回答
min，max具有O(N)时间复杂度，因为它们必须遍历给定的列表/字符串并检查每个索引以找到min/max。但是我想知道，如果用在一个集合上，最大的时间复杂度是多少？例如：
s = {1,2,3,4} # s is a set
使用min/max，我们得到：
min(s) = 1
max(s) = 4
由于sets不使用诸如列表和字符串之类的索引，而是使用可以直接访问的桶来操作，那么min/max的时间复杂度是否与一般情况不同？
谢谢!
浏览 0提问于2018-03-11得票数 8
回答已采纳
1回答
以下的时间复杂度是多少？
我知道不检查重复项的排列使用O(n!)，但我对shoudSwap函数特别感兴趣，如下所示：
// Returns true if str[curr] does not match with any of the
// characters after str[start]
bool shouldSwap(char str[], int start, int curr)
{
for (int i = start; i < curr; i++)
if (str[i] == str[curr])
retur
浏览 0提问于2019-07-20得票数 0
1回答
我想问问自己，下面的代码的时间和空间复杂度是多少。这是为了从一个单词列表中吐出字谜。
def ana(input_):
results = []
for key, word1 in enumerate(input_):
a=set([i for i in word1])
for word2 in input_[key+1:]:
b=set([i for i in word2])
if len(set(a)-set(b))==0 and len(set(b)-set(a))==0:
浏览 5提问于2020-01-30得票数 0
回答已采纳
1回答
递归地生成唯一的字符串排列
、、、、
目标
编写用于生成输入字符串的所有排列的递归方法。将它们作为一组返回。
见：递归字符串排列 -采访蛋糕
问题
1:如果字符串可以有重复字符，那么问题会如何改变呢？
下面的解决方案适用于重复字符，因为原始输入的索引用于生成原始输入减去给定索引下的字符的唯一组合。因此，可能存在重复字符，但是，它们的唯一索引将生成正确的解决方案。
2:时空复杂度是多少？
时间复杂性：O(n^2)，因为在输入中有一个迭代，其中一个索引要检查，另一个迭代，将字符放置在输入的每个位置，以生成各种组合。因此，n x n.这遵循规则，为Y的每一次做X。参见：字符串所有排列的时间复杂性 - GeeksforGeeks
空间复杂
浏览 0提问于2020-11-02得票数 0
使用哈希表集合类型(如std::unordered_map与std::set )的实际折衷是什么？
对于我正在做的一些随意的事情(在C++中)，我有一个从一对大列表中识别重复项的集合交叉问题。
我的第一个假设是迭代第一个列表并将每个列表插入到一个std::unordered_map<T, bool>或(std::hash_map)中，其中插入时的值参数总是true。然后在hash_map中查找第二个列表中的每个项目。工作假设是，每个插入都是O(1)，每个查找也是O(1)。
然后，我开始思考也许std::set更合适。一些粗略的在线搜索显示std::set的实现是红色/黑色真，插入和
浏览 4提问于2014-06-12得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
