109
правок
Изменения
м
→Построение f
===Построение <math>f</math>===
Зададим <math>f(0) = f(1) = 0</math>. Затем рекурсивно определим <math>f(n)</math>. Для этого рассмотрим три случая:
*<math>{(\log_2 n} ) ^ {f(n-1)} \ge n</math>:
*:<math>f(n) = f(n-1)</math>;
*<math>f(n-1)=2i</math>:
Первый случай позволяет сказать, что <math>f(n)</math> ограничена <math>O\left(\log_{\log_2 n} n\right) = O(\log_2 n)</math>.
Второй «ответственен» за множества <math>A_i</math> для чётных <math>i</math>, третий — для нечетных.
Логарифм в условии <math>|x| < \log_2 n</math> необходим для полиномиальности <math>f(n)</math>.
===Полиномиальность <math>f</math>===
