该算法在Big(O)中的时间复杂度

Question

我想出了以下算法来计算时间复杂度，以找到字符串中出现次数第二多的字符。该算法分为两部分。将字符插入O(n(中映射的第一部分。第二部分我有困难。在映射上迭代是O(n(push，pop是O(log(n((。第二部分的BigO复杂性是什么？最后，整体的复杂性是什么？理解这一点有什么帮助吗？

void findKthHighestChar(int k,std::string str)
{
std::unordered_map<char, int> map;

//Step 1: O(n)
for (int i = 0; i < str.size(); i++)
{
map[str[i]] = map[str[i]] + 1;
}
//Step2: O(n*log())
//Iterate through the map
using mypair = std::pair<int, char>;
std::priority_queue<mypair, std::vector<mypair>, std::greater<mypair>> pq;
for (auto it = map.begin(); it != map.end(); it++) //This is O(n) .
{
pq.push(mypair(it->second, it->first)); //push is O(log(n))
if (pq.size() > k) {
pq.pop();                           //pop() is O(log(n))
}
}
std::cout << k << " highest is " << pq.top().second;
}

Answer 1

您有两个输入变量，k和n(带k < n(
还有一个隐藏的：字母大小的A

• Step1的平均事例复杂度为O(n)。

• 步骤2:O(std::min(A, n)*log(k))。

  迭代地图是O(std::min(A, n))

  队列大小绑定到k，因此其操作在O(log(k((中

整个算法如此O(n) + O(std::min(A, n)*log(k))如果我们简化并去掉一些变量，只保留n:

• (k->n，A->n(：O(n) + O(n*log(n))所以O(n*log(n))
• (k->n，std::min(A, n)->A(: O(n) + O(log(n))所以O(n)

Answer 2

一定是这个算法吗？

你可以使用一个(字母表大小的(数组来保存频率。

您可以在O(n(中填充它(一次遍历字符串(。然后你可以一次找到最大或第二大的频率。仍然是O(n(。