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

I have created the following code in Jana (Java-Based Abstract Notation for Algorithms) which creates a 2-dimensional array of length n:

我在Jana(基于Java的抽象符号算法)中创建了以下代码,它创建了一个长度为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
}

This code has an asymptotic runtime of O(n^2).

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

My question is, assuming that each element of the matrix is initialized to 0 at the call, how can I make this code more efficient?

我的问题是,假设在调用时矩阵的每个元素都被初始化为0,我该如何才能使这个代码更有效?

Thanks in advance for the help!

在此先感谢您的帮助!

2 个解决方案

#1

Assuming you only have to initialize the cells that get 1 value (the rest of the cells are 0 by default):

假设您只需初始化获得1值的单元格(其余单元格默认为0):

If a is much smaller than n, you can initialize the cells that get 1 value in O(n + a*n) time.

如果a远小于n,则可以初始化在O(n + a * n)时间内获得1值的单元格。

For example, if a == 0, all you need is to set the n cells of the main diagonal of the matrix ((0,0),(1,0),...,(n-1,n-1)) to 1.

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

If a == 1, you need to set the n cells of the main diagonal + the 2*(n-1) cells of the diagonal adjacent to the main diagonal.

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

...

If a = c, you need to set O(n) + O(2c*n) cells to 1, which is O(n + c*n).

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

To implement this algorithm, you'll need to replace your O(n^2) loop with 2*a+1 O(n) loops (one loop for each relevant diagonal).

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

#2

I think that you use the wrong tool for your problem. Not every problem is a nail, and so not every solution involves a hammer. If you create a Matrix interface, and program against that interface, you can solve the instantiation in O(1) and also use less memory:

我认为您使用错误的工具来解决您的问题。不是每个问题都是钉子,因此并非所有解决方案都涉及锤子。如果您创建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
    }
}

#1