求分析复杂度

喵仔牛奶 @ 2023-06-23 20:04:35

by 喵仔牛奶 @ 2023-06-23 20:14:04

顺带问一下 \sum\limits_{d|n}\dfrac{1}{d} 是什么级别。

by bamboo12345 @ 2023-06-23 20:14:48

应该是 O(n^{\frac{3}{4}}) 吗？

by dehsirehC @ 2023-06-23 20:16:34

@bamboo123 你说得对，但感觉远达不到

by ღꦿ࿐ @ 2023-06-23 20:17:46

by bamboo12345 @ 2023-06-23 20:18:17

@liqingyang 感觉这玩意儿是不是杜教筛的那个复杂度啊

by jijidawang @ 2023-06-23 20:18:48

@bamboo123 显然比杜教筛小吧

by bamboo12345 @ 2023-06-23 20:21:07

@jijidawang 但感觉小的不多说实话

by bamboo12345 @ 2023-06-23 20:22:54

搞错了第二个是 \frac{\sigma(n)}{n}

by dehsirehC @ 2023-06-23 20:23:03

感觉把约束个数的那个式子带进去就差不多了

by bamboo12345 @ 2023-06-23 20:26:15

但其实第二个只要知道比 \ln n 还要小估计就没太大问题了吧，实际用的话无所谓感觉