Combinazione. Complessità dell'algoritmo

Algoritmi
1

Ciao a tutti,
ho risolto con successo Combinazioni totalizzando 100/100, tuttavia non riesco a capire quale possa essere la complessità del mio algoritmo. La prima parte del programma è il crivello di Eratostene che funziona in \mathcal O(N \log \log N). Per la seconda parte, sono fermo ad una complessità \mathcal O(N ^ 2). Tuttavia questo algoritmo riesce a superare il subtask con N < 1000000, che richiederebbe una complessità di circa \mathcal O(N). Per qualche ragione il second ciclo for viene eseguito in media \mathcal log N volte. Qualcuno riuscirebbe a spiegarmi o a dimostrare perchè questo algoritmo è così efficente?

Questo è il mio programma:

#include<bits/stdc++.h>

using namespace std;
vector<bool> prime;




void suddividi(int N, int* X, int* Y) {
    int scam;

    prime.resize(4*N+10);
    prime[0] = prime[1] = true;
    for(int i=2;i*i<prime.size();i++){
        if(!prime[i]){
            for(int j=i*i;j<prime.size();j+=i){
                prime[j] = true;
            }
        }
    }

    for(int i=0;i<N;i++){
        X[i] = 2*i+1;
        Y[i] = 2*i+2;
    }
    for(int i=0;i<N;i++){
        if(!prime[X[i] + Y[i]]) continue;
        for(scam = i + 1 ;prime[X[scambio] + Y[i]] || prime[X[i] + Y[scambio]];scambio--);
        swap(Y[i],Y[scambio]);
    }


	return ;
}
2

Ma in realtà penso che sia addirittura inferiore a O(NlogN) , la mia soluzione è in O(N) (escluso il crivello che utiliziamo entrambi O(NloglogN)) eppure la mia soluzione risulta più lenta della tua.

1 Mi Piace
3

Hai qualche prova della tua congettura? Sono curioso anch’io

6 Mi Piace
4

Non c’è nessuna prova aaahahahh, mi ero inizialmente basato sui tempi ma sottoponendo nuovamente il codice viene eseguito in 0.7sec quindi nulla, mi sa che mi tocca aspettare qualcuno di bravo nel calcolare le complessità :wink:

Tu in che complessità l’hai risolto? Per curiosità

1 Mi Piace
5

Anche io lineare. Comunque con qualche trucco si può abbassare la complessità del crivello a \mathcal O(N), qui è spiegato brevemente.

6 Mi Piace
6

  1. Va tenuto presente che il file output.txt può anche essere di 15/16MB e che quindi il tempo di I/O (solo quello di output) fa la parte del leone

  2. Sicuri che non si possa fare a meno del crivello di Eratostene? I numeri primi da controllare possono essere molto molto pochi. Dei miei tentativi quello che ha ottenuto il tempo inferiore non lo usa.