shekarchee Ответов: 3

нахождение локального минимума матрицы NxN с алгоритмом Порядка N в наихудшем случае

Как найти локальный минимум матрицы NxN без алгоритма and O N^2, как показано ниже. Время уходит навсегда, Когда N становится большим. Мне нужен алгоритм для B Порядка N в худшем случае.

int row = 0;
           int column = 0;
           Random random = new Random();


           int[,] matrix = new int[10, 10];
           for (int r = 0; r < 10; r++)
           {
                for (int c = 0; c < 10; c++)
                {
                     int randomNumber = random.Next(0, 100);
                     matrix[r, c] = randomNumber;
                }
           }


           int min = 100;
           Stopwatch timer = new Stopwatch();
           timer.Start();

           for (int i = 0; i < matrix.GetLongLength(0); i++)
           {
                for (int j = 0; j < matrix.GetLongLength(1); j++)
                {
                     if (matrix[i, j] < min)
                     {
                          min = matrix[i, j];
                     }

                }
           }
           timer.Stop();
          double time = timer.ElapsedMilliseconds;
          Console.WriteLine(time);

Sergey Alexandrovich Kryukov

Что такое "локальный минимум"? Как вы думаете, есть ли "глобальный" и "локальный" минимум? :-)
--СА

Andreas Gieriet

Если скорость действительно важно, что вы можете подумать о программировании этого на каком-нибудь более подходящем языке. Может Быть, C/C++? Сложность по-прежнему NxN, но может быть меньше накладных расходов.

3 Ответов

Рейтинг:
2

Andreas Gieriet

Как сказал Сакрюков, проблема имеет сложность O(N2).

Иногда это помогает взглянуть на проблему с другой стороны:


  • Это может помочь, если вы определите, что минута собственность пока строящий матрицу и каким-то образом кэшировать ее... предполагая, что матрицы постоянны, как только они построены.
  • Или еще более странно: храните все значения в отсортированной структуре и только относиться от матрицы к этим значениям (возможно, с помощью какого-то механизма подсчета ссылок)... предполагая, что у вас есть огромные матрицы с небольшим количеством отличающихся значений).
  • ...
    • Овации

    Энди

Рейтинг:
1

jkool_

Я думаю, что эта проблема имеет следующий фокус:
найти локальный минимум:
пара индексов i и j такая, что m[i][j] < m[i+1][j], m[i][j] < m[i][j+1],
m[i][j] < m[i-1][j], и m[i][j] < m[i][j-1]. Следовательно, можно достичь O(n).
Ниже приведен пример на Java, надеюсь, он будет полезен.

public static void main(String[] args) {
        int[][] m = {{4, 5, 20, 31, 1}
                    ,{7, 31, 11, 8, 7}
                    ,{20, 29, 13, 19, 33}
                    ,{6, 16, 17, 27, 39}
                    ,{32, 37, 24, 26, 41}};
        
        int value = findLocalMinimum(m);
        System.out.println("value: "+value);
    }
    
    private static int findLocalMinimum(int m[][]){ 
        return find(m, m.length/2, m.length/2); //O(n)
    }
    
    private static int find(int m[][], int a, int b){
        if( (b == 0 || m[a][b-1] > m[a][b]) && (b == m.length-1 || m[a][b+1] > m[a][b]) && 
            (a == 0 || m[a-1][b] > m[a][b]) && (a == m.length-1 || m[a+1][b] > m[a][b]))
            return m[a][b];
        else if(b > 0 && m[a][b-1] < m[a][b])
            return find(m, a, b-1);
        else if(b < m.length-1 && m[a][b+1] < m[a][b])
            return find(m, a, b+1);
        else if(a > 0 && m[a-1][b] < m[a][b])
            return find(m, a-1, b);
        else 
            return find(m, a+1, b);
    }

С уважением!

Рейтинг:
0

Sergey Alexandrovich Kryukov

Короткий ответ: нет такой вещи, как чудо.

Ответ уже содержится в вопросе. 1) алгоритм, который вы показываете, действительно имеет O(N2 2 ) она может быть улучшена, но сложность не может расти ниже, чем O(N2).

Во-первых, давайте посмотрим, почему сложность равна O(N2). Если вы проверите все N2 элементы матрицы, это дает вам упомянутую сложность. Если вы проверяете не все из них, есть вероятность неправильного ответа (ложный минимум), потому что любое из непроверенных значений может быть меньше найденного значения.

Реальная скорость зависит от тестового набора значений. Тем не менее, существует некоторая вероятность того, что существует не меньше значений, потому что вы могли бы скорее найти значение int.MinValue В моем решении ниже это учтено. Эта строка с комментарием "сомнительная проверка" несколько снижает сложность, но увеличивает абсолютное время работы алгоритма. В целом, это полезно только в том случае, если вероятность int.MinValue в данных достаточно высока. Как правило, реальная производительность любого алгоритма зависит от способа генерации набора данных.

Теперь производительность вашего кода может быть улучшена одним таинственным трюком: ++j тогда получается лучшая производительность j++ Я избегал этого . for циклы с помощью foreach, пожалуйста, смотрите ниже. Хотите верьте, хотите нет, но он работает правильно для многомерных массивов.

Кроме того, вам нужно исправить ошибку. Вы 100-это ошибка, даже не ошибка, просто глупость. Реальное решение заключается в использовании int.MaxValue Для типов с плавающей запятой вы должны были использовать +Inf который правильно сравнивается с другими значениями с плавающей запятой.

Итак, вот фиксированное решение:

internal static int Minimum(int[,] matrix) {
    int result = int.MaxValue; //sic!
    foreach(int value in matrix) {
        if (value == int.MinValue) return value; // questionable check
        if (value < result)
            result = value;
    } //loop
    return result;
} //Minumum


—СА