помогите решить найти общую форумулу для рекурсии

[Invisible]

Помогите плиз решить два примера



$ T(n)=$\sqrt n$$T(\sqrt n)+n
$T(2)=1 $


$ T(n)=2T(\frac n 2)+n log_2 n
$T(1)=1 $

[maxal]

$T(n) = \Theta(n \log \log n)$
и
$T(n) = \Theta(n \log^2 n)$

[Invisible]

maxal а можно общую формулу (не рекурсивную)
а не асимптотическую функцию

спасибо

[PAV]

Что-то я не понял, как быть в первом случае, если $n$ не является полным квадратом и в втором случае, если $n$ нечетное?

Типа, $T(3)$ в каждом из двух случаев как ищется?

[Invisible]

PAV писал(а):

Что-то я не понял, как быть в первом случае, если $n$ не является полным квадратом и в втором случае, если $n$ нечетное?

Типа, $T(3)$ в каждом из двух случаев как ищется?

такие условия задачи.

мое мнение, те значения думаю не учитываются так как это для больших n
думаю случаи $T(3)$ пренебрегаются

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

никто не может помочь чтоб сверится?

[esperanto]

Интересно, я такое задание дал своим на прошлой неделе на дом. Так что подсказывать не буду.

ХОтя первое уравнение решается подходящей заменой

[maxal]

$$T(2^{2^k}) = (2k+1) 2^{2^k - 1}$$

и

$$T(2^k) = (k^2 + k+ 2) 2^{k - 1}$$

[Invisible]

maxal большое спасибо

esperanto я точно не ваш ученик, не волнуйтесь

[Invisible]

У меня еще вопрос
я ищу O(n);
могу ли я
рекурсивную формулу:

$$T(n)= \begin{cases} n,&\text{если $n\le3$;}\\ T(n)=T(\lfloor \frac n 2 \rfloor) + T(\lfloor \frac n 3 \rfloor) +T(\lceil \frac n 4 \rceil) +n^2\\ \end{cases} $$

оценить как
$T(n) \le 3T( \frac n 2 )+n^2$

(ведь $ \frac n 4 \le \frac n 3 \le \frac n 2$ )

или это сильно грубая оценка?

[maxal]

Не проще ли доказать оценку $T(n)\sim c n^2,$ где константа $c$ удовлетворяет равенству:
$c = c\cdot\left(\frac{1}{4} + \frac{1}{9} + \frac{1}{16}\right) + 1,$
т.е. $c=\frac{144}{83}.$

[esperanto]

Invisible писал(а):

У меня еще вопрос
я ищу O(n);
могу ли я
рекурсивную формулу:

$$T(n)= \begin{cases} n,&\text{если $n\le3$;}\\ T(n)=T(\lfloor \frac n 2 \rfloor) + T(\lfloor \frac n 3 \rfloor) +T(\lceil \frac n 4 \rceil) +n^2\\ \end{cases} $$

оценить как
$T(n) \le 3T( \frac n 2 )+n^2$

(ведь $ \frac n 4 \le \frac n 3 \le \frac n 2$ )

или это сильно грубая оценка?

можете

[Invisible]

maxal, esperanto спасибо