2001-gre-vs-practice.pdf/Q39

Ссылки сюда (1) →

Вопрос: Q39-e5724f

Задача зарезервирована: илья52 11:04, 21 декабря 2024 (UTC)

Для вычисления матричного произведения и , где содержит строк и столбцов, а - строк и столбцов, требуется время, пропорциональное , и в результате получается матрица из строк и столбцов. Рассмотрим произведение трех матриц , , , которые содержат, соответственно, строк и столбцов, строк и столбцов, а также строк и столбцов. При каком условии потребуется меньше времени, чтобы вычислить произведение как () , (т.е. сначала умножить первые две матрицы), или быстрее вычислить его как ()?

Ответы

• Нет такого условия, время всегда будет одним и тем же.
• Правильный ответ:

Объяснение

Исходники — вопрос 39 на 33 странице книги «2001-gre-vs-practice.pdf»

Оценим сколько времени нужно на умножение () .

Умножение () пропорцианально , получается матрица размера на . Далее результат умножается на . Время умножения пропорцианально .

Таким образом, первое умножение пропорцианально .

Аналогичными рассуждениями получаем, что умножение вторым способом пропорцианально .

По условию, первый способ должен занимать меньше времени, составим неравенство:

Разделим обе части на .

Получим неравенство .

StasFomin 19:04, 23 декабря 2024 (UTC): Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала все замечания по оформлению в канале, уже нет сил переделывать за всеми.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.