Разработчик реализовал алгоритм обработки двух квадратных матриц размера N x N. Сначала алгоритм вычисляет произведение двух матриц с использованием трех вложенных циклов (стандартный алгоритм). Затем он находит максимальный элемент матрицы перебором всех ее элементов. Известно, что для N = 20 000 время выполнения алгоритма составляет 0,3 с. Оцените время выполнения (в секундах) при N = 200 000, если время выполнения одной операции сложения постоянно. В ответ запишите целое число.

Решение:

Алгоритм обработки двух матриц размера N x N с использованием трех вложенных циклов имеет сложность \( O(N^3) \) для умножения матриц и \( O(N^2) \) для поиска максимального элемента. Поскольку \( N^3 \) доминирует над \( N^2 \) при больших \( N \), общая сложность алгоритма — \( O(N^3) \).

Пусть \( T(N) \) — время выполнения алгоритма при размере матрицы \( N \). Тогда \( T(N) \) пропорционально \( N^3 \).

Дано: \( N_1 = 20 000 \), \( T(N_1) = 0.3 \) с.

Нужно найти: \( T(N_2) \) при \( N_2 = 200 000 \).

Составим соотношение:

\[ \frac{T(N_2)}{T(N_1)} = \left(\frac{N_2}{N_1}\right)^3 \]

Подставим известные значения:

\[ \frac{T(N_2)}{0.3} = \left(\frac{200000}{20000}\right)^3 \]

\[ \frac{T(N_2)}{0.3} = (10)^3 \]

\[ \frac{T(N_2)}{0.3} = 1000 \]

\[ T(N_2) = 0.3 \times 1000 \]

\[ T(N_2) = 300 \] с.

Ответ: 300