Проблемы сложности времени с мультикартой

Я создал программу, которая находит медиану списка чисел. Список чисел является динамическим в том смысле, что числа можно удалять и вставлять (можно вводить повторяющиеся числа), и в течение этого времени новая медиана переоценивается и распечатывается.

Я создал эту программу, используя мультикарту, потому что

1) польза от того, что он уже отсортирован,
2) легкая вставка, удаление, поиск (так как мультикарта реализует бинарный поиск)
3) разрешены повторяющиеся записи.

Ограничения на количество записей + удалений (представленных как N): 0 < N <= 100 000

Программа, которую я написал, работает и печатает правильную медиану, но она не достаточно быстра. Я знаю, что unsorted_multimap быстрее, чем multimap, но тогда проблема с unsorted_multimap заключается в том, что мне придется его отсортировать. Я должен отсортировать это, потому что, чтобы найти медиану, вам нужно иметь отсортированный список. Поэтому мой вопрос: будет ли целесообразно использовать unsorted_multimap, а затем быстро отсортировать записи, или это просто смешно? Будет ли быстрее просто использовать вектор, быстро сортировать вектор и использовать бинарный поиск? Или, может быть, я забыл какое-то невероятное решение, о котором я даже не подумал.

Хотя я не новичок в C ++, я признаю, что мои навыки со сложностью времени несколько выше.


Чем больше я смотрю на свой вопрос, тем больше начинаю думать, что было бы лучше использовать вектор с быстрой сортировкой и двоичным поиском, поскольку структуры данных в основном уже реализуют векторы.

3

Решение

Если ваша цель состоит в том, чтобы отслеживать медиану на лету, когда элементы вставляются / удаляются, вы должны использовать min-heap и max-heap. Каждый из них будет содержать половину элементов … Пару дней назад был похожий вопрос: Как реализовать Median-кучу

Хотя, если вам нужно искать конкретные значения для удаления элементов, вам все равно нужна какая-то карта.

Вы сказали, что это медленно. Итерируете ли вы от начала карты до (N / 2) -го элемента каждый раз, когда вам нужна медиана? Вам не нужно. Вы можете отслеживать медиану, постоянно поддерживая итератор, указывающий на нее, и счетчик количества элементов меньше этого. Каждый раз, когда вы вставляете / удаляете, сравнивайте новый / старый элемент с медианой и обновляйте итератор и счетчик.

Другой способ увидеть это — два мультикарта, каждый из которых содержит половину элементов. Один содержит элементы меньше, чем медиана (или равно), а другой содержит те, которые больше. Кучи делают это более эффективно, но они не поддерживают поиск.

Если вам нужна медиана только несколько раз, вы можете использовать алгоритм «выбора». Это описано в книге Седжвика. Это занимает в среднем O (N) времени. Это похоже на быструю сортировку, но не сортирует полностью. Он просто разбивает массив на случайные точки, пока, в конце концов, он не «выберет» на одной стороне меньшие m элементов (m = (n + 1) / 2). Затем вы ищете самый большой из этих m элементов, и это медиана.

3

Другие решения

чем больше я смотрю на свой вопрос, тем больше начинаю думать, что было бы лучше использовать вектор с быстрой сортировкой и двоичным поиском, поскольку структуры данных в основном уже реализуют векторы.

Если у вас мало обновлений — используйте несортированный std :: vector + станд :: nth_element алгоритм, который является O (N). Вам не нужна полная сортировка, которая является O (N * ln (N)).

живое демо nth_element:

#include <algorithm>
#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>

using namespace std;

template<typename RandomAccessIterator>
RandomAccessIterator median(RandomAccessIterator first,RandomAccessIterator last)
{
RandomAccessIterator m = first + distance(first,last)/2; // handle even middle if needed
nth_element(first,m,last);
return m;
}

int main()
{
vector<int> values = {5,1,2,4,3};
cout << *median(begin(values),end(values)) << endl;
}

Выход:

3

Если у вас много обновлений и только удаление из середины — используйте две кучи comocomocomocomo предлагает. Если бы вы использовали fibonacci_heap — тогда вы также получите удаление O (N) из произвольной позиции (если у вас нет дескриптора).

Если у вас много обновлений и вам нужно удалить O (ln (N)) из произвольных мест — используйте два мультимножества в качестве МПК предлагает.

5

Вот как вы могли бы реализовать это в O(log N) за обновление:

template <typename T>
class median_set {
public:
std::multiset<T> below, above;

// O(log N)
void rebalance()
{
int diff = above.size() - below.size();
if (diff > 0) {
below.insert(*above.begin());
above.erase(above.begin());
} else if (diff < -1) {
above.insert(*below.rbegin());
below.erase(below.find(*below.rbegin()));
}
}

public:
// O(1)
bool empty() const { return below.empty() && above.empty(); }

// O(1)
T const& median() const
{
assert(!empty());
return *below.rbegin();
}

// O(log N)
void insert(T const& value)
{
if (!empty() && value > median())
above.insert(value);
else
below.insert(value);
rebalance();
}

// O(log N)
void erase(T const& value)
{
if (value > median())
above.erase(above.find(value));
else
below.erase(below.find(value));
rebalance();
}
};

(Работа в действии с тестами)

Идея заключается в следующем:

  • Следите за значениями выше и ниже медианы в двух наборах
  • Если добавлено новое значение, добавьте его в соответствующий набор. Всегда проверяйте, чтобы в приведенном ниже наборе было ровно на 0 или 1 больше, чем в другом
  • Если значение удалено, удалите его из набора и убедитесь, что условие все еще выполняется.

Вы не можете использовать priority_queueпотому что они не позволят вам удалить один элемент.

2

Can any one help me what is Space and Time complexity of my following C# program with details.
//Passing Integer array to Find Extreme from that Integer Array
public int extreme(int[] A)
{
int N = A.Length;
if (N == 0)
{
return -1;
}
else
{
int average = CalculateAverage(A);
return FindExtremes(A, average);
}
}
// Calaculate Average of integerArray
private int CalculateAverage(int[] integerArray)
{
int sum = 0;
foreach (int value in integerArray)
{
sum += value;
}
return Convert.ToInt32(sum / integerArray.Length);
}
//Find Extreme from that Integer Array
private int FindExtremes(int[] integerArray, int average) {
int Index = -1; int ExtremeElement = integerArray[0];
for (int i = 0; i < integerArray.Length; i++)
{
int absolute = Math.Abs(integerArray[i] - average);
if (absolute > ExtremeElement)
{
ExtremeElement = integerArray[i];
Index = i;
}
}
return Index;
}
2

Вы почти наверняка лучше использовать вектор. Возможно поддержание вспомогательного вектора индексов, которые будут удалены между медианными вычислениями, чтобы вы могли удалять их партиями. Новые дополнения также можно поместить во вспомогательный вектор, отсортировать, а затем объединить.

1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector