社区讨论

关于复杂度分析

PPrincessQi蔡鸡
灌水区参与者 16已保存回复 33

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
33 条
当前快照
1 份
快照标识符
@lobyazhc
此快照首次捕获于
2023/10/30 04:56
2 年前
此快照最后确认于
2023/11/04 10:12
2 年前
查看原帖
CPP
for(int i=1;i<=n;i++)
	for(int j=1;j<=30;j++);
这份代码的复杂度是 O(n)O(n)
但
CPP
void dfs(int x,int fa){
	d[x]=d[fa]+1;
	f[x][0]=fa;
	for(int i=1;i<=30;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for(int i=beg[x];i;i=nex[i]){
		int y=to[i];
		if(y!=fa)
			dfs(y,x);
	}
}//这是对于一棵树的倍增预处理
这份代码的复杂度是 O(nlog⁡n)O(n\log n)
所以我突然迷惑了，有无神仙解答一下

回复

共 33 条回复，欢迎继续交流。

正在加载回复...