时间戳

首页 > 解决方案 > 复杂度 O(N) 数组和双精度

c++ - 复杂度 O(N) 数组和双精度

问题描述

如何获得复杂度 O(N)？我目前的复杂度为 O(N^2)，对吧？

    vector<int> coins;
    vector<int> div;

    int n;
    cin >> n;

    int b, m;

    for (int k = 0; k < n; k++)
    {
        cin >> m;
        for (int i = 0; i < m; i++)
        {
            cin >> b;
            coins.push_back(b);
        }
    }

编辑：代码在这里https://pastebin.com/bPG7D3W6

标签： c++

解决方案

那不是O(N^2)顺便说一句。那就是O(N * M)。因为你有两个循环。一个是从 0 到N，另一个是从 0 到 的嵌套循环M。也许如果你试图说出你想要达到的目标，重新格式化循环会更容易吗？

目前我看不到如何在保持其功能的同时以不同的复杂性重新设计这个循环。

编辑：

@bitmask 在他们的回答中提出了一个很好的观点。如果您预先分配向量，它将停止push_back() 重新分配向量。重新分配是O(N)。问题是我们没有M常数，它因用户的输入而异。但是你可以通过至少在你得到之后分配向量来执行可爱的优化n，大小为n. 这是一个可爱的优化的原因是因为它会为您节省一些性能，但不会影响您的 Big O。

vector<int> coins;
vector<int> div;

int n;
cin >> n;

int b, m;


coins.reserve(n);
...

推荐阅读