Início / coding / Perguntas / 77788966
Accepted
IRP_HANDLER
Asked: 2024-01-10 02:24:00 +0800 CST

Complexidade de std::inplace_merge

  • 772

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?

c++

1 respostas

  1. Best Answer

    Seus cálculos estão quase corretos, mas:

    1. Você está misturando seus parâmetros; o que nvocê usa muda o significado entre o número de elementos em um vetor e o número de elementos no vetor combinado.
    2. Tradicionalmente, a notação O grande ignora fatores constantes e quaisquer termos que sejam ofuscados por uma expressão O maior. Então 2mé a mesma coisa que m, e se nfor um superconjunto de m, n log nsignifica que você ignora 2mtotalmente o termo.
    3. Da mesma forma, você combina termos que são efetivamente a mesma coisa (portanto, ter mfor nums1e nfor nums2não faz sentido; o n log ntrabalho está no tamanho combinado ; você normalmente ignoraria a distinção entre as duas entradas).
    4. A complexidade do seu espaço (se você não está descartando fatores constantes) é indiscutivelmente 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 em nums1, e duas de cada elemento em nums2). 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)( nsendo o tamanho combinado de ambas as entradas) e a complexidade do espaço como O(n)(precisa de até 2nespaço, se nums1estiver vazio e nums2contiver 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_mergetentará 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 para O(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.

    • 3

relate perguntas