algorithm - 为什么以下两个重复查找器算法具有不同的时间复杂度？

Question

我正在读这个question .所选答案包含以下两种算法。我不明白为什么第一个的时间复杂度是 O(ln(n))。在最坏的情况下，如果数组不包含任何重复项，它将循环 n 次，第二个也是如此。我错了还是我错过了什么？谢谢

1) 更快(在极限范围内)的方式

这是一种基于哈希的方法。您必须为自动装箱付费，但它是 O(ln(n)) 而不是 O(n2)。一个有进取心的人会去寻找一个原始的基于 int 的哈希集(我认为 Apache 或 Google Collections 有这样的东西。)

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

2)向惠勒鞠躬

请参阅 HuyLe 的答案以获得或多或少的 O(n) 解决方案，我认为这需要几个附加步骤:

static boolean duplicates(final int[] zipcodelist) {    
    final int MAXZIP = 99999;    
    boolean[] bitmap = new boolean[MAXZIP+1];    
    java.util.Arrays.fill(bitmap, false);    

    for (int item : zipcodeList)
        if (!bitmap[item]) bitmap[item] = true;
        else return true;    
    }

    return false; 
}

Answer 1

第一个解决方案的预期复杂度应为 O(n)，因为必须遍历整个邮政编码列表，并且处理每个邮政编码的预期时间复杂度为 O(1)。

即使考虑到插入到 HashMap 中可能会触发重新哈希，复杂度仍然是 O(1) .这有点不合逻辑，因为 Java HashMap 和链接中的假设之间可能没有任何关系，但它表明这是可能的。

来自 HashSet文档:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

第二个解也一样，分析正确:O(n)。

(只是一个题外话，BitSet 比数组快，如原帖所示，因为 8 个 boolean 被打包到 1 个 byte 中，它使用更少的内存)。