计算复杂度时：a[0] + a[1] 会导致两次数组访问，还是只有一次？

Question

假设 a 是一个整数数组。 1) 给定代码：

for(int i = 0; i < N; i++){
   if(a[0] + a[1] == 0){
      ...
   }
}

时间复杂度是 ~2n 还是 ~1n 注意：我使用波浪符号，而不是 big-Oh 符号。常数很重要。

2)这段代码怎么样：

for(int i = 0; i < N; i++){
   if(a[0] == 0 && a[1] == 0){
      ...
   }
}

时间复杂度是 ~2n 还是 ~1n

非常感谢！

Answer 1

在第一个例子中，有两个数组访问。访问 a[0] 并没有告诉我们任何有关 a[1] 的信息。我们需要进行两次访问才能执行 + 操作。正如字节码*向我们展示的那样：

      10: aload_0
      11: iconst_0
      12: iaload
      13: aload_0
      14: iconst_1
      15: iaload
      16: iadd

aload_0 将变量 0 中的对象压入堆栈（a，在我的例子中），当然 iconst_0 将 0 压入堆栈，并且我们看到一个 iaload 从数组中得到一个 int。然后我们看到索引 1 重复了整个过程，然后是加法。

在第二个例子中，如果 a[0] 是 0，&& 短路并且 a[1] 永远不会加载或测试，因此所需的时间会有所不同取决于需要 a[1] 的频率。

* 我是如何得到那个字节码的：我创建了一个 E.java 文件：

class E {

    public static void main(String[] args) {
        foo(new int[] { 1, 2, 3, 4, 5, 6 });
    }

    static void foo(int[] a) {
        int N = a.length;
        for(int i = 0; i < N; i++){
           if(a[0] + a[1] == 0){
              System.out.println("Foo");
           }
        }
    }
}

然后编译，用javap -c E看字节码

计算复杂度时：a[0] + a[1] 会导致两次数组访问，还是只有一次？

When calculating complexity: does a[0] + a[1] result in two array accesses, or only one?

java

complexity-theory

time-complexity