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

Question

我在 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
}

该代码的渐近运行时间为 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) 循环(每个相关对角线一个循环)。