c++ - 以下排序算法是否为O(n)？

Question

算法:

在 map 中插入元素计数

从第一个元素

开始

(如果第一个出现在 map 中)，插入输出数组(计数总数)，递增第一个

如果第一个不在 map 中，请查找 map 中存在的下一个数字

复杂度:O(线性数组中的最大元素)是线性的，因此O(n)。

vector<int> sort(vector<int>& can) {
    unordered_map<int,int> mp;
    int first = INT_MAX;
    int last = INT_MIN;
    for(auto &n : can) {
        first = min(first, n);
        last = max(last, n);
        mp[n]++;
    }
    vector<int> out;
    while(first <= last) {
        while(mp.find(first) == mp.end()) first ++;
        int cnt = mp[first];
        while(cnt--) out.push_back(first);
        first++;
    }
    return out;
}

Answer 1

复杂度:O(线性数组中的最大元素)是线性的，因此O(n)。

不，不是O(n)。 while循环迭代last - first + 1时间，此数量取决于数组的内容而不是数组的长度。

通常，我们使用n表示算法所处理的数组的长度。为了描述范围(即数组中最大值和最小值之间的差)，我们可以引入一个不同的变量r，然后时间复杂度为O(n + r)，因为填充映射的第一个循环会迭代O( n)次，填充 vector 的第二个循环迭代O(r)次，从cnt倒数的其内部循环总共迭代O(n)次。

定义n的另一种更正式的方式是“输入大小”，通常以对算法输入进行编码所用的位数来度量。假设输入是一个长度为2的数组，其中仅包含数字0和M表示某个数字M。在这种情况下，如果用于编码输入的位数为n，则数字M的数量级可以为O (2n)，第二个循环执行了那么多次迭代；因此根据这个正式定义，时间复杂度是指数级的。