java - 计算数组访问次数

Question

我试图弄清楚如何确定某些简单方法的复杂性(数组访问)。

如果我做得正确，我需要一些确认。例如这个方法。

    int i = 0;  
    while(i < N){
        clone[i][j] = clone[++i][j];
        clone[i][j] = 0;
    }

这里的数组访问总数是 3 吗？一个用于clone[i][j]，另一个用于clone[++i][j]，最后一个用于clone[i][j]。这意味着它有±3N数组访问？

像这样怎么样:

if(克隆[i][j] == 值1 || 克隆[i][j] == 值2)

我可以将其视为一次还是两次数组访问？

提前致谢!

Answer 1

我将这些算作六次数组访问。

您正在访问二维数组，以及类似的语句

clone[i][j] = 0;

可以类似地写成

int temp[] = clone[i];
temp[j] = 0;

您还可以查看字节码:A a class like

class ArrayAcc
{
    static void foo()
    {
        int array[][] = new int[2][2];
        array[1][1] = 123;
    }

}

编译和反汇编

javap -c ArrayAcc.class

给出以下输出:

....
static void foo();
Code:
   0: iconst_2
   1: iconst_2
   2: multianewarray #2,  2             // class "[[I"
   6: astore_0
   7: aload_0
   8: iconst_1
   9: aaload
  10: iconst_1
  11: bipush        123
  13: iastore
  14: return

aaload 指令加载对堆栈上“内部”数组的引用。 iastore 指令将值 123 放入此“内部”数组中。

<小时/>

对于问题的其他部分，

if(clone[i][j] == value1 || clone[i][j] == value2)

这里取决于第一个条件是否为true。如果第一个条件为true，则将不评估第二个条件。如果你写了

if(clone[i][j] == value1 | clone[i][j] == value2)

(使用单个|)那么您总是会检查两个条件。