O(N^2*2^N) più veloce di (N*2^N)

Linguaggi
1

Non saprei che tag mettere ma oggi ho trovato due pezzi di codici davvero strani, fanno esattamente la stessa cosa solo che uno nella complessità ha un fattore N aggiuntivo.

(constraints: N <= 21)
Codice con complessità O(N^2*2^N):

for(int i = 0;i<n;i++){
for(int j=0; j < (1<<n);j++)if(__builtin_popcount(j)==i+1){
	//ciclo da 0 a N qua
}
}

Codice con complessità O(N*2^N):

for(int j=0; j < (1<<n);j++){
	int i = __builtin_popcount(j)-1;
	//ciclo da 0 a N qua
}

L’unica differenza tra i due codici mi sembra essere che nel primo la funzione __builtin_popcount venga chiamata molte più volte, mentre il ciclo all’interno (che ho omesso) viene eseguito esattamente lo stesso numero di volte con gli stessi valori. Tuttavia il primo codice risulta leggermente più veloce. C’è probabilmente qualcosa che mi sto perdendo ma non riesco proprio a capire cosa.

Per chi fosse interessato questo è il problema, mentre questo è il codice completo:

#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
using ll = long long;

constexpr ll mod = 1000000007;

void solve();
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
	// cin>>t;
	rep(i,t){
		solve();
	}
}


void solve(){
	int n;
	cin>>n;
	vector<vector<int>> matr(n,vector<int>(n));
	rep(i,n)rep(j,n)cin>>matr[i][j];
	vector<ll> dp(1<<n);
	dp[0]=1;
	rep(i,n){
		rep(j,(1<<n))if(__builtin_popcount(j)==i+1){
			rep(z,n)if((j & (1<<z)) && matr[i][z]){
				dp[j]=(dp[j] + dp[j ^ (1<<z)])%mod;
			}
		}
	}
	cout<<dp[(1<<n)-1]<<'\n';
}
2

Sarebbe interessante provare a compilare con -O0 per disabilitare eventuali ottimizzazioni e riprovare.

In generale il compilatore può essere molto furbo a volte, e rimuovere completamente cicli for non necessari.

3

In realtà i due pezzi di codice hanno esattamente la stessa complessità di O(N∗2^N).
Immagino tu abbia “Moltiplicato” le complessità dei singoli cicli per ottenere la complessità totale.
Però si può fare un’analisi più precisa e trovare un bound migliore per il primo pezzo di codice (lo riporto qua con un formatting diverso):

for(int i = 0;i<n;i++) {
    for(int j=0; j < (1<<n);j++) {
        if(__builtin_popcount(j)==i+1) {
	        // ciclo da 0 a N
        }
    }
}

L’if verrà giustamente eseguito N*2^N volte, ma solo in 2^N di queste la condizione sarà soddisfatta e il for più interno verrà eseguito. La complessità totale è quindi O(N*2^N) (complessità di eseguire ogni volta l’if) + 2^N*O(N) (complessità di eseguire, nei casi che soddisfano la condizione, il ciclo più interno) = O(N*2^N)

Il dubbio è comunque legittimo nel senso che la prima soluzione sta facendo un po’ più conti, anche se non molti di più (il 10% in più, potrebbe essere). Comunque il tempo d’esecuzione varia molto e, come si dice,

La soluzione più veloce è quella inviata alle 3 di notte.

6 Mi Piace