用N阶算法作为最坏情况找到NxN矩阵的局部最小值 [英] finding local minimum of a NxN matrix with algorithm of order N as worst case

问题描述

如何在不使用O N ^ 2算法的情况下找到NxN矩阵的局部最小值，如下所示.当N变大时，时间永远长存.我需要将b排序为最坏情况的算法.

How do I find the local minimum of a NxN matrix without and O N^2 algorithm as below. The time takes for ever when N grows large. I need the algorithm to b order N as its worst case.

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);

推荐答案

简单的答案是:没有奇迹.

答案已包含在问题中. 1)您展示的算法确实具有O(N ² )的复杂度； 2)可以改进，但复杂度不能低于O(N ² ).

首先，让我们看看为什么复杂度是O(N ² ).如果您测试矩阵的所有N ² 个元素，它将为您带来所述的复杂性.如果您未全部测试它们，则可能会给出错误答案(最小错误数)，因为任何未经测试的值都可能小于找到的值.

实际速度取决于测试值集.就是说，存在不小的值的可能性，因为您可以更快地找到int.MinValue的值.在下面的解决方案中，这已得到考虑.这行评论可疑检查"稍微降低了复杂度，但增加了算法的绝对时间.总体而言，仅当数据中int.MinValue的概率足够高时，它才有用.通常，任何算法的实际性能都取决于生成数据集的方法.

现在，可以通过一个神秘的技巧来提高代码的性能:++j比j++更好.我通过使用foreach避免了for循环，请参见下文.信不信由你，它适用于多维数组.

另外，您需要修复错误.您100是一个错误，甚至不是错误，只是愚蠢.真正的解决方案是使用int.MaxValue.对于浮点类型，应该使用+Inf正确地与其他浮点值进行比较.

因此，这是固定的解决方案:

Short answer is: there is no such thing as miracle.

The answer is already contained in the question. 1) The algorithm you show is really of the O(N²) complexity; 2) It can be improved but the complexity cannot grow lower then O(N²).

First, let''s see why the complexity is O(N²). If you test all N² elements of the matrix, it gives you the said complexity. If you test not all of them, there is a chance of incorrect answer (false minimum) because any of the untested values can be less then the found value.

The real speed depends on the test set of values. That said, there is some probability that there is no less values, because you could sooner find the value of int.MinValue. In my solution below, this is taken into account. This line commented "questionable check" slightly reduce the complexity, but increase absolute time of the algorithm. Overall, it is useful only if the probability of int.MinValue in data is high enough. Generally, the real performance of any algorithm depends on the method of generation of data set.

Now, performance of your code could be improved by one mysterious trick: ++j makes better performance then j++. I avoided for loops by using foreach, please see below. Believe or not, it works correctly for multidimensional arrays.

Also, you need to fix a bug. You 100 is a bug, not even a bug, just foolishness. Real solution is using int.MaxValue. For floating point types, you should have used +Inf which correctly compares with other floating point values.

So, here is the fixed solution:

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

—SA

—SA

正如SAKryukov所说，问题是复杂度为O(N ² ).

有时，它有助于从不同角度查看问题:

• 如果在构造矩阵b时确定 min 属性并以某种方式对其进行缓存，则可能会有所帮助...假设矩阵一旦构造便是恒定的.
• 或更奇怪的是:将所有值存储在排序的结构中，并且仅从矩阵引用到这些值(可能具有某种引用计数机制)...假设您拥有庞大的矩阵，没有多少不同的值).
• ...
干杯

安迪

As SAKryukov said, the problem is of complexity O(N²).

Sometimes it helps to view the problem from a different angle:

• It might help if you determine that min property while constructing the matrix and cache it somehow... assuming the matrices are constant once they are constructed.
• Or even more weird: store all the values in a sorted structure and only refer from the matrix to these values (maybe with some reference counting mechanism)... assuming you have huge matrices with not many differing values).
• ...
Cheers

Andi

这篇关于用N阶算法作为最坏情况找到NxN矩阵的局部最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！