关于复杂度的一个小疑惑
  • 板块学术版
  • 楼主Kevin911
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/1/15 13:59
  • 上次更新2024/1/15 19:13:56
查看原帖
关于复杂度的一个小疑惑
632131
Kevin911楼主2024/1/15 13:59

众所周知,调和级数近似 O(nlog⁡n)O(n\log n),

即∑i=1n⌊ni⌋=O(nlog⁡n)\sum_{i=1}^n \lfloor \frac{n}{i}\rfloor=O(n\log n)

那么∑i=1n⌊ni⌋2\sum_{i=1}^n \lfloor \frac{n}{i}\rfloor^2的近似值是啥。

比如有时打了这么个循环

for(int i=1;i<=n;i++)
   for(int j=i;j<=n;j+=i)
      for(int k=i;k<=n;k+=i)

就不知道该怎么判断复杂度,请教一下大佬

2024/1/15 13:59
加载中...