1

Очень многие тестирующие системы устанавливают максимальное время работы кода, моя история как раз об этом. Код не проходит на последнем тесте из-за превышения времени работы (дольше 1 сек). Задача такая: Вход : массив из чисел Вывод: массив, где каждый i,j элемент - это сумма всех элементов до ij-го введенного массива. Пример:

Вход
2 3
1 2 3
4 5 6

Выход

1 3 6
5 12 21

Мой кусочек кода:

    for (long int i = 0; i < array.rows; i++) {
        for (long int j = 0; j < array.cols; j++) {
            cin >> input;
            array.data[i][j] = input;
            long int k = 0;
            for (long int t = 0; t <= i; t++) {
                for (long int l = 0; l <= j; l++) {
                    k += array.data[t][l];
                }
            }
            cout << k << ' ';
        }
        cout << endl;
    }

Есть ли идеи, как ускорить?

2
  • 3
    Лучше, когда такие вопросы включают 1. абсолютно точную исходную постановку задачи со всеми деталями, 2. URL проверяющей системы. Очевидно, что если в таких системах не проходит по времени - надо не байты передвигать, а менять сам алгоритм.
    – Harry
    21 окт 2020 в 14:52
  • 1
    Правильное решение должно работать за O(n**2), а приведённое в вопросе работает за O(n**4).
    – Qwertiy
    21 окт 2020 в 14:55

2 ответа 2

6

Проблема в том, что ваше решение пересчитывает каждый раз заново всю сумму элементов, что приводит к ужасной асимптотике в О(n^4). Эту задачу можно решить с помощью динамического программирования. Для этого подумайте, как можно получить ответ для i,j за O(1) из уже имеющихся данных, а не за О(n^2) циклами.

Небольшая подсказка: пусть d - искомый массив. Как узнать d[i][j] зная значения a[i][j], d[i-1][j-1], d[i-1][j] и d[i][j-1]?

Это решение также позволяет помимо оптимизации времени работы до О(n^2) оптимизировать память до O(n) если заметить, что мы всегда работаем только с двумя строками массива d: текущей и предыдущей.

5

Код переведён с Питона отсюда, работает за n^2 (количество элементов в матрице).

Исходные данные в a[][], кумулятивные суммы в cs[][] такой же размерности. Если новый массив не требуется, а исходные данные сохранять не нужно, то вычисления можно производить внутри того же a[][].

Копируется первая строка, затем делается один проход с вычислением сумм по столбцам, затем проход с вычислением по строкам.

for (int c = 0; c < a.cols; c++)
    cs[0][c] = a[0][c];

for (int r = 1; r < a.rows; r++)
    for (int c = 0; c < a.cols; c++)
        cs[r][c] = cs[r-1][c] + a[r][c];

 for (int r = 0; r < a.rows; r++)
     for (int c = 1; c < a.cols; c++)
         cs[r][c] += cs[r][c-1];
1
  • 1
    я бы добавил в ответ пару строчек пояснений. О том, что cs - это массив промежуточных сумм, которые высчитываются одна из другой... Но Ваш ответ всё равно прекрасен!
    – S.H.
    21 окт 2020 в 15:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.