我的 Java 解决方案是 O(n) 还是我遗漏了什么？

Question

我对某个问题的解决方案显然比 95% 的解决方案慢，我想确保我的时间复杂度是正确的。

在我看来这段代码是 O(n)。我使用了几个最多 O(n) 的循环并且它们没有嵌套所以我不相信解决方案是 n^2.

我使用 HashMap 作为存储，并在我的 while 和 for 循环中分别使用 O(1) 的 HashMap 方法进行插入和查找。

这个解的复杂度是 O(n) 还是我遗漏了什么？

 public int pairSum(ListNode head) {
    
    HashMap<Integer, Integer> nodeVals = new HashMap<Integer, Integer>();
    
    int count = 0;
    
    ListNode current = head;
    nodeVals.put(count, current.val);
    count++; 
    
    while (current.next != null) {
        current = current.next;
        nodeVals.put(count, current.val);
        count++;
    }
    
    int maxTwinSum = 0;
    for (int i = 0; i < nodeVals.size() / 2; i++) {
        int currTwinSum;
        currTwinSum = nodeVals.get(i) + nodeVals.get(nodeVals.size() - 1 - i);
        if (currTwinSum > maxTwinSum) maxTwinSum = currTwinSum;
    }
    
    return maxTwinSum;
}

Answer 1

首先：HashMap 方法是 摊销的 O(1)，这基本上意味着您可以 将它们视为 O( 1) 如果您经常使用它们，因为这就是它们的平均。但是构建 hashmap 仍然是一个“相对昂贵”的操作（这个概念不能用 bit-O 表示法来表达，因为它只关心渐近最坏的情况）。

其次：您在 HashMap 中构建列表的完整、低效副本，这可能比大多数其他方法慢。

第一个优化是用一个简单的 ArrayList 替换你的 HashMap：无论如何你只使用数字和严格单调递增的键，所以列表是完美的匹配。

Answer 2

Is my Java solution O(N) or am I missing something?

两者都是！

您的解决方案是O(N)，并且您遗漏了一些东西。

您缺少的是复杂性和性能不是一回事。复杂性是关于某些措施（例如所用时间、使用的space等）如何根据某些问题大小变量进行更改；例如列表的大小 N.

换句话说...并非所有 O(N) 问题的解决方案都具有相同的性能。有些更快，有些更慢。

在你的例子中，HashMap 是一个相对昂贵的数据结构。虽然它（摊销）O(1) 用于 get 和 put 等操作，但 比例常数 与（例如）使用 ArrayList 或保存相同信息的数组。

所以...我希望比您的解决方案更快的解决方案不会使用 HashMap。

不利的一面是，如果您只考虑 N 的值小于一些门槛。这是从 Big O 的数学定义得出的。

例如，如果您对整数数组进行排序并且数组大小足够小，简单的冒泡排序会比快速排序更快。

简而言之：复杂性不是性能。

我的 Java 解决方案是 O(n) 还是我遗漏了什么？

Is my Java solution O(n) or am I missing something?

java

hashmap

time-complexity