Eu tenho alguma confusão relacionada à complexidade de espaço da mesclagem de mesclagem. Diz que é O (n). No entanto, se eu olhar para a implementação no wiki, parece O (nlogn).
Isso ocorre porque em cada chamada recursiva, eu dividoo array para a esquerda e para a direita. Por exemplo, vamos começar na primeira chamada para ordenação por mesclagem. Ele dividirá a matriz em duas metades esquerda e direita para as quais já precisamos de n espaço. Como você pode ver na implementação do wiki, ele cria dois novos arrays para conter as partes esquerda e direita.
Agora duas chamadas recursivas são feitas para a direitae partem as metades correspondentemente, as quais dividirão a sua parte em esquerda e direita, o que novamente tomará espaço n combinando as quatro novas metades e assim por diante.
Como todas essas chamadas são chamadas recursivas,a memória é consumida na pilha repetidamente e se acumula em O (nlogn). Então, acho que a complexidade do espaço para essa implementação específica é O (nlogn).
Por favor, forneça algumas ideias?
Respostas:
-1 para resposta № 1Você está perto. Se você está incluindo o espaço das chamadas recursivas, é O (n) + O (logn), que = O (n). Espero que isso resolva sua pergunta.
Vejo esta postagem para mais.