Форум программистов, компьютерный форум CyberForum.ru

Оптимизировать алгоритм - C++

Восстановить пароль Регистрация
 
Wolkodav
 Аватар для Wolkodav
599 / 452 / 32
Регистрация: 18.09.2012
Сообщений: 1,685
24.12.2013, 00:54     Оптимизировать алгоритм #1
Приятель подкинул задачку:
Получить новую матрицу В, элемент b[i][j] которой равен наименьшему из элементов a[k][l] исходной матрицы, где k меняется от i до n, а l – от 1 до j. С у четом, что Матрица А исходная.
Он предложил решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void preobr (int **A, int **&B,const int n,const int m)
{
B=new int*[n];
for (int i=0; i<n; i++)
    B[i]=new int [m];
for (int i=0; i<n; i++)
    for (int j=0; j<m; j++)
    {
        int min=A[i][j];
        for (int k=i; k<n; k++)
            for (int l=0; l<j; l++)
                if (A[k][l]<min) min=A[k][l];
                    B[i][j]=min;
    }
}
Преподователь сказала, что нужно сделать оптимальнее
Чтобы трудоемкость была не n^4, а 3*n^2. Ничего лучше не придумали, может хоть кто-нибудь идейку подскажет?

Добавлено через 1 час 54 минуты
Нету идей?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2013, 00:54     Оптимизировать алгоритм
Посмотрите здесь:

C++ оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
C++ Нужно оптимизировать
Оптимизировать перебор C++
C++ Оптимизировать вычисление формулы
C++ Оптимизировать функцию
C++ Оптимизировать код
C++ Оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления
C++ Оптимизировать и минимализировать код

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.12.2013, 07:51     Оптимизировать алгоритм #2
Цитата Сообщение от Wolkodav Посмотреть сообщение
может хоть кто-нибудь идейку подскажет?
идея здесь только одна может быть. внимательно читаем условие и понимаем что нужно искать минимальное число в прямоугольном секторе ограниченном точками A[n-1][0] и A[i][j] (точки находятся на концах диагонали прямоугольника). Так вот если идти не с 0-ой строки вниз, а наоборот с n-1 строки вверх то получится, что для очередной точки B[i][j] можно минимум вычислить так: выбрать минимально значение из трех значений: A[i][j], B[i+1][j], B[i][j-1].
И все, единственное остается проверять что не выходим за границы матрицы, когда берем значения: B[i+1][j], B[i][j-1].
Yandex
Объявления
24.12.2013, 07:51     Оптимизировать алгоритм
Ответ Создать тему
Опции темы

Текущее время: 16:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru