Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
Вычисление значения <tex>g(n+1)</tex> состоит из вычисления <tex>g(n)</tex>, проверки неравенства <tex>(\log_2 n)^{g(n)} \ge n</tex> и, возможно, запуска одной из двух внутренних функций. Время выполнения этих функций составляет:
<texli>T(n) \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \mathrm{SAT}))для случая </tex>; <tex>T(n) \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|)</tex>; <tex>T(n) \le k_1 n ((equiv 1 \log_2 n)^pmod{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n)</tex>; <tex>T(n) \le k_1 (n^2 + n^2 \log_2 n + n T(g, \log_2 n)):<br/tex>; <tex>T(n) \le k_1 (2n^3 + n T(g, \log_2 n))</tex>;parbox{0px}{* для случая <tex>g(n) \equiv 1 \pmodbegin{2align*}</tex>: <tex>T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(x)|) + T(f_i(x) \in \mathrm{SAT}))</tex>;\le \\ <tex>T(n) & \le k_2 n (2^{\log_2 n} \log_2 n + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n)</tex>;\le \\<tex>T(n) & \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n))</tex>;\le \\<tex>T(n) & \le k_2 (2n^3 + n T(g, \log_2 n))\end{align*}}</tex>.</li></ul>
Вычислить <tex>(\log_2 n)^{g(n)}</tex> можно за
<tex>k_3 \log_2 g(n) |(\log_2 n)^{g(n)}|^2 \le k_3 (g(n) |log_2 n|)^2 log_2 n \le k_3 n^3</tex>.
Таким образом,
<tex>T(g, n) \le T(g, n-1) + k (n^3 + n T(g, \log_2 n))</tex>.
Пусть <tex>T(g, 1) = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно
<tex>c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4</tex>.
