给定排序代码的时间复杂度是多少？

Question

我想过用hash map排序，插入操作的时间复杂度是O(log(n))所以，我想知道是否可以用O(log(n)+n)排序？

//sahil L. Totala 
#include <bits/stdc++.h>
#include <iostream>

using namespace std;
int main ()
{
  
  cout << "how much no. do you want:";
  int n;

  map < int, int > mp;

  cin >> n;

  for (int i = 0; i < n; i++)
    {
      int k = 0;
      cin >> k;
      mp.insert ({k, 1});
    }

  for (auto itr = mp.begin (); itr != mp.end (); ++itr)
    {
      cout << itr->first << endl;
    }

  return 0;
}

Answer 1

就目前而言，代码类似于 O(N log M)，其中 N 是输入元素的总数，M 是唯一元素的数量。

您正在尝试将 N 个元素插入到您的地图中，但该尝试只会对之前不存在的元素成功。这意味着地图将只包含输入中每个唯一元素的一个节点，因此每次插入都是唯一元素数量的对数。

虽然这有一点问题：就目前而言，您的代码并没有真正正常工作。如果输入包含重复项，则只会写出唯一的数字。例如，如果您对 [1 1 1 1 2 2 1 2 1] 进行排序，预期输出通常为 [1 1 1 1 1 1 1 2 2 2]，但您的代码将仅生成 [1 2].

可以在大致保持当前复杂性的同时修复该问题。最明显的方法是将 mp.insert ({k, 1}); 更改为 ++mp[k].

然后您将输出循环更改为：

  for (auto itr = mp.begin (); itr != mp.end (); ++itr)
    {
      for (auto i = 0; i<itr->second; i++)
          cout << itr->first << '\n';
    }

递增意味着我们计算每个输入值出现的次数。然后我们将这些值中的每一个写出来，只要它出现就经常写出来。

至少在理论上，如果我们希望输入包含大量重复项，这可以为我们节省一点复杂度。

就目前而言，您并没有真正使用与每个键关联的值，因此您可以使用 std::set 而不是 std::map。

修复代码的另一种方法是改用 std::multiset，但这会将复杂度从 O(N log M) 更改为 O(N log N)。

顺便说一句，我建议避免 std::endl。只需写出一个 new-line，如修改后的输出循环所示。 using namespace std; 和 #include <bits/stdc++.h> 也是最好避免的。

给定排序代码的时间复杂度是多少？

What is time complexity of the given code for sorting?

c++

sorting

time-complexity