2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Площадь под дискретной гиперболой
Сообщение23.01.2013, 12:34 
Какова сложность получения суммы типа $  \sum_{i = 1}^{y_0}\lfloor\frac{z}{i} \rfloor$?
$z>y$
$z$,$y$,$y_0$ - натуральные числа
$ \lfloor\frac{z}{i} \rfloor$- целая часть $ \frac{z}{i} $
некоторые общие идеи здесь http://dxdy.ru/topic65477.html

 
 
 
 Re: Площадь под дискретной гиперболой
Сообщение23.01.2013, 13:38 
Вам ее надо точно вычислить или приближенно?
Для приближенной оценки при $y_0=z=y$ есть формула Дирихле. Точное значение, наверное, быстрее чем за $O(\sqrt{y})$ не посчитаешь :roll: (просто используется симметричность фигуры относительно прямой $y=x$) (если умеем считать $S(y,y,y)$ за $O(f(n))$, то автоматически умеем считать $\tau(y)=S(y,y,y)-S(y-1,y-1,y-1)$, а $\tau(y)$ вряд ли можно считать быстро).
Вообще, 3 параметра. По всем трем верхняя оценка нужна?

 
 
 
 Re: Площадь под дискретной гиперболой
Сообщение25.01.2013, 14:28 
Речь шла о точном значении. Спасибо!

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group