c++ vector.size()的复杂度
时间: 2024-04-09 12:26:26 浏览: 3
C++中的`vector.size()`函数用于返回`vector`容器中元素的数量。其复杂度是O(1),即常数时间复杂度。
`vector`是一个动态数组,它在内存中是连续存储的,因此可以通过直接访问数组的长度来获取元素的数量,而不需要遍历整个容器。无论`vector`中有多少个元素,`size()`函数都可以在常数时间内返回结果。
相关问题
给定一个n,求 n 个节点的树的最大团个数的期望。 最大团的定义是选出最多的点,使得任意两点之间都有边.c++代码.时间复杂度nlogn
我们可以使用树形DP来解决这个问题。设$f[u]$表示以节点$u$为根的子树中最大团的个数期望,$g[u]$表示以节点$u$为根的子树中不包含节点$u$的最大团的个数期望,$siz[u]$表示以节点$u$为根的子树大小。则有如下转移方程:
$$f[u] = g[u] + \frac{1}{2^{siz[u]-1}}$$
$$g[u] = \sum\limits_{v\in son[u]} \frac{f[v]}{1-\frac{1}{2^{siz[v]+1}}}$$
其中,$son[u]$表示节点$u$的子节点集合。
这个转移方程的含义是,节点$u$不在最大团中的概率为$g[u]$,所以节点$u$在最大团中的概率为$1-g[u]$。又因为节点$u$的子节点中只要有一个不在最大团中,那么节点$u$就不能在最大团中,所以节点$u$在最大团中的概率为子节点$u$的$f[v]$的乘积之和除以不满足要求的概率$1-\frac{1}{2^{siz[v]+1}}$的乘积之和。
最后,我们只需要计算$f[1]$就是答案。时间复杂度为$O(n\log n)$。
以下是代码实现:
```c++
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1005;
vector<int> G[MAXN];
int n, siz[MAXN];
double f[MAXN], g[MAXN], ans;
void dfs(int u, int fa) {
siz[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
f[u] += g[v];
}
f[u] += 1.0 / (1 << (siz[u] - 1));
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa) continue;
g[u] += f[v] / (1 - 1.0 / (1 << (siz[v] + 1)));
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
printf("%.10lf\n", f[1]);
return 0;
}
```
c++ vector 方法
C++中的vector是一种动态数组,可以在运行时动态增加或减少大小。下面是一些常见的vector方法:
1. push_back(x): 将元素x添加到vector的末尾。时间复杂度为O(1)。例如,v.push_back(1)将元素1添加到vector v的末尾。
2. size(): 返回vector中元素的个数。例如,v.size()返回vector v中元素的个数。
3. empty(): 检查vector是否为空。如果vector为空,则返回true;否则返回false。
4. clear(): 清空vector中的所有元素。将vector的大小重置为0。
5. resize(n): 调整vector的大小为n。如果n小于vector的当前大小,则删除多余的元素;如果n大于vector的当前大小,则在末尾添加默认值的元素。
6. erase(iterator): 删除指定位置的元素。例如,v.erase(it)将删除迭代器it指向的元素。
7. insert(iterator, x): 在指定位置之前插入元素x。例如,v.insert(it, 10)将在迭代器it指向的位置之前插入元素10。
8. begin(): 返回指向vector第一个元素的迭代器。
9. end(): 返回指向vector最后一个元素之后的位置的迭代器。
这些是vector的一些常用方法,可以根据需要选择适合的方法来操作vector。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [C++ vector的常见用法详解(超详细)\(^o^)/~](https://blog.csdn.net/m0_56494923/article/details/123263285)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *3* [C++ vector用法详解](https://blog.csdn.net/wxy2020915/article/details/126766020)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]