这段伪代码的时间复杂度是多少?

Question

for loop {
initialize new hashmap 
for loop {
if (hashmap.containsKey(i)
map.put(something)
}
}

基本上是两个嵌套的for循环，其中包含一个containsKey函数。

我认为它是O(n^2)，因为嵌套循环，但它也可能是O(n^3)，因为containsKey函数。有人能帮我一下吗?

Answer 1

这实际上取决于您的代码中使用的是哪种映射实现。假设HashMap的实现是O(1)，但对于TreeMap实现它O(log(N))。有关详细信息，您可以查看以下内容:

Java集合框架实现的Big-O总结?

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html containsKey-java.lang.Object——

如果你使用HashMap，那么时间复杂度是O(N^2)，如果你使用TreeMap，它将是O(N^2)(log(N))在你的情况下。