2004-gre-cs-practice-book.pdf/Q12 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 28: Строка 28:
 
{{question-ok|}}
 
{{question-ok|}}
  
−
[[Категория:Анализ временной сложности]]
+
[[Категория:Рекуррентные соотношения]]

Версия 00:19, 14 декабря 2024

Вопрос: Q12-4c9f66

Вопрос: Анализ алгоритма

Пусть T(n) определяется как и для всех целых чисел

Какое из следующих утверждений представляет порядок роста T(n) как функции n?

Ответы

  • Правильный ответ:

Объяснение

Исходники — вопрос 12 на 17 странице книги «2004-gre-cs-practice-book.pdf» 

from sympy import *
T = Function('T')
n = symbols('n', integer=True, positive=True)
recurrence = T(n+1) - T(n) - 3*n
latex(rsolve(recurrence, T(n), {T(1):7}))
Источник — «https://discopal.ispras.ru/index.php?title=2004-gre-cs-practice-book.pdf/Q12&oldid=33436»