求问时间复杂度
查看原帖
求问时间复杂度
1305692
xiangixuan楼主2025/7/28 18:47

第一篇题解的代码:

Rep(i,1,n){ // <- O(n)
	memset(f,0,sizeof(box));
	memset(g,0,sizeof(g));
	RepG(j,i){ // <- O(n)
		int v=e[j].to;
		deepest=0;
		memset(box,0,sizeof(box));
		dfs(v,i,1);
		Rep(k,1,deepest){ // <- O(n)
			ans+=f[k]*box[k];
			f[k]+=g[k]*box[k];
			g[k]+=box[k];
		}
	}
}

三个最坏 O(n)O(n) 的循环,为什么合起来复杂度是 O(n2)O(n^2) ? QwQ

2025/7/28 18:47
加载中...