c++ - 两种包含重复算法的时间复杂度差异

Question

我完成了一个leetcode algorithm的两个版本并且想知道我的复杂性分析是否正确，即使以 ms 为单位的在线提交时间没有准确显示。目标是将数字 vector 作为引用，如果它包含重复值则返回 true，否则返回 false。

两种最直观的方法是:

1.) 对 vector 进行排序并扫描到倒数第二个，然后查看是否有任何相邻元素相同，如果相同则返回 true。

2.) 使用哈希表并插入值，如果表中已存在键，则返回 true。

我先完成了第一个版本，它很快，但是看到排序例程如何采用 O(nlog(n)) 和哈希表插入 & map.count ()s would制作第二个版本 O(log(n) + N) = O(N) 我认为散列版本对于非常大的数据集会更快。

在在线评审中我被证明是错误的，但是我认为他们没有使用足够大的数据集来抵消 std::map 开销。所以我运行了很多测试，重复填充大小在 0 到 10000 之间的 vector ，递增 2，添加 0 到 20000 之间的随机值。我将输出传输到一个 csv 文件并在 linux 上绘制它，这是我得到的图像.

是the provided image真正向我展示了 O(N) 和 O(nlog(n)) 算法之间的区别？我只是想确保我的复杂性分析在这些方面是正确的？

运行的算法如下:

bool containsDuplicate(vector<int>& nums) {
  if(nums.size() < 2) return false;
  sort(nums.begin(), nums.end());
  
  for(int i = 0; i < nums.size()-1; ++i) {
    if(nums[i] == nums[i+1]) return true;
  }
  return false;
}
// Slightly slower in small cases because of data structure overhead I presume
bool containsDuplicateWithHashing(vector<int>& nums) {
  map<int, int> map;
  for (int i = 0; i < nums.size(); ++i) {
    if(map.count(nums[i])) return true;
    map.insert({nums[i], i});
  }
  return false;
}

Answer 1

std::map is sorted, and involves O(log n) cost for each insertion and lookup ，因此在“无重复”情况下(或在“vector 末尾附近的第一个重复”情况下)的总成本将具有类似于排序和扫描的大 O:O(n log n);它通常在内存中是零散的，因此开销很容易高于优化的 std::sort。

不过，如果重复很常见，它看起来会快得多；如果您通常在前 10 个元素中找到重复项，那么输入是否有 10,000 个元素并不重要，因为 map 在您找到重复项并躲开之前没有时间增长。只是只有在成功时才能正常工作的测试对于一般用途来说并不是一个很好的测试(如果重复如此常见，测试似乎有点愚蠢)；您希望在包含重复和不包含重复的情况下都有良好的表现。

如果您希望比较算法复杂度明显不同的方法，请尝试使用 std::unordered_set替换基于 map 的解决方案(insert 返回键是否也已存在，因此您可以将工作从一次查找然后一次插入减少到每个循环中只有一次组合插入和查找)，它具有平均情况 O(1) 插入和查找，O(n) 重复检查复杂度。

仅供引用，另一种方法是 O(n log n) 但使用类似于排序的策略，在早期发现重复时使用快捷方式，将使用 std::make_heap 堆(O(n) 工作)，然后重复 pop_heap (O(log n) per pop) 从堆中取出并与堆的 .front() 进行比较；如果你刚刚弹出的值和前面相同，你就有了一个拷贝，可以立即退出。您也可以使用 priority_queue适配器将其简化为单个容器，而不是手动使用 std::vector 等工具函数。