我的带有 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))。

Answer 2

哈希 table 用于检查整数之间的冲突。

returns两个数组中不同整数的数量

  private static int distinctNumberOfItems(int[] arrayA, int[] arrayB) {

    HashSet<Integer> setA = new HashSet<Integer>();
    HashSet<Integer> setB = new HashSet<Integer>();

    for (int i : arrayA) {
      setA.add(i);
      setB.add(i);
    }

    for (int i : arrayB) {
      setB.add(i);
      if (setA.contains(i))
        setB.remove(i);
    }
    System.out.println(setB);
    return setB.size();
  }
}

Answer 3

您需要乘坐 symmetric difference between the sets to get the unique elements in each. In Java, this is done with Set#removeAll。

private static int distinctNumberOfItems(int[] arrayA, int[] arrayB) {

    HashSet<Integer> setA = new HashSet<Integer>();
    HashSet<Integer> setB = new HashSet<Integer>();
    HashSet<Integer> setC = new HashSet<Integer>();

    for (int i : arrayA) {
        setA.add(i);
        setC.add(i);
    }
    for (int i : arrayB) {
        setB.add(i);
    }

    setA.removeAll(setB);
    setB.removeAll(setC);
    return setA.size() + setB.size();
}

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

Big O for my binary search algorithm with for loop?

java

big-o

binary-search

time-complexity