java - 我的带有 for 循环的二进制搜索算法的大 O？

Question

我正在努力使我的算法运行时间尽可能短。

这个算法的运行时间是多少？是 O(log n) 还是 O(n log n) 因为 for 循环？

import java.util.Arrays;

public class countDifferenceBetweenTwoArrays {
  private static int countDifference(int[] arrayA, int[] arrayB) {
    int differenceCount = 0;
    for (Integer i : arrayA) {
      if (Arrays.binarySearch(arrayB, i) < 0) {
        differenceCount++;
      }
    }
    for (Integer i : arrayA) {
      if (Arrays.binarySearch(arrayB, i) < 0) {
        differenceCount++;
      }
    }
    return differenceCount;
  }

Answer 1

您的实现是 O(nlog(n))。您遍历每个数组，这是一个复杂度为 O(n) 的操作。在每次迭代中，您执行 O(log(n)) 二进制搜索操作。这为您提供了 O(nlog(n)) 的运行时间来处理每个数组。你这样做了两次，但我们忽略了常数因子 2，使整个函数的复杂度为 O(nlog(n))。