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