Portanto, tenho dois vetores classificados e queria mesclá-los em um único vetor classificado sem usar um vetor adicional.
Como existe essa condição, não posso usar std::merge , então tentei std::inplace_merge .
Eu tenho esta função que leva ambos os vetores e dois números m e n que são o número de elementos em cada vetor. Veja como resolvi esse problema:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
auto it = std::remove_if(std::execution::par, nums1.begin() + m, nums1.end(),
[](const int val)
{
return val == 0;
}
);
nums1.erase(it, nums1.end());
nums1.insert(nums1.end(), nums2.begin(), nums2.end());
std::inplace_merge(std::execution::par, nums1.begin(), nums1.begin() + nums1.size() - nums2.size(), nums1.end());
}
Caso de exemplo
vec 1 = [1,2,3,0,0,0]
m = 3
vec2 = [2,5,6]
n = 3
Resultado esperado:[1, 2, 2, 3, 5, 6]
Minha tentativa de encontrar a complexidade do espaço e do tempo
tudo está funcionando bem, agora o que eu quero é descobrir a complexidade do tempo e do espaço. Eu descobri o seguinte:
A complexidade do espaço seria o tamanho do vetor total, certo? Neste caso acredito que seja O(m + n)
Quanto à complexidade do tempo, std::remove_if levaria no máximo m , então std::vector::erase e std::vector::insert levaria n (o número de elementos no segundo vetor) e finalmente std: :inplace_merge levaria O (n log n).
Então no final temos O(n log n + 2m + n) , estou correto?
Seus cálculos estão quase corretos, mas:
n
você usa muda o significado entre o número de elementos em um vetor e o número de elementos no vetor combinado.2m
é a mesma coisa quem
, e sen
for um superconjunto dem
,n log n
significa que você ignora2m
totalmente o termo.m
fornums1
en
fornums2
não faz sentido; on log n
trabalho está no tamanho combinado ; você normalmente ignoraria a distinção entre as duas entradas).O(m + 2n)
, já que você não está consumindo os elementos do segundo vetor, você os está copiando (então você acaba com uma cópia de cada elemento emnums1
, e duas de cada elemento emnums2
). Mas é claro, de acordo com o número 2/3, isso é mais detalhe do que você usaria para a notação O grande.Portanto, em termos de grande O, você expressaria a complexidade do tempo de forma simples
O(n log n)
(n
sendo o tamanho combinado de ambas as entradas) e a complexidade do espaço comoO(n)
(precisa de até2n
espaço, senums1
estiver vazio enums2
contiver todos os dados, mas fatores constantes não importa para o grande-O). À medida que o tamanho dos inputs aumenta, estes são os termos dominantes, todo o resto se torna irrelevante do ponto de vista teórico (mesmo que essas preocupações práticas possam realmente importar na vida real).Observe que, na prática,
std::inplace_merge
tentará alocar espaço temporário, se possível, e se tiver sucesso, a complexidade do tempo (em termos do número de comparações necessárias) cai paraO(n)
, portanto, o espaço do mundo real usado pode ser maior do que o esperado, enquanto o o tempo pode crescer mais lentamente do que o esperado.