问询C++函数containsDuplicates的时间复杂度为O(n)还是O(nlogn)

时间复杂度分析结论 #

• 你对平均时间复杂度的理解是正确的，网上说的O(nlogn)的说法是错误的，除非混淆了unordered_map和有序map的实现。

平均情况复杂度 #

unordered_map是哈希表实现，插入、访问操作的平均时间复杂度为O(1)：

1. 第一个遍历数组的循环共执行n次，每次操作O(1)，总复杂度为O(n)
2. 第二个遍历哈希表的循环，最多执行n次（数组所有元素都不重复的场景），总复杂度为O(n)
3. 大O表示法会忽略常数系数，因此整体平均时间复杂度为O(n)，你计算的O(n)+O(n)=2O(n)的推导逻辑没有问题，只是最终简化后写为O(n)即可。

O(nlogn)说法的来源 #

这个说法大概率是把unordered_map和C++ STL中的有序map搞混了：

• 有序map底层是红黑树实现，每次插入的时间复杂度为O(logk)（k为当前树中元素数量），如果把代码里的unordered_map换成map，第一个循环的总复杂度就是O(nlogn)，整体复杂度为O(nlogn)，这就是该说法的错误来源。

补充说明 #

另外你贴的代码存在逻辑漏洞：如果数组中没有重复元素，函数走完两个循环后没有执行return false，会触发未定义行为，需要在最后补return false;的逻辑。

内容的提问来源于stack exchange，提问作者James Franco