2019-gate-computer-science-and-it-practice.pdf/Q02-alg4 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q02-alg4-31d68c == <blockquote> Вопрос из «Algorithms Test 4» где-то со страницы 238. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q02-alg4-31d68c == | == Вопрос: Q02-alg4-31d68c == | ||
| − | + | Рассмотрим массив из ''n'' элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>O(n)</m> |
| − | ( | + | * <m>O(n^2)</m> |
| − | + | * Правильный ответ: <m>O(n \log n)</m> | |
| − | * Правильный ответ: | + | * <m>O(\log n)</m> |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | < | + | Отсортируем массив за <m>O(n \log n)</m> и возьмем три последних элемента в нем. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|238|2}} |
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 12:43, 25 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Sorting]] |
Текущая версия на 12:43, 25 декабря 2024
Вопрос: Q02-alg4-31d68c
Рассмотрим массив из n элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве?
Ответы
- Правильный ответ:
Объяснение
Отсортируем массив за и возьмем три последних элемента в нем.
Исходники — вопрос 2 на 238 странице книги «2019-gate-computer-science-and-it-practice.pdf»