反复引用会增加时间复杂度吗？

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语句之前使用变量更有利于分配此取消引用的结果，或者编译器/堆（或其他东西）是否保留此值在内存中，这样多个语句只被评估一次？如果它被评估两次，这会增加像哈希映射这样的东西的时间复杂度，或者查找只需要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)调用，地图可能在两个调用之间发生了变化。至少我不知道一个编译器，但也许有一些深入分析你的代码。

---

循环本身在O(n)中为n = nums.length，因为你至少有最坏的情况（地图不包含键），你完全迭代它，为O(n)产生n = nums.length。也许在一个典型的情况下，因为你的complement可能在任何地方，可能没有模式会使它只能产生不断的迭代。

上面的循环也在O(n)中运行，因为它执行O(1)语句n-times。

Answer 2

由于编译器/ JIT无法知道对方法的两次调用是否会产生相同的结果，因此无法优化调用。鉴于任何程序可能是多线程的，甚至可能是这样，如果没有适当的同步，则在两次调用之间修改映射，并且get的结果返回不同的对象。

因为如果你要求一个不存在的密钥，get方法将返回null，代码可以重写为：

for (int i = 0; i < nums.length; i++) {
   int complement = target - nums[i];
   Integer value = map.get(complement);

   if (value != null && value != i) {
       return new int[] { i, value };
   }
}

Answer 3

不，时间复杂度不会改变：通过if语句的每个可能的执行路径所需的时间可以通过查找所需的时间上限，乘以因子3，加上所有其他恒定时间的一些开销 - 计算。 O(3 * constant_1 + constant_2)渐渐地仍然只是O(1)的正常数。

由于不保证引用透明性，编译器不会优化三个查找。

然而，理论上（可能在将来的版本中）哈希映射的具体实现可以维护具有预先计算的哈希码的缓存以及它们在内部存储的数组中的位置，用于最近已经传递给contains方法的密钥。

另一个要考虑的因素是硬件如何处理内存访问。通过足够聪明的内存管理器，当第二次访问时，哈希映射的内容可能是“温暖的”，因此第二次和第三次访问并不重要。

结论：不，渐近运行时不会改变。首先纠正它。然后对其进行分析然后根据需要对其进行优化。