2004-gre-cs-practice-book.pdf/Q12 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q12-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q12-4c9f66 == | == Вопрос: Q12-4c9f66 == | ||
| + | == Вопрос: Анализ алгоритма == | ||
| − | < | + | Пусть ''T(n)'' определяется как <m>T(1)=7</m> и <m>T(n+1)=3n+T(n)</m> для всех целых чисел <m>n \ge 1</m> |
| − | + | ||
| − | + | Какое из следующих утверждений представляет порядок роста ''T(n)'' как функции ''n''? | |
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>Q(n)</m> |
| − | ( | + | * <m>Q(n\log(n))</m> |
| + | * Правильный ответ: <m>Q(n^2)</m> | ||
| + | * <m>Q(n^2\logn)</m> | ||
| + | * <m>Q(2^n)</m> | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|17|12}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | <m>\frac{3 n \left(n - 1\right)}{2} + 7</m> |
| − | + | ||
| − | + | ||
| + | <code-python> | ||
| + | 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})) | ||
| + | </code-python> | ||
| − | + | {{question-ok|}} | |
| − | + | ||
| − | {{ | + | |
| − | + | [[Категория:Анализ временной сложности]] | |
| − | + | ||
| − | + | ||
Версия 00:17, 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}))