d*z
发帖数: 150 | 1
the len of r and s are no more than 2n
so
First we can get x+y=r-s+1 in O(n)
The time to get u=(x+y)(x+y)-4r is O(nlog(n)).
and the time to find x-y=sqrt(u) should be O(
n*log(n)log(n)log(log(n)) ).
so I think the time is O( n*log(n)*log(n)*log(log(n)) ).
Of course it is less than O(n*n). That's in polynomial time.
But in the fact, the comment algorithm to multiply and divid
is both O(n*n).
As to the sqrt(), we can use
x(n)=(x(n-1)*x(n-1)+a)/(2*x(n-1))
to found the sqrt(a), we only need to iter |
|
