Литература по теории сложности

[vlad_light]

У нас сегодня была первая пара по теории сложности. Сперва решали задачи типа: при заданых $f(n)$ найти такое $g(n)$, что $f(n)=O(g(n))$. С этим проблем особых не возникало, хотя я бы ещё порешал таких задачек... Дальше решали задачи на длинну числа, а с этим вообще ничего непонятно было... Например, найти длинну числа $n!$. Подскажите, пожалуйста, литературу по этим темам: учебник и задачник (желательно с объяснением). Спасибо!

[mihailm]

определение длины числа дайте (как в лекциях было)

[vlad_light]

$1+[\frac{\ln n}{\ln 2}]$

[mihailm]

длина числа (натурального) это количество знаков в его двоичном разложении, что тут может быть сложного?
А чтобы посчитать длину факториала воспользуйтесь формулой Стирлинга

[vlad_light]

ща попробую:
$length(n!)=1+[\frac{n\ln (n)-n+\frac{1}{2}\ln (2\pi n)}{\ln 2}]$
Мы как-то по-другому решали, что-то типа такого:

$$length(n!)=1+[\frac{\ln (1\cdot 2\cdot ...\cdot n)}{\ln 2}]=1+[\frac{\sum\limits _{k=1}^n\ln (k)}{\ln 2}]=\sum\limits _{k=1}^n(1+\frac{\ln (k)}{\ln 2})+1-n=$$

$$\sum\limits _{k=1}^nlength(k)+1-n$$

Дальше я не знаю, как вон ту суму посчитать.

Цитата:

длина числа (натурального) это количество знаков в его двоичном разложении

Судя из этого получил формулу для

$$lenght(n)=\sum\limits_{k=1}^n k(2^k-2^{k-1}+1)$$

Подставляя в предыдущую формулу, получим:

$$1-n+\sum\limits _{k=1}^n\sum\limits_{i=1}^k i(2^i-2^{i-1}+1)$$

Как её крутить, я пока не представляю... Можете, пожалуйста, решить полностью подробно, скажем, этот или похожий пример, чтоб я понял суть. Я просто, если честно, даже не представляю, как должен выглядеть ответ... Буду очень благодарен!

(Оффтоп)

Вольфрам выдаёт что-то страшное...

$$\frac{1}{6}(n^3+3n^2+4(3\cdot 2^n+2)n-24(2^n-1))=O(n2^n)$$

если я правильно посчитал, конечно

[mihailm]

выкиньте числа меньшего порядка и получите что-то примерно
$nlog_2n$
по вашей формуле надо считать выделяя из числа большую степень двойки

[vlad_light]

Насколько я понял, по формуле Стирлинга, Вы хотите от меня увидеть:

$$length(n!)=1+[\frac{n\ln n+O(n)}{\ln 2}]=O(n\ln n)$$

Это и будет ответ?
И литературу напишите, если не сложно... Спасибо!

[mihailm]

в каком виде ответ требует преподаватель, в таком и надо,
про литературу я затрудняюсь ответить, может кто другой напишет