Блог пользователя acash

unable to calculate time complexity of below algorithm
Автор acash, история, 5 лет назад, По-английски

I stuck at a problem ,It was a basically implementation problem ,It passed all the test cases But I have doubt regarding its time complexity.

for (int i = 0; i < 1e6 + 100; i++) {
    sort(v[i].begin(), v[i].end());
}

The time complexity of this loop seems to be O(n*n*logn) .Then It should definitely fail because n value can be 10^6.Even O(n*n) fail for such higher value of n,I have seen already so many times on codeforces.

What is its correct time complexity??

Problem link

Please forgive me if it is too basic!

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e6 + 100;
vector<int> a, f(1e6 + 100);
vector<int>v[N];
int main() {
    int n;
    cin >> n;
    a.resize(n);
    int mx = -1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        f[a[i]]++;
        v[a[i]].push_back(i);
        mx = max(mx, f[a[i]]);
    }
    for (int i = 0; i < 1e6 + 100; i++) {
        sort(v[i].begin(), v[i].end());
    }
    int diff = INT_MAX;
    int ans[2];
    for (int i = 0; i < 1e6 + 100; i++) {
        if (f[i] == mx) {
            int temp = v[i][v[i].size() - 1] - v[i][0];
            if (diff > temp) {
                diff = temp;
                ans[0] = v[i][0];
                ans[1] = v[i][v[i].size() - 1];
            }
        }
    }
    cout << ans[0] + 1 << " " << ans[1] + 1;

}
  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

When I started I had the same problems with these kind of complexities, but it's very simple. Let's just use the $$$O$$$ notation to avoid using constants (I don't think it's correct to say that some $$$O(f(n)) \leq O(g(n))$$$, so we'll use this just for simplicity).

First of all, let's notice that the sizes of each $$$v_{i}$$$ sum up to $$$n$$$, thus:

$$$ \sum\limits_{i=0}^{MAX}|v_{i}| = n $$$

So, if we operate the complexities:

$$$ \sum\limits_{i=0}^{MAX}O(|v_{i}|log(|v_{i}|)) + O(1) \leq \sum\limits_{i=0}^{MAX}O\left(|v_{i}|log\left(\sum\limits_{i=0}^{MAX}|v_{i}|\right)\right) + O(1) $$$

This because $$$|v_{i}| \leq \sum\limits_{i=0}^{MAX}|v_{i}|$$$ and $$$log(x)$$$ is an increasing function. The $$$O(1)$$$ is the cost of iterating over the value of $$$i$$$ and accesing it's vector.

$$$ \sum\limits_{i=0}^{MAX}O\left(|v_{i}|log\left(\sum\limits_{i=0}^{MAX}|v_{i}|\right)\right) + O(1) = \sum\limits_{i=0}^{MAX}O(|v_{i}|logn) + O(1) \leq O(logn)\sum\limits_{i=0}^{MAX}|v_{i}| + \sum\limits_{i=0}^{MAX}O(1) $$$
$$$ O(logn)\sum\limits_{i=0}^{MAX}|v_{i}| + \sum\limits_{i=0}^{MAX}O(1) = O(logn)\cdot n + O(MAX) = O(nlogn + MAX) $$$

The final complexity will be $$$O(nlogn + MAX)$$$. However, I think that if you just store the maximum and the minimum value for each $$$i$$$ in, say, arrays $$$maxV_{i}$$$ and $$$minV_{i}$$$ then it can just take $$$O(n + MAX)$$$.

I hope this helped :D

→ Ответить