2019-gate-computer-science-and-it-practice.pdf/Q32-alg1 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q32-alg1-31d68c == | == Вопрос: Q32-alg1-31d68c == | ||
| − | + | Какое из следующих рекуррентных соотношений не может быть использовано в оценке времени работы алгоритма быстрой сортировки? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>T(n)=T\left(\frac{6n}{10}\right) + T\left(\frac{4n}{10}\right) + \Theta(n)</m> |
| − | ( | + | * <m>T(n)=T\left(\frac{4n}{5}\right) + T\left(\frac{n}{5}\right) + \Theta(n)</m> |
| − | + | * <m>T(n)=T\left(n-1\right) + T\left(1\right) + \Theta(n)</m> | |
| − | * | + | * Правильный ответ: <m>T(n)=T\left(\frac{4n}{5}\right) + T\left(\frac{4n}{5}\right) + \Theta(n)</m> |
| − | * | + | |
| − | + | ||
| − | * | + | |
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | + | Данный массив разбивается на два непустых подмассива. | |
| − | + | В правильном ответе разбиение означает, что в первой части массива находится 80 процентов чисел, значит во второй части массива должно быть 20 процентов. Таким образом вместо <m>T\left(\frac{4n}{5}\right)</m> нужно <m>T\left(\frac{n}{5}\right)</m>. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|225|32}} | |
| − | |||
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 00:19, 25 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Sorting]] |
| + | [[Категория:Рекуррентные соотношения]] | ||
Текущая версия на 00:19, 25 декабря 2024
Вопрос: Q32-alg1-31d68c
Какое из следующих рекуррентных соотношений не может быть использовано в оценке времени работы алгоритма быстрой сортировки?
Ответы
- Правильный ответ:
Объяснение
Данный массив разбивается на два непустых подмассива. В правильном ответе разбиение означает, что в первой части массива находится 80 процентов чисел, значит во второй части массива должно быть 20 процентов. Таким образом вместо нужно .
Исходники — вопрос 32 на 225 странице книги «2019-gate-computer-science-and-it-practice.pdf»