从 $n$ 枚举判断一个数的位数之和是否为 $4$ 的倍数。
位数和可以这么写。
int f(int x){
return x==0?0:f(x/10)+x%10;
}
时间复杂度是 $O(10^{\frac k 9} \log n)$,其中 $k$ 是倍数:$4$。
我们来证明复杂度:
-
单次问位数和是 $\log$ 的。
-
枚举数的上界为 $O(10^{\frac k 9})$ 的。
第一个显然,我们来证明第二个:
举个例子,若$k=30$。
假设n=......00000
那你至多枚举到:
n=......03999,O(10^(k/9)) 个
你又至多枚举O(10^(k/9))个数从任意一个数枚举到
n=......00000