Помогите оценить сложность решения

[Алекс77]

Доброе время суток всем!

Необходимо "незамутненным" взглядом оценить сложность нижеприводимого решения задачи.

Количество действий F зависит от длинны ввода n.

1) $\forall n \leq N \Rightarrow F(n) \leq C $, где N и C - наперед известные константы.

2) $F(n) = C + F(\lfloor 0,75 n \rfloor) + F(\lceil 0,75 n \rceil) + \tau (\lfloor 0,75 n \rfloor) + \tau (\lceil 0,75 n \rceil) $,
где $\tau(n)$ - количество делителей числа n и для этой задачи $\tau(n) \leq \log_3 n$.

Помогите, пожалуйста, оценить сложность количества действий.

Заранее всем благодарен за помощь, подсказки и комментарии.

[Sonic86]

А оценивать штуки типа
$f(n)=C+2f(\frac{3}{4})n$ умеете?

$[t]\leqslant t, \lceil t\rceil<t+1$

[Алекс77]

Sonic86, скиньте, пожалуйста ссылки, где можно о подобных рекурсивных вычислениях почитать.
Вычисления, где есть порядковая связь между шагами (пример - числа Фибоначчи), более или менее стандартизированы, есть общедоступная методика.
А вот когда на четверть уменьшается размерность, тут сложнее, потому и прошу о подсказке/помощи.
Заранее благодарен!

[Xaositect]

Тут тоже есть общедоступная методика. Ключевые слова - теорема Акра-Баззи, например, тут: http://courses.csail.mit.edu/6.046/spri ... abazzi.pdf

[Алекс77]

Xaositect, огромное спасибо за ссылку, очень полезная статья!

Перевел, почитал, вник, хочу поделиться результатом, исправьте, если что упустил или ошибся.

Согласно уравнению (1) в этой статье получаем следующие результаты.

1) $k=1$;
2) $a=2$;
3) $b=0,75$;
4) $g(x)=C$;
5) Условие $$x_0=N$ удовлетворяет требованиям $N \geq \frac43 $ и $N \geq 4$.

Решение вспомогательного уравнения $ab^p=1$ приводит к результату $p=\log_{\frac34}{\frac12}=2,409...$

Таким образом получаем, что сложность решения F составляет:

$\Theta(F(n))=\Theta(n^p(1 + C $\int_1^n \frac{du}{u^{p + 1}}))$

Решение интеграла дает:
$$\int_1^n \frac{du}{u^{p + 1}}= \int_1^n u^{-p-1} du = \frac{n^{-p}}{-p}+\frac1p = \frac{1-n^{-p}}p$

Учитывая, что $ \frac{1-n^{-p}}p \leq \frac1p $, можно грубо оценить сложность решения F следующим образом:

$$\Theta(F(n))=\Theta(n^p(1+\frac Cp)) \approx \Theta(n^p) = \Theta(n^{2,409...})$

Следовательно, можно утверждать, что решение F является полиномиально ограниченным от n.

Поправьте, если в моих рассуждениях есть ошибка.
Заранее благодарен всем за комментарии, помощь в решении и подсказки.

[Xaositect]

Алекс77 в сообщении #893858 писал(а):

2) $F(n) = C + F(\lfloor 0,75 n \rfloor) + F(\lceil 0,75 n \rceil) + \tau (\lfloor 0,75 n \rfloor) + \tau (\lceil 0,75 n \rceil) $,
где $\tau(n)$ - количество делителей числа n и для этой задачи $\tau(n) \leq \log_3 n$.

Алекс77 в сообщении #895495 писал(а):

4) $g(x)=C$;

По условию получается $g(x) = O(\log n)$.

Дальше все правильно, и результат будет тот же, потому что $\frac{\log u}{u^{p+1}} = O(\frac{1}{u^{p + 1 - \varepsilon}})$ и поэтому $\int_1^{\infty} \frac{\log u}{u^{p+1}}du$ сходится.

[Алекс77]

Xaositect, еще раз огромное спасибо за помощь!!!