If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Curso: Computer science theory > Unidade 1

Lição 8: Merge sort
Computação
Computer science theory
Algoritmos
Merge sort
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies

Análise do merge sort

Google Sala de Aula
Dado que a função merge é executada em um tempo Θ(n) quando está intercalando n elementos, como podemos demonstrar que o mergeSort é executado em um tempo Θ(nlog2⁡n)? Começamos pensando sobre as três partes da divisão-e-conquista e como contar seus tempos de execução. Assumimos que estamos ordenando um total de n elementos em todo o array.
  1. O passo da divisão é executado em tempo constante, independente do tamanho do subarray. Afinal, o passo da divisão apenas calcula o ponto médio q dos índices p e r. Lembre que na notação Θ-grande, nós denotamos o tempo constante como Θ(1).
  2. O passo da conquista, em que nós ordenamos recursivamente dois subarrays de aproximadamente n/2 elementos cada, leva algum tempo, mas vamos contar esse tempo quando considerarmos os subproblemas.
  3. O passo da combinação intercala um total de n elementos, levando um tempo Θ(n).
Se pensarmos nos passos da divisão e combinação juntos, o tempo de execução Θ(1) do passo da divisão é de ordem menor quando comparado com o tempo de execução Θ(n) do passo da combinação. Então vamos considerar que os passos da divisão e combinação juntos levam um tempo Θ(n). Para deixar as coisas mais concretas, vamos dizer que os passos da divisão e da combinação levam tempo cn em que c é alguma constante.
Para manter tudo mais simples, vamos assumir que se n>1, então n é sempre par, assim quando precisarmos pensar sobre n/2, estaremos sempre pensando em um inteiro. (Contando o caso em que n é ímpar não muda o resultado em termos da notação Θ-grande.) Então agora podemos pensar no tempo de execução do mergeSort para um subarray de n elementos como a soma do tempo de duas execuções do mergeSort em um subarranjo de (n/2) elementos (para o passo da conquista) mais cn (para os passos da divisão e combinação—na verdade apenas para a intercalação de elementos).
Agora temos que verificar o tempo de execução para duas chamadas recursivas de n/2 elementos. Cada uma dessas duas chamadas recursivas leva duas vezes o tempo de execução do mergeSort em um subarray de (n/4) elementos (porque temos que dividir n/2 pela metade) mais cn/2 para intercalar. Nós temos dois subproblemas de tamanho n/2, e cada um leva um tempo cn/2 para intercalar, então o tempo total que gastamos para intercalar subproblemas de tamanho n/2 é 2⋅cn/2=cn.
Vamos traçar os tempos de combinação em uma "árvore":
Um diagrama com uma árvore à esquerda e tempos de merge à direita. A árvore está identificada como "Tamanho do subproblema" e a parte à direita está identificada como "Tempo total de merge para todos os subproblemas desse tamanho". O primeiro nível da árvore mostra um único nó n e o tempo de merge correspondente de c vezes n. O segundo nível da árvore mostra dois nós, cada um de 1/2 n, e um tempo de merge de 2 vezes c vezes 1/2 n, o mesmo que c vezes n.
Cientistas da computação desenham árvores de cabeça para baixo em relação como árvores de verdade crescem. Uma árvore é um grafo sem ciclos (caminhos que começam e terminam no mesmo lugar). É convencionado chamar os vértices de uma árvores de nós. O nó raiz fica em cima; aqui, a raiz é rotulada com o tamanho do subarray de tamanho n para o array de n elementos original. Abaixo da raiz há dois nós filhos, cada um indicado por n/2 para representar os tamanhos de subarray para os dois subproblemas de tamanho n/2.
Cada um dos subproblemas de tamanho n/2 ordena recursivamente dois subarrays de tamanho (n/2)/2, ou n/4. Como há dois subproblemas de tamanho n/2, há quatro subproblemas de tamanho n/4. Cada um desses quatro subproblemas intercala um total de n/4 elementos, e então o tempo para intercalar cada um dos quatro subproblemas é cn/4. Somados os quatro subproblemas, podemos verificar que o tempo total de intercalação de todos os quatro subproblemas de tamanho n/4 é 4⋅cn/4=cn:
Um diagrama com uma árvore à esquerda e tempos de merge à direita. A árvore está identificada como "Tamanho do subproblema" e a parte à direita está identificada como "Tempo total de merge para todos os subproblemas desse tamanho". O primeiro nível da árvore mostra um único nó n e o tempo de merge correspondente de c vezes n. O segundo nível da árvore mostra dois nós, cada um de 1/2 n, e um tempo de merge de 2 vezes c vezes 1/2 n, o mesmo que c vezes n. O terceiro nível da árvore mostra quatro nós, cada um de 1/4 n, e um tempo de merge de 4 vezes c vezes 1/4 n, o mesmo que c vezes n.
O que você acha que aconteceria com subproblemas de tamanho n/8? Haverá oito deles, e o tempo de intercalação para cada um será cn/8, com um tempo de intercalação total de 8⋅cn/8=cn:
Um diagrama com uma árvore à esquerda e tempos de merge à direita. A árvore está identificada como "Tamanho do subproblema" e a parte à direita está identificada como "Tempo total de merge para todos os subproblemas desse tamanho". O primeiro nível da árvore mostra um único nó n e o tempo de merge correspondente de c vezes n. O segundo nível da árvore mostra dois nós, cada um de 1/2 n, e um tempo de merge de 2 vezes c vezes 1/2 n, o mesmo que c vezes n. O terceiro nível da árvore mostra quatro nós, cada um de 1/4 n, e um tempo de merge de 4 vezes c vezes 1/4 n, o mesmo que c vezes n. O quarto nível da árvore mostra oito nós, cada um de 1/8 n, e um tempo de merge de 8 vezes c vezes 1/8 n, o mesmo que c vezes n.
Conforme os subproblemas ficam menores, o número de subproblemas dobra em cada "nível" de recursão, mas o tempo da intercalação cai pela metade. O dobro de subproblemas e a queda pela metade do tempo de intercalação se cancelam, então o tempo total de intercalação é cn em cada nível de recursão. Em algum momento, nós descemos até subproblemas de tamanho 1: o caso base. Temos que gastar um tempo Θ(1) para ordenar subarrays de tamanho 1, porque temos que testar se p<r, e esse teste leva tempo. Quantos subarrays de tamanho 1 existem? Como nós começamos com n elementos, deve haver n subarrays de tamanho 1. Como cada caso base leva Θ(1), vamos dizer que juntos os casos bases levam um tempo cn:
Um diagrama com uma árvore à esquerda e tempos de merge à direita. A árvore está identificada como "Tamanho do subproblema" e a parte à direita está identificada como "Tempo total de merge para todos os subproblemas desse tamanho". O primeiro nível da árvore mostra um único nó n e o tempo de merge correspondente de c vezes n. O segundo nível da árvore mostra dois nós, cada um de 1/2 n, e um tempo de merge de 2 vezes c vezes 1/2 n, o mesmo que c vezes n. O terceiro nível da árvore mostra quatro nós, cada um de 1/4 n, e um tempo de merge de 4 vezes c vezes 1/4 n, o mesmo que c vezes n. O quarto nível da árvore mostra oito nós, cada um de 1/8 n, e um tempo de merge de 8 vezes c vezes 1/8 n, o mesmo que c vezes n. Abaixo desse nível, são mostrados pontos para indicar que a árvore continua assim. Um nível final é mostrado com n nós de 1 e um tempo de merge de n vezes c, o mesmo que c vezes n.
Agora sabemos quanto tempo a intercalação leva para cada tamanho de subproblema. O tempo total para o mergeSort é a soma dos tempos de intercalação para todos os níveis. Se há l níveis na árvore, então o tempo de intercalação total é l⋅cn. Então o que é o l? Começamos com subproblemas de tamanho n e dividimos pela metade repetidamente até chegarmos a problemas de tamanho 1. Vimos essa característica quando analisamos a busca binária, e a resposta é l=log2⁡n+1. Por exemplo, se n=8, então log2⁡n+1=4, e com certeza a árvore tem quatro níveis: n=8,4,2,1. O tempo total para o mergeSort, entã,o é cn(log2⁡n+1). Quando usamos a notação Θ-grande para descrever esse tempo de execução, podemos descartar o termo de menor ordem (+1) e o coeficiente constante (c), ficando com um tempo de execução de Θ(nlog2⁡n), conforme prometido.
Há mais uma coisa sobre o merge sort que vale a pena destacar. Durante a intercalação, ele faz uma cópia de todo o array que está sendo ordenado, com uma metade em lowHalf e a outra metade em highHalf. Como ele copia mais do que um número constante de elementos em algum momento, dizemos que o merge sort não trabalha no mesmo local. Em contrapartida, o ordenamento por seleção e o ordenamento por inserção trabalham no mesmo local, como eles nunca copiam mais do que um número constante de elementos do array em qualquer momento. Cientistas da computação gostam de levar em conta se um algoritmo trabalha no mesmo local porque há alguns sistemas em que o espaço é escasso, então algoritmos que trabalham no mesmo local têm preferência.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Entrar
Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.