我对某个问题的解决方案显然比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;
}
我的Java解决方案是
O(N)还是缺少什么？
两者都是！
您的解决方案是O(N)，并且您缺少了一些东西。
你缺少的是复杂性和性能不是一回事。复杂性是指某些度量(如所用时间、所用空间等(如何根据某些问题大小变量而发生变化；例如列表CCD_ 3的大小。
换句话说。。。并非问题的所有CCD_ 4解决方案都具有相同的性能。有些更快，有些更慢。
在您的情况下，HashMap是一种相对昂贵的数据结构。虽然它(摊销(O(1)用于get和put等操作，但与使用ArrayList或数组来保存相同信息相比，比例常数较大。
所以。。。我预计比您更快的解决方案不会使用HashMap。
另一方面，如果只考虑N的值小于某个阈值，则O(N^2)解决方案可能比O(N)解决方案更快。这源于大O 的数学定义
例如，如果您正在对整数的数组进行排序，并且数组大小足够小，则天真的bubblesort将比快速排序更快。
简而言之：复杂性不是性能。
首先：HashMap方法被摊销O(1(，这基本上意味着，如果你经常使用它们，你可以将它们视为O(1。但构建一个哈希图仍然是一个"问题"；相对昂贵的"；运算(这个概念不能用bit-O表示法来表达，因为它只关心渐近最坏的情况(。
第二：在HashMap中构建一个完整的、低效的列表副本，这可能比大多数其他方法慢。
第一个优化是用一个简单的ArrayList替换HashMap：无论如何，你只使用数字和严格单调递增的键，所以列表是完美的匹配。