这题复杂度为什么是O(n^2)啊...
查看原帖
这题复杂度为什么是O(n^2)啊...
102506
封禁用户楼主2019/5/16 18:01

rt,看到题解对复杂度的分析都是O(n2)O(n^2)

但是我们要对每条边进行一次融合操作

设边两端点为x, y, 那每次融合操作的复杂度是O(sizex2+sizexsizey)O(size_x^2+size_x*size_y)

所以总体复杂度不是O(n3)O(n^3)吗QAQ

2019/5/16 18:01
加载中...