2019-gate-computer-science-and-it-practice.pdf/Q11-alg2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q11-alg2-31d68c == <blockquote> Вопрос из «Algorithms Test 2» где-то со страницы 226. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q11-alg2-31d68c == | == Вопрос: Q11-alg2-31d68c == | ||
| + | Какие из представленных ниже утверждений являются верными? | ||
| − | < | + | # <m>3n + 1 \in O(3^n)</m> |
| − | + | # <m>100n\log n \in O(n\log n)</m> | |
| − | + | # <m>2n \neq O(n^K)</m>, <m>K</m> — константа | |
| − | + | # <m>n^j \in O(n^i), 0<i<j</m> | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
=== Ответы === | === Ответы === | ||
| − | + | * Правильный ответ: i, ii, iii | |
| − | + | * i, ii, iv | |
| − | + | * ii, iii | |
| − | * | + | * i, ii |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | <i> | + | Пусть <m>0 < i < j</m>, тогда по определению: |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | <m>n^j \neq c * n^i</m> что является неверным. | |
| − | + | ||
| − | + | ||
| − | + | Первые три утверждения верные по определению ограниченных сверху функций. | |
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|226|11}} |
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 01:01, 25 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Анализ временной сложности]] |
Текущая версия на 01:01, 25 декабря 2024
Вопрос: Q11-alg2-31d68c
Какие из представленных ниже утверждений являются верными?
- , — константа
Ответы
- Правильный ответ: i, ii, iii
- i, ii, iv
- ii, iii
- i, ii
Объяснение
Пусть , тогда по определению:
что является неверным.
Первые три утверждения верные по определению ограниченных сверху функций.
Исходники — вопрос 11 на 226 странице книги «2019-gate-computer-science-and-it-practice.pdf»