No
Merging Parcial existirá a presença de algum outro método de ordenação,
diferente do MergeSort, afim de reduzir ao máximo o tempo de processamento. O
custo deste método, no geral, será uma composição de pelo menos dois métodos.
O método de tratamento que escolhemos
para desenvolver o Merging Parcial foi o de ordenar os subarrays com um
Heapsort e então uni-los com um Merge.
O algoritmo do HeapSort rearranja os
elementos de um vetor v[1 . . n] de modo que eles fiquem em ordem crescente, ou seja, de
modo que tenhamos v[1] ≤ v[2] ≤ . . . ≤ v[n].
Com base nisso temos
que juntar os custos seguindo a seguinte observação, para encontrarmos o custo
real:
O consumo de tempo do HeapSort, é proporcional ao número de
comparações entre elementos do vetor e, portanto, proporcional a Nlog N, no pior caso. Assim,
estabelecemos que no custo final será somado o custo das N vezes que foi
executado o método de ordenação secundário, mais o custo do próprio merge, que
é de O (N Log N).
A
função Merge () é usada para mesclar duas metades. A mesclagem (arr, l, m, r) é
o processo-chave que pressupõe que arr [l.. m] e arr [m + 1.. r] são
classificados e mescla os dois subarrays classificados em um.
A
complexidade de tempo do Merge é O (N
Log N) em todos os 3 casos (pior, média e melhor), pois o Merge() do
Merging Parcial divide o array em subarrays e levar tempo linear para mesclar dois
dos subarrays.
Logo o custo final será
de O( 2N log N), no pior caso.
Ja que no pior caso, o custo seria O(2NlogN), que sera melhor que a maioria dos outros metodos (que custam O(n2)), quais sao os motivos para nao utilizar o Merge Parcial?
ResponderExcluirMerge Parcial é útil quando existe um volume de dados tão grande que não é possível armazena-los na memória principal disponível, quando for possível esse armazenamento é muito mais prático utilizar bons algoritmos, com tempo de processamento menor que os demais, como quick ou heapsort para ordenar tudo de uma vez.
ExcluirAlgoritmos de ordenação com o custo constante de O(N^2) só são viáveis para uma quantidade pequena de dados.