c++ vector.size()的复杂度

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)$。

以下是代码实现：

#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;
}

题目1：给定n个数值，从小到大排序。 要求： 1. 输入随机生成0≦x≦109数组，长度分别为5、10、100； 2. 采用快速排序输出每次执行的排序结果 3. 时间复杂度、空间复杂度、实际执行时间、实际占用内存空间？给出c++代码

题目1要求我们对随机生成的整数数组进行从小到大的排序，使用快速排序算法。以下是使用C++实现的快速排序示例：

#include <iostream>
#include <vector>
#include <cstdlib> // 用于rand()函数
#include <ctime>   // 用于srand(time(NULL))

// 交换两个元素的位置
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 快速排序函数
template<typename T>
void quickSort(T arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 计算并返回分区索引
int partition(T arr[], int low, int high) {
    T pivotValue = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 指针i初始化为低值

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivotValue) {
            i++; // 如果当前元素小于基准，移动指针i并将两者交换
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 将基准放到正确位置
    return i + 1;
}

// 主函数
int main() {
    srand(time(0)); // 设置随机数种子
    int n;
    std::cout << "Enter the length of array (5, 10, or 100): ";
    std::cin >> n;

    switch (n) {
        case 5:
            std::vector<int> shortArray(5, 0); // 创建大小为5的随机数组
            for (int i = 0; i < 5; i++) {
                shortArray[i] = rand() % 1000; // 生成0-999之间的随机数
            }
            std::cout << "Sorting 5 elements...\n";
            quickSort(shortArray.data(), 0, shortArray.size() - 1);
            break;
        case 10:
            std::vector<int> mediumArray(10, 0);
            for (int i = 0; i < 10; i++) {
                mediumArray[i] = rand() % 1000;
            }
            std::cout << "Sorting 10 elements...\n";
            quickSort(mediumArray.data(), 0, mediumArray.size() - 1);
            break;
        case 100:
            std::vector<int> longArray(100, 0);
            for (int i = 0; i < 100; i++) {
                longArray[i] = rand() % 1000;
            }
            std::cout << "Sorting 100 elements...\n";
            quickSort(longArray.data(), 0, longArray.size() - 1);
            break;
        default:
            std::cerr << "Invalid length! Exiting.\n";
            return 1;
    }

    // 输出排序后的数组
    std::cout << "Sorted Array:\n";
    for (const auto& num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}

**性能分析：**

- 时间复杂度：平均情况下的时间复杂度是O(n log n)，最坏情况（数组完全逆序）下是O(n^2)，但在实践中快速排序通常是高效的。
- 空间复杂度：由于递归调用栈，空间复杂度为O(log n)的额外空间，因为需要保存每个递归调用的信息。

**实际执行时间和内存占用：**

这将取决于具体的硬件环境，上述代码仅给出了基本的逻辑，实际运行时会有所不同。为了得到准确的时间和内存消耗，你需要在特定环境下用编译器（如g++）运行程序，并使用性能分析工具进行测量。例如，可以使用`chrono`库来测量执行时间，而内存使用则可以使用操作系统提供的命令行工具（如Linux上的`time`或Windows上的`Task Manager`）。