关于时间复杂度
查看原帖
关于时间复杂度
866943
Tiga_Zhou楼主2023/5/18 17:34

不知道大家队这个题的时间复杂度有没有疑问。

这个题用匈牙利算法看似是 O(nm)O(nm) 的时间复杂度,但实际上每一次最多跑 mm 遍,时间复杂度最坏应该是 1+2+3+...+m=m2+m2,m≤104.1+2+3+...+m=\frac {m^2+m}{2},m\leq 10^4. 而且一般都跑不满,再加上洛谷评测机本来就很快,于是就很顺利的过掉了。

大概应该是这样吧,如果说错了,还请修正。

2023/5/18 17:34
加载中...