问题求解

liu_cheng_ao 2018-02-06 13:12:55 2018-02-15 16:13:27

是否存在实数 0<\epsilon<1 满足:

\forall M\in \mathbb{N}^*,\exists a,b \in \mathbb{N}^*, a>M,b>M, \mathrm{s.t.} |\frac{a}{b}-\frac{1}{e}|<\frac{1}{(\lfloor \epsilon \sqrt{b} \rfloor)!}

其中 e 是自然对数的底。


如果存在这样的实数,下述算法的时间复杂度为 \Theta(\sqrt{n})

function inverse_element(x,n)
	if x<=1 then
		return x
	else
		return -(n/x)*inverse_element(n mod x,n) mod n
end function

UPD:问题已解决,由于下面的问题(Open Problem)被证明是 O(n^{1/3}) 的,故不存在满足条件的 \epsilon

共 3 条回复

riteme

这看上去不现实啊,根号b的阶乘怎么说也是指数级别的吧...

liu_cheng_ao

这里的时间复杂度是对于 0\le x<n 取最大值的 ……

spj

O(\sqrt n) 而不是 \Theta(\sqrt n) 吧, x=1 的时候是 \Theta(1) 的。