LinkedHashMap 复杂度

Question

我有一个简单的问题要找到数组 A 中的第一个唯一元素。但是，困扰我的是使用不同方法的时间复杂度。到目前为止我已经尝试了这两种方法。

第一种方法：

LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();
for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();
return -1;

第二种方法：

    for(int i=0; i< A.length; i++){
        boolean unique = true;
        nestedFor:for(int j=0; j< A.length; j++){
            if(i != j && A[i] == A[j]){
                unique = false;
                break nestedFor;
            }
        }
        if(unique)
            return A[i];
    }
    return -1;

测试包含 1000000 个元素的数组，第一个方法执行时间约为 2000 毫秒，而第二个方法执行时间约为 10 毫秒。我的问题是：与复杂度为 O(n^2) 的第二种方法相比，第一种方法的复杂度是 O(nLogn)，难道不应该执行得更快吗？我在这里错过了什么？测试代码下方：

    int[] n = new int[1000000];
    for (int i = 0; i < n.length; i++)
        n[i] = new Random().nextInt(2000000);

    long start = System.currentTimeMillis();
    firstUnique(n);
    System.err.println("Finished at: " + (System.currentTimeMillis() - start ) + "ms");

编辑：

for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

消耗 99% 的执行时间，而

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();

总是1-3ms。所以，是的，填充地图是最昂贵的操作。

对于此类问题，您认为最有效的方法是什么？

Answer 1

我的观察：第二种方法要快得多，因为它使用 Array 并声明了宽度。在第一个示例中，发生了大小变化。

请尝试定义更准确的大小 LinkedHashMap 以将初始容量设置为 1000000。

接下来的事情是 Array 是一个更简单的结构，GC 不会尝试做任何事情。但是，当涉及到 LinkedHashMap 时，它的创建和操作成本在某些情况下比简单地从 Array.

获取特定索引处的元素要复杂得多。

Answer 2

时间复杂度忽略了系数，因为了解函数如何随着输入大小的增加而增长通常更有用。尽管您的第一个函数的时间复杂度较低，但在输入较小的情况下，它会运行慢得多，因为您正在制作许多 ArrayList 对象，这在计算上是昂贵的。然而，你的第二种方法只使用数组访问，这比实例化一个对象要便宜得多。

Answer 3

时间复杂度应该从渐近的意义上来理解（即随着输入大小增长到 googolplex），仅此而已。如果一个算法具有线性时间复杂度，那仅意味着存在一些 a,b，使得执行时间（大致 !!!）= a * inputsize + b。它没有说明 a 和 b 的实际大小，并且两个线性算法仍然可能具有巨大的性能差异，因为它们的大小 a/b 差异很大。

（此外，您的示例很糟糕，因为算法的时间复杂度应考虑所有基础操作（例如对象创建等）的复杂度。其他人也在他们的答案中暗示了这一点。）

Answer 4

我怀疑您没有选择为第二种情况创造 "worst case" 条件的输入。

例如，如果您构造的数组使得所有百万个元素都有重复项（例如 A[i] = 2 * i / A.length），那么第二种方法比第一种方法慢得多，因为它必须检查10^12 个元素组合。

您可以通过将内部 for 循环的条件更改为仅从 j = i + 1 开始检查来使其更快（大约快两倍），但 10^12 / 2 仍然是一个相当大的数字。

如果您只是简单地选择随机数来填充数组，那么第一个元素很可能是唯一的，并且第一个和第二个元素中的一个是唯一的可能性更大，等等。在几个元素之后，您几乎可以确定该元素是唯一的，因此它会在几次迭代后停止。

第一种方法花费的 2 秒太长了。我只能认为您在基准测试之前没有正确预热 JIT。但即使不尝试这样做，你的第一种方法对我来说也只需要 40-50 毫秒（经过几次迭代后下降到 10-15 毫秒）。

大部分时间将归因于对象创建 - 在键和值的自动装箱以及 ArrayList 实例的创建中。

Answer 5

考虑改用 2 组：

public int returnFirstUnqiue(int[] a)
{
  final LinkedHashSet<Integer> uniqueValues = new LinkedHashSet<Integer>(a.length);
  final HashSet<Integer> dupValues = new HashSet<Integer>(a.length);

  for (int i : a)
  {
    final Integer obj = i;
    if (!dupValues.contains(obj))
    {
      if (!uniqueValues.add(obj))
      {
        uniqueValues.remove(obj);
        dupValues.add(obj);
      }
    }
  }

  if (!uniqueValues.isEmpty())
  {
    return uniqueValues.iterator().next();
  }
  return -1;
}

Answer 6

首先，为什么基准测试不相关：

即使我们忽略由使用的方法、GC 等引起的不准确，发现方法 2 在一百万个条目上更快也不会告诉您它在十亿个条目上的表现如何
- Big-O是一个理论概念，必须从理论上证明。大多数基准可以在这里为您做的是让您估计复杂性，这不是通过在一个输入上比较两种方法来完成的，而是通过在多个输入上比较一种方法，每个输入都比前一个大一个数量级（甚至那么几乎不可能得出任何有用的结论）
Big-O 是最坏情况 的复杂性，但对于第一种方法（映射），您的随机输入可能在某个地方 "in the middle"，而它会远非数组的最坏情况——实际上它有 50% 的机会在第一次迭代中成功，而映射必须被完全处理并且平均有大约 50 万个条目
- "map" 方法的最坏情况可能是所有元素都不同但具有相同的哈希码（因此您需要在 n 次迭代的每一次中读取添加元素的整个列表）
- "array" 方法的最坏情况是所有元素都相等（需要完成整个嵌套迭代）

至于找到一个好的算法 - 你可以使用 Map<Integer, Boolean> 而不是 Map<Integer, List<Integer> 因为你只需要存储唯一标志而不是值列表 - 添加 True 第一次看到元素的时候，遇到口是心非的时候切换到False

LinkedHashMap 操作 put、containsKey/get 具有大 O 复杂度 O(n)（最坏情况）使得整个算法 O(n^2)
但是，put 的 分摊复杂度 是 O(1)（使得所有插入的 分摊复杂度 O( n)) 并且 get 的平均复杂度是恒定的（这取决于所使用的哈希函数对给定输入的工作情况）；唯一值查找则为 O(n)

LinkedHashMap 复杂度

LinkedHashMap complexity

java

big-o

time-complexity

nested-loops

linkedhashmap