109
правок
Изменения
м
→Полиномиальность f
<math>a(n) = O\left(2^{\log_2 n}\right) = O(n)</math>, таким образом <math>a(n) \in \tilde{P}</math>.
<math>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}</math>
<math>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}</math>
<math>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}</math>
<math>b_4(n) = b3b_3(b1b_1(n)) = O\left(n^4\right) \in \tilde{P}</math>
Чтобы построить программу <math>p_i</math> достаточно построить <math>\tilde{p_i}</math>.
