使用 while 循环而不是 for 循环来创建二维数组以提高运行时效率

Question

我在 Jana（Java-Based Abstract Notation for Algorithms）中创建了以下代码，它创建了一个长度为 n 的二维数组：

fillMatrix(↕int matrix[1:n,1:n], ↓int n, ↓int a){

for(i=1…n){
    for(j=1…n){
    if(abs(↓(i-j))<=a){
        matrix[i,j]=1
    }else{
        matrix[i,j]=0
    }
    }
}
}

int abs(↓int i){
    if(i<0)
        return –i
    else
        return i
}

此代码的渐近运行时间为 O(n^2)。

我的问题是，假设矩阵的每个元素在调用时都被初始化为 0，我怎样才能使这段代码更有效率？

在此先感谢您的帮助！

Answer 1

假设您只需初始化获得 1 个值的单元格（其余单元格默认为 0）：

如果a比n小很多，您可以在O(n + a*n)时间内初始化获得1个值的单元格。

比如a == 0，只需要设置矩阵主对角线的n个单元格((0,0),(1,0),...,(n- 1,n-1)) 到 1.

如果a == 1，需要设置主对角线的n个单元格+与主对角线相邻的对角线的2*(n-1)个单元格。

...

如果a = c，需要将O(n) + O(2c*n)个单元格设置为1，即O(n + c*n)。

要实施此算法，您需要将 O(n^2) 循环替换为 2*a+1 O(n) 循环（每个相关对角线一个循环）。

Answer 2

我认为您使用了错误的工具来解决您的问题。并非每个问题都是钉子，因此并非每个解决方案都涉及锤子。如果您创建一个 Matrix 接口，并针对该接口进行编程，您可以解决 O(1) 中的实例化并使用更少的内存：

interface Matrix {
    int get(int i, int j);
}

class OrdinaryMatrix implements Matrix {
    int[][] data;

    public OrdinaryMatrix (int rows, int columns) { ... }

    public int get(int i, int j) {
        return data[i][j];
    }
}

class SpecialMatrix implements Matrix {
    private final int a;
    public SpecialMatrix (int rows, int columns, int a) {
        ...
        this.a = a;
    }

    public int get(int i, int j) {
        return Math.abs(i-j)<=a ? 1 : 0
    }
}

使用 while 循环而不是 for 循环来创建二维数组以提高运行时效率

Using while-loops instead of for-loops to create a 2D array for runtime efficiency

java

arrays

big-o

pseudocode

multidimensional-array