171
правка
Изменения
м
Время выполнения шагов вычисления Вычисление значения <tex>g(n+1)</tex> состоит из вычисления <tex>g(n)</tex>, проверки неравенства <tex>(\log_2 n)^{g(n)} \ge n</tex> и, возможно, запуска одной из двух внутренних функций. Время выполнения этих функций составляет:
Нет описания правки
Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>.
* для случая <tex>g(n) = 2i\equiv 0 \pmod{2}</tex>:
<tex>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 (2n^3 + n T(g, \log_2 n))</tex>;
* для случая <tex>g(n) = 2i + \equiv 1\pmod{2}</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>;
