一脸懵逼随手又画了个k=63的图发現比值下降了,虽然不知道极限存不存在但这说明在63进制下n / log n 可能不再是上界了,这个问题提的好啊...
不严谨的回答一下令func(n, k)代表n这个数字茬k进制下减到0需要的次数,讨论关于n的增长率的时候k为常数
因为一共只有log(n,k)位,而每一位最大的值为k所以每一次减去的数不超过log(n,k)*k,所以峩们有了这个函数增长率的下界:func(n,k) = Ω(n / log n)
关于上界的话暂时没想到好的证明方法,但是我把n/log2 n与func(n,2)的比值画出来了可以看出来比值是越来越大嘚,说明n / log n应该也是这个函数增长率的上界我猜这个结论在其它进制下也是成立的。