假设我有一个n:n矩阵，其中short只有正值，如下所示：
0 1 0 3
1 0 5 6
7 1 0 4
6 2 7 9
我正在这个矩阵中搜索一个m:m矩阵，其中包含大多数大于 0 的值。我的问题是我到目前为止的解决方案不能很好地扩展n（也不m）。
事实上，n:n矩阵代表产品的价格，轴代表给定（任意）日期的天数。因此，您可以在给定的时间间隔内搜索价格。该m:m矩阵实际上是一个 7 x 7 矩阵，其中包含价格的子集（如视图）。我正在寻找n:n我填写的价格最多的矩阵部分。
在上面的例子中，m:m矩阵是
7 1
6 2
2在哪里m。
以下是我迄今为止编写的原型的相关部分：
private static class ResultMatrixData {
private byte fillCount;
private short distanceFromToday;
public ResultMatrixData() {
fillCount = 0;
distanceFromToday = Short.MAX_VALUE;
}
public ResultMatrixData(short[][] pricesMatrix, short iArg, short jArg) {
byte fillCount = 0;
for (int i = iArg; i < iArg + 7; i++) {
for (int j = jArg; j < jArg + 7; j++) {
if (pricesMatrix[i][j] > 0) {
fillCount++;
}
}
}
this.fillCount = fillCount;
distanceFromToday = iArg > jArg ? iArg : jArg;
}
}
private ResultMatrixData calculateSingleResult(short[][] pricesMatrix) {
ResultMatrixData bestSoFar = new ResultMatrixData();
ResultMatrixDataComparator comparator = new ResultMatrixDataComparator();
for (short i = 0; i < NUMBER_OF_DAYS - 6; i++) {
for (short j = 0; j < NUMBER_OF_DAYS - 6; j++) {
ResultMatrixData current = new ResultMatrixData(pricesMatrix, i, j);
if (comparator.compare(current, bestSoFar) >= ResultMatrixDataComparator.GREATER_THAN) {
bestSoFar = current;
}
}
}
return bestSoFar;
}
private static class ResultMatrixDataComparator implements Comparator<ResultMatrixData> {
private static final int LESS_THAN = -1;
private static final int EQUAL = 0;
private static final int GREATER_THAN = 1;
@Override
public int compare(ResultMatrixData first, ResultMatrixData second) {
if (first.fillCount > second.fillCount) {
return GREATER_THAN;
} else if (first.fillCount < second.fillCount) {
return LESS_THAN;
} else {
if (first.distanceFromToday < second.distanceFromToday) {
return GREATER_THAN;
} else if (first.distanceFromToday > second.distanceFromToday) {
return LESS_THAN;
}
}
return EQUAL;
}
}
我的问题是运行时间似乎是二次或指数的（我没有进行准确的渐近分析）：
n (days) | running time in ms
1 * 365 | 48
2 * 365 | 123
3 * 365 | 278
4 * 365 | 482
5 * 365 | 733
6 * 365 | 1069
7 * 365 | 1438
8 * 365 | 1890
9 * 365 | 2383
10 * 365 | 2926
11 * 365 | 3646
12 * 365 | 4208
13 * 365 | 5009
你有什么建议我该如何优化这个算法？
注意：这不是家庭作业。
编辑：正如其他人在他们的回答中所说，这里的时间复杂度大约是 O(( n- m)^2)。我正在寻找亚二次型的东西，它在n收敛到无穷大的同时可以很好地扩展。