求助一个时间复杂度
  • 板块学术版
  • 楼主djwj233
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/12/4 10:13
  • 上次更新2023/11/3 23:00:57
查看原帖
求助一个时间复杂度
114558
djwj233楼主2021/12/4 10:13

RT,昨天 ABC 的 G,我的最坏复杂度是

Θ(∑i=1nd(i)2)\Theta(\sum_{i=1}^n d(i)^2)

我不知道这个东西的渐近复杂度qwq

题解里面直接搞出 max⁡i=1nd(i)≤63,n≤2×105\max\limits_{i=1}^{n}d(i)\le63,n\le 2\times 10^5,然后说最大是 63nlog⁡n\mathcal 63n\log n,但是个人感觉非常扯淡。

目前只会证它是 O(n43log⁡n)\mathcal O(n^{\frac{4}{3}}\log n) 和 Ω(nlog⁡2n)\Omega(n\log^2 n) 的。

2021/12/4 10:13
加载中...