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

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

Если у вас мало обновлений — используйте несортированный 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)) из произвольных мест — используйте два мультимножества в качестве МПК предлагает.

Вот как вы могли бы реализовать это в 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потому что они не позволят вам удалить один элемент.

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;
}

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