Merge/MergeSort [contagem]

[Gman9]

Boas pessoal alguém consegue me ajudar a perceber o seguinte...

Considerando a implementação recursiva do algoritmo de ordenação merge sort.

Para um array de dimensão 2^n, qual o número de vezes que a função merge é chamada?

static void mergesort(int [] a, int l, int r){
  if (l < r) {
    int m = (l+r)>>>1;
    mergeSort(a, l, m);
    mergeSort(a, m+1, r);
    merge(a, l, m, r);
  }
}

[HappyHippyHippo]

a ideia do algoritmo merge sort recai em dividir a lista em elementos mais pequenos (a metade) e fazer o "merge" (junção ordenada) dessas listas (já ordenadas pela recursividade)

se o algoritmo recai em dividir em metade, então em cada chamada, se tens uma lista de 2^n elementos, ficas com duas listas de 2^(n-1) elementos, às quais terás de chamar a função recursivamente.

O que pretendes saber é na realidade o que se chamada de complexidade no tempo do algoritmo, que é de n*log(n), onde n é o número de elementos

Sendo assim, o número de vezes que a função é chamada para uma lista de 2^n é de (2^n)*log(2^n)

[Rui Carlos]

1 hora atrás, HappyHippyHippo disse:

O que pretendes saber é na realidade o que se chamada de complexidade no tempo do algoritmo, que é de n*log(n), onde n é o número de elementos

O número de chamadas ao merge (que é o que é perguntado) não é a complexidade da função/algoritmo, visto que conta a chamada ao merge como 1, e não como a complexidade dessa função.

---

O algoritmo começa por dividir as listas recursivamente em duas partes "iguais" até ter sub-listas de um elemento, e depois usa o merge para as voltar a juntar.  Ou seja, para uma lista de N elementos usam-se N/2 chamadas à função merge para juntar N/2 pares de sub-listas de um elemento, obtendo-se N/2 sub-listas de dois elementos.  Se agora temos N/2 sub-listas, temos (N/2)/2 pares de sub-listas, pelo usamos (N/2)/2 chamadas à função merge para voltar a juntar as sub-listas.  Depois teríamos ((N/2)/2)/2 chamadas, etc. Isto repete-se até teres duas sub-listas de N/2 elementos, que precisam de uma última chamada para serem juntas.

Assim, estaremos então a usar N/2 + (N/2)/2 + ((N/2)/2)/2 + ... + 2 + 1 chamadas à função merge.  Sendo N = 2^n, ficamos com: 1 + 2 + ... + ((2^n)/2)/2 +  (2^n)/2 = 1 + 2 + ... + 2^(n-2) + 2^(n-1) = 2^(n - 1) * 2 - 1 = 2^n - 1.

[HappyHippyHippo]

40 minutes ago, Rui Carlos said:

O número de chamadas ao merge (que é o que é perguntado) não é a complexidade da função/algoritmo, visto que conta a chamada ao merge como 1, e não como a complexidade dessa função.

está decidido, vou deixar de responder quando estou a dormir em pé ... a partir de agora, só de respondo de manhã 😄