2001-gre-vs-practice.pdf/Q39 — различия между версиями
Илья52 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | == Вопрос: Q39-e5724f == | |
{{reserve-task|[[Участник:Илья52|илья52]] 11:04, 21 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Илья52|илья52]] 11:04, 21 декабря 2024 (UTC)}} | ||
<blockquote> | <blockquote> | ||
| Строка 40: | Строка 40: | ||
{{question-ok|}} | {{question-ok|}} | ||
| + | |||
| + | {{Badsol}} | ||
| + | |||
| + | [[Участник:StasFomin|StasFomin]] 19:04, 23 декабря 2024 (UTC): Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала [https://t.me/c/2489499765/78/191 все замечания по оформлению в канале], уже нет сил переделывать за всеми. | ||
[[Категория:Надо не забыть выбрать тему]] | [[Категория:Надо не забыть выбрать тему]] | ||
Версия 19:07, 23 декабря 2024
Вопрос: Q39-e5724f
Задача зарезервирована: илья52 11:04, 21 декабря 2024 (UTC)
Для вычисления матричного произведения и , где содержит строк и столбцов, а - строк и столбцов, требуется время, пропорциональное , и в результате получается матрица из строк и столбцов. Рассмотрим произведение трех матриц , , , которые содержат, соответственно, строк и столбцов, строк и столбцов, а также строк и столбцов. При каком условии потребуется меньше времени, чтобы вычислить произведение как () , (т.е. сначала умножить первые две матрицы), или быстрее вычислить его как ()?
Ответы
- Нет такого условия, время всегда будет одним и тем же.
Объяснение
Исходники — вопрос 39 на 33 странице книги «2001-gre-vs-practice.pdf»
Оценим сколько времени нужно на умножение () .
Умножение () пропорцианально , получается матрица размера на . Далее результат умножается на . Время умножения пропорцианально .
Таким образом, первое умножение пропорцианально .
Аналогичными рассуждениями получаем, что умножение вторым способом пропорцианально .
По условию, первый способ должен занимать меньше времени, составим неравенство:
Разделим обе части на .
Получим неравенство .
Правильный ответ: 2.
