java - 重复取消引用会增加时间复杂度吗？

Question

假设我有一个如下的 if 语句

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement) && map.get(complement) != i) {
        return new int[] { i, map.get(complement) };
    }
}

如果 if 语句的计算结果为 true，则 map.get(complement) 会被程序运行两次，从而更有利的是在此 if 语句之前使用变量来分配此结果取消引用，或者编译器/堆(或其他东西)是否会将这个值保留在内存中，以便这样的多个语句只被评估一次？如果它被评估两次，是否会增加像这里的 HashMap 这样的东西的时间复杂度，或者查找只需要 O(1) 时间，所以它并不重要？

Answer 1

对 HashMap 的查找需要 O(1)。
对于时间复杂度常数因子无关紧要，因此如果您执行 O(1) 调用两次，它仍然只是 O(1) > 因为O(2) = O(1)。所以类似

map.get(complement)
map.get(complement)
map.get(complement)
map.get(complement)

仍然是O(1)，因为您只执行它恒定的次数，与输入变量无关。

Java 本身不会优化 map.get(complement) 调用， map 可能在两次调用之间发生了变化。至少我不知道有哪个编译器可以做到这一点，但也许有些编译器可以深入分析您的代码。

<小时/>

对于n = nums.length，循环本身的时间复杂度为O(n)，因为您至少遇到了最坏的情况(其中映射不包含 key )完全迭代它，产生 O(n) for n = nums.length。可能也是在典型情况下，因为您的补集可以在任何地方，可能没有任何模式可以使它只产生恒定的迭代。

上面的循环运行时间也为 O(n)，因为它执行 O(1) 语句 n 次。