Sobre a dúvida na aula de hoje:
afinal é qual dos dois é piso e qual é teto?
Mergesort(A,p,q) ...... T(teto(n/2))
Mergesort(A,q+1,r) .... T(piso(n/2))
Considerando que q = piso((p+r)/2), temos:
[] | []
[][] | []
[][] | [][]
[][][] | [][]
O lado esquerdo é teto e o direito é piso, pois o q entra na primeira chamada do Mergesort. Num vetor de tamanho ímpar (2k+1), teremos:
q = piso((1+2k+1)/2) = k+1
Então um lado ficará de 1 até k+1 tendo o tamanho (k+1-1+1 = k+1); o outro de k+2 até 2k+1 (cujo tamanho é 2k+1-(k+2)+1 = k).
Ah, no vetor de tamanho par (2k) a divisão fica correta (k para cada lado).
[] | []
[][] | []
[][] | [][]
[][][] | [][]
O lado esquerdo é teto e o direito é piso, pois o q entra na primeira chamada do Mergesort. Num vetor de tamanho ímpar (2k+1), teremos:
q = piso((1+2k+1)/2) = k+1
Então um lado ficará de 1 até k+1 tendo o tamanho (k+1-1+1 = k+1); o outro de k+2 até 2k+1 (cujo tamanho é 2k+1-(k+2)+1 = k).
Ah, no vetor de tamanho par (2k) a divisão fica correta (k para cada lado).
Apoiado.
Só não concordo com a frase "no vetor de tamanho
par a divisão fica correta". Não há divisão
correta nem incorreta. O que acontece é que os
dois lados ficam iguais.
Só não concordo com a frase "no vetor de tamanho
par a divisão fica correta". Não há divisão
correta nem incorreta. O que acontece é que os
dois lados ficam iguais.
Justo. Usei o termo 'correta' porque acho bonitinho divisões que dão certo. Foi um equívoco.