2001-gre-vs-practice.pdf/Q39 — различия между версиями
Материал из DISCOPAL
Илья52 (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | == Вопрос: Q39-e5724f == | |
| + | Для вычисления матричного произведения <m>M_1</m> и <m>M_2</m>, | ||
| + | * где <m>M_1</m> содержит ''p''-строк и ''q'' столбцов, | ||
| + | * <m>M_2</m> — ''q'' строк и ''r'' столбцов, | ||
| + | * требуется время, пропорциональное ''p × q × r'' , и в результате получается матрица из ''p'' строк и ''r'' столбцов. | ||
| + | ** алгоритм Штрассена или алгоритм Копперсмита-Винограда не рассматриваем. | ||
| − | + | Рассмотрим произведение трех матриц | |
| − | + | * <m>N_1</m> — ''w'' строк и ''x'' столбцов | |
| − | + | * <m>N_2</m> — ''x'' строк и ''y'' столбцов | |
| − | + | * <m>N_3</m> — ''y'' строк и ''z'' столбцов. | |
| − | Рассмотрим произведение трех матриц <m>N_1</m> | + | |
| − | как (<m>N_1</m><m>N_2</m>) <m>N_3</m>, ( | + | При каком условии потребуется меньше времени, чтобы вычислить произведение как (<m>N_1</m> × <m>N_2</m>) × <m>N_3</m>, (то есть сначала умножить первые две матрицы), или быстрее вычислить его как <m>N_1</m> × (<m>N_2</m> × <m>N_3</m>)? |
| − | + | ||
=== Ответы === | === Ответы === | ||
| Строка 18: | Строка 22: | ||
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2001-gre-vs-practice.pdf|33|39}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Оценим сколько времени нужно на умножение (<m>N_1</m> × <m>N_2</m>) × <m>N_3</m>. | |
| − | + | На всякий случай, повод вспомнить стандартный механизм умножения двух матриц (скажем <m>N_1</m> × <m>N_2</m>). | |
| + | * Для каждого элемента результирующей матрицы, которая будет иметь размер ''w × y'' необходимо вычислить скалярное произведение строки из первой и столбца из второй. | ||
| + | * Каждое скалярное произведение включает ''x'' умножений и ''x - 1'' сложений. | ||
| + | * Общее количество операций равно: | ||
| + | <m>w \times y \times (x \text{ умножений} + (x - 1) \text{ сложений}) \approx w \times x \times y </m> | ||
| − | + | Умножение (<m>N_1</m> × <m>N_2</m>) пропорционально ''wy'', получается матрица размера ''w × y''. Далее результат умножается на <m>N_3</m>. Время умножения пропорционально ''wyz''. | |
| − | + | Таким образом, первое умножение пропорционально ''wxy + wyz''. | |
| − | + | Аналогичными рассуждениями получаем, что умножение вторым способом пропорционально ''xyz + wxz''. | |
| − | + | По условию, первый способ должен занимать меньше времени, составим неравенство: | |
| − | < | + | ''wxy + wyz < xyz + wxz'' |
| − | + | Разделим обе части на ''wxyz''. | |
| − | {{ | + | Получим неравенство <m>\frac{1}{x} + \frac{1}{z} < \frac{1}{w} + \frac{1}{y}</m>. |
| − | [[Участник:StasFomin|StasFomin]] | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 22:21, 27 декабря 2024 (UTC)}} |
| − | [[Категория: | + | [[Категория:Умножение матриц]] |
| + | [[Категория:Анализ временной сложности]] | ||
Текущая версия на 22:21, 27 декабря 2024
Вопрос: Q39-e5724f
Для вычисления матричного произведения и ,
- где содержит p-строк и q столбцов,
- — q строк и r столбцов,
- требуется время, пропорциональное p × q × r , и в результате получается матрица из p строк и r столбцов.
- алгоритм Штрассена или алгоритм Копперсмита-Винограда не рассматриваем.
Рассмотрим произведение трех матриц
- — w строк и x столбцов
- — x строк и y столбцов
- — y строк и z столбцов.
При каком условии потребуется меньше времени, чтобы вычислить произведение как ( × ) × , (то есть сначала умножить первые две матрицы), или быстрее вычислить его как × ( × )?
Ответы
- Нет такого условия, время всегда будет одним и тем же.
- Правильный ответ:
Объяснение
Исходники — вопрос 39 на 33 странице книги «2001-gre-vs-practice.pdf»
Оценим сколько времени нужно на умножение ( × ) × .
На всякий случай, повод вспомнить стандартный механизм умножения двух матриц (скажем × ).
- Для каждого элемента результирующей матрицы, которая будет иметь размер w × y необходимо вычислить скалярное произведение строки из первой и столбца из второй.
- Каждое скалярное произведение включает x умножений и x - 1 сложений.
- Общее количество операций равно:
Умножение ( × ) пропорционально wy, получается матрица размера w × y. Далее результат умножается на . Время умножения пропорционально wyz.
Таким образом, первое умножение пропорционально wxy + wyz.
Аналогичными рассуждениями получаем, что умножение вторым способом пропорционально xyz + wxz.
По условию, первый способ должен занимать меньше времени, составим неравенство:
wxy + wyz < xyz + wxz
Разделим обе части на wxyz.
Получим неравенство .