2019-gate-computer-science-and-it-practice.pdf/Q21-alg3 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q21-alg3-31d68c == <blockquote> Вопрос из «Algorithms Test 3» где-то со страницы 233. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q21-alg3-31d68c == | == Вопрос: Q21-alg3-31d68c == | ||
| − | < | + | Какая временная сложность выполнения данного кода? |
| − | + | <code-cpp> | |
| − | + | for (i = n; i > 0; i/= 2){ | |
| − | + | for (int j = 1; j < n; j * = 2){ | |
| − | + | for (int k = 0; k < n; k + = 2){ | |
| − | + | sum + = (i + j * k); | |
| − | + | } | |
| − | + | } | |
| − | + | } | |
| − | + | </code-cpp> | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>O(n^3)</m> |
| − | ( | + | * <m>O(n^2\log n)</m> |
| − | + | * <m>O(\log n * \log n * \log n)</m> | |
| − | * | + | * Правильный ответ: <m>O(n * \log n * \log n)</m> |
| − | * | + | |
| − | * | + | |
| − | * | + | |
| − | * | + | |
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | + | * Во внешнем цикле for переменная ''i'' уменьшается вдвое, поэтому она проходит цикл (''log n'') раз. | |
| − | + | * Для каждого следующего цикла ''i'' также выполняется цикл (''log n'') раз из-за удвоения переменной ''j''. | |
| − | + | * Самый внутренний цикл на ''k'' выполняется ''n/2'' раза. | |
| − | + | * Циклы являются вложенными, поэтому границы должны быть умножены. | |
| − | + | * В результате, получается значение алгоритма <m>O(n * \log n * \log n)</m>. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|234|21}} |
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 10:32, 25 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Анализ временной сложности]] |
| + | [[Категория:Понимание кода]] | ||
Текущая версия на 10:32, 25 декабря 2024
Вопрос: Q21-alg3-31d68c
Какая временная сложность выполнения данного кода?
for (i = n; i > 0; i/= 2){ for (int j = 1; j < n; j * = 2){ for (int k = 0; k < n; k + = 2){ sum + = (i + j * k); } } }
Ответы
- Правильный ответ:
Объяснение
- Во внешнем цикле for переменная i уменьшается вдвое, поэтому она проходит цикл (log n) раз.
- Для каждого следующего цикла i также выполняется цикл (log n) раз из-за удвоения переменной j.
- Самый внутренний цикл на k выполняется n/2 раза.
- Циклы являются вложенными, поэтому границы должны быть умножены.
- В результате, получается значение алгоритма .
Исходники — вопрос 21 на 234 странице книги «2019-gate-computer-science-and-it-practice.pdf»