Таким образом, проблема, которую я решаю, заключается в нахождении элемента большинства в наборе целых чисел, размеру набора 0 < n < 10^5, и каждый элемент 0 < a < 10^9. Поэтому мне просто нужно выяснить, какой элемент проявляется строго больше, чем n/2 раза.Две функции не требуют времени, которого я ожидал бы из-за их большой сложности O, может кто-нибудь объяснить, почему?
У меня есть два решения, которые, как я считаю, оба правильные, но они не действуют, как я ожидал бы с моим пониманием их сложности. Может ли кто-нибудь объяснить мне, что я сделал неправильно/неправильно понял?
int getMajElement(vector<int> a)
{
std::unordered_map<int, int> countMap;
std::unordered_map<int, int>::iterator it;
for (int i : a)
{
it = countMap.find(i);
if (it == countMap.end())
{
countMap.insert(std::pair<int, int>(i, 1));
}
else
{
it->second++;
}
}
int mostOfNum = 0;
int mostOfNumCount = 0;
for (std::pair<int, int> pair : countMap)
{
if (pair.second > mostOfNumCount)
{
mostOfNumCount = pair.second;
mostOfNum = pair.first;
}
}
if (mostOfNumCount > floor(a.size()/2))
{
return mostOfNum;
}
else
{
return -1;
}
}
Из моего понимания, первый "для (INT I: а)" должна работать в O (N) времени, в то время как нахождение/приращением значения должны работать в O (1) время для HashMap. Второй цикл for (std :: pair pair: countMap) должен также выполняться в O (n) времени, так как я просто повторяю не более n пар. Это будет общее время O (n).
Эта функция занимает 2,4 секунды для работы при n = 10^5 и каждый a = rand()% 10^9. Я убедился в том, что вы просто выполняете функции, а не устанавливаете начальные значения.
Затем следующий занимает 0,70 секунды при тех же условиях, но я ожидал, что первый будет быстрее.
Вторая функция использует рекурсивный метод деления и покорения для решения проблемы и должна принимать время O (n log (n)). Он в основном разбивает список на n отдельных частей, а затем проверяет, является ли элемент большинства в левой половине таким же, как элемент большинства в правой половине. Если нет, он сканирует список, чтобы узнать, какое значение является общим большинством (значение> пол ((справа налево)/2)) для этого раздела и передать его обратно, else -1.
Может кто-нибудь объяснить мне, что вызывает разницу во времени, это просто ошибка внедрения, которую я сделал?
int get_majority_element(vector<int> &a, int left, int right) {
if (left == right) return -1;
if (left + 1 == right) return a[left];
int mid = left + floor((right - left)/2);
int leftMajority = get_majority_element(a, left, mid);
int rightMajority = get_majority_element(a, mid, right);
if(leftMajority == rightMajority)
{
return leftMajority;
}
else if (rightMajority == -1)
{
return leftMajority;
}
else if (leftMajority == -1)
{
return rightMajority;
}
else
{
int leftCount = 0, rightCount = 0;
for (int i = left; i < right; i++)
{
if (a[i] == leftMajority)
{
leftCount++;
}
else if (a[i] == rightMajority)
{
rightCount++;
}
}
if (leftCount > floor((right - left)/2))
{
return leftMajority;
}
else if (rightCount > floor((right - left)/2))
{
return rightMajority;
}
else
{
return -1;
}
}
return -1;
}
Правильно, я понимаю, что вы говорите, в этой ситуации, но по мере того, как n становится все больше и больше, эффект сложности становится более выраженным. – Sw1sh
@ Sw1sh. , , Бесконечность действительно, очень большая. На пределе вы * можете * сравнивать разные алгоритмы. Но вы действительно не знаете, находитесь ли вы в точке, где сравнение действительно, если вы не проанализируете накладные расходы и константы в уравнении, описывающее масштабирование производительности. –