求助一个时间复杂度
  • 板块学术版
  • 楼主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

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

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

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