Броят на делителите на N
Често при олимпиадни задачи, за да се оцени асимптотиката на алгоритъма, се изисква да се знае приблизителният брой делители на входното число. По-точно, изисква се да се знае максималния брой делители сред всички числа до, да речем, милиард.
Най-грубата оценка е O (sqrt(N)), а именно най-много два квадратни корена от N.
Но често това се оказва твърде груба оценка, неоправдано надценена.
Обичайната оценка, която използвам, еO(кубичен корен от N). Чух тази мистериозна оценка от някого преди много време и никога не съм я разбирал, но я използвах и тя проработи.
Съвсем наскоро направихме стрес тест и при числа до милиард беше потвърдено - броят на делителите не надвишава два кубични корена от числото. Тези „доказателства“ са напълно достатъчни, за да продължим да прилагаме тази оценка на практика. Но нямаше начин да се намери математическо обяснение за това.
Днес за пореден път реших да потърся тази тема в интернет. Този път го намерих. това, от което се нуждаете, е изненадващо бързо:en.wikipedia.org/wiki/Divisor_function. Тук има много интересни неща, но ето основното, удивителната за мен формула:
"за всеки eps>0: d(n) = o(n^eps)"
Оказва се, че всъщност броят на делителите се държи в безкрайност не само по-добре от квадратния, кубичния и други корени на числото n; това обикновено есубполиномиално количество!
n ^ (log2 / log log n)" (е, аз грубо преминах реда, всъщност формулата е по-сложна там) Дирихле: "SUM_ d(i) / n