2019-gate-computer-science-and-it-practice.pdf/Q20-alg4 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
Худшее время <m>\Theta(n \log n)</m>, тогда амортизированная временная сложность <m>\Theta(\log n)</m>. | Худшее время <m>\Theta(n \log n)</m>, тогда амортизированная временная сложность <m>\Theta(\log n)</m>. | ||
| − | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf| | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|239|20}} |
{{question-ok|[[Участник:StasFomin|StasFomin]] 14:41, 25 декабря 2024 (UTC)}} | {{question-ok|[[Участник:StasFomin|StasFomin]] 14:41, 25 декабря 2024 (UTC)}} | ||
[[Категория:Анализ временной сложности]] | [[Категория:Анализ временной сложности]] | ||
Текущая версия на 14:50, 25 декабря 2024
Вопрос: Q20-alg4-31d68c
Пусть структура данных поддерживает операцию «foo», таким образом, что последовательность из n операций «foo» занимает времени в худшем случае. Какова амортизированная временная сложность операции «foo»?
Ответы
- Правильный ответ:
Объяснение
Худшее время , тогда амортизированная временная сложность .
Исходники — вопрос 20 на 239 странице книги «2019-gate-computer-science-and-it-practice.pdf»