109
правок
Изменения
→Полиномиальность f
Покажем, что <tex>f \in \tilde{P}</tex>. Для упрощения будем считать, что алфавит <tex>\Sigma=\{0,1\}</tex>.
<tex>T(n) = T(n-1) + a(n)(b_1(n) + b_2(n) + b_3(n) + b_4(n)) + c_1(n) + c2_2c_2(n)</tex>, где:
*<tex>T(n-1)</tex> идёт на вычисление <tex>f(n-1)</tex>;
*<tex>a(n)</tex> — время перебора всех слов <tex>x</tex> таких, что <tex>|x| < \log_2 n</tex>;
*<tex>c_2(n)</tex> — время, необходимое для построения функции <tex>f_i</tex>.
<tex>a(n) = O\left(2^{\log_2 n}\right) = O(n)</tex>, таким образом <tex>a(n) \in \tilde{P}</tex>.
<tex>b_1(n) = O\left(i(\log_2 n)^i\right) = O\left(f(n-1)(\log_2 n)^{f(n-1)}\right) = O\left(f(n-1)n\right) = O(n^2) \in \tilde{P}</tex>
<tex>b_2(n) = O \left( 2^{\log_2 n} \log_2 n\right) = O\left(n \log_2 n\right) = O\left(n^2\right) \in \tilde{P}</tex>
<tex>b_3(n) = O \left(2^{\log_2 n} \log_2 n + \log_2 n\right) = O \left(n \log_2 n\right) = O\left(n^2\right) \in \tilde{P}</tex>
<tex>b_4(n) = b_3(b_1(n)) = O\left(n^4\right) \in \tilde{P}</tex>
Чтобы построить программу <tex>p_i</tex> достаточно построить <tex>\tilde{p_i}</tex>.
