Conteúdo principal
Ciência da Computação
Análise do merge sort
Dado que a função
merge é executada em um tempo \Theta, left parenthesis, n, right parenthesis quando está intercalando n elementos, como podemos demonstrar que o mergeSort é executado em um tempo \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis? 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.- 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 \Theta, left parenthesis, 1, right parenthesis.
- O passo da conquista, em que nós ordenamos recursivamente dois subarrays de aproximadamente n, slash, 2 elementos cada, leva algum tempo, mas vamos contar esse tempo quando considerarmos os subproblemas.
- O passo da combinação intercala um total de n elementos, levando um tempo \Theta, left parenthesis, n, right parenthesis.
Se pensarmos nos passos da divisão e combinação juntos, o tempo de execução \Theta, left parenthesis, 1, right parenthesis do passo da divisão é de ordem menor quando comparado com o tempo de execução \Theta, left parenthesis, n, right parenthesis do passo da combinação. Então vamos considerar que os passos da divisão e combinação juntos levam um tempo \Theta, left parenthesis, n, right parenthesis. Para deixar as coisas mais concretas, vamos dizer que os passos da divisão e da combinação levam tempo c, n em que c é alguma constante.
Para manter tudo mais simples, vamos assumir que se n, is greater than, 1, então n é sempre par, assim quando precisarmos pensar sobre n, slash, 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 left parenthesis, n, slash, 2, right parenthesis elementos (para o passo da conquista) mais c, n (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, slash, 2 elementos. Cada uma dessas duas chamadas recursivas leva duas vezes o tempo de execução do
mergeSort em um subarray de left parenthesis, n, slash, 4, right parenthesis elementos (porque temos que dividir n, slash, 2 pela metade) mais c, n, slash, 2 para intercalar. Nós temos dois subproblemas de tamanho n, slash, 2, e cada um leva um tempo c, n, slash, 2 para intercalar, então o tempo total que gastamos para intercalar subproblemas de tamanho n, slash, 2 é 2, dot, c, n, slash, 2, equals, c, n.Vamos traçar os tempos de combinação em uma "árvore":
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, slash, 2 para representar os tamanhos de subarray para os dois subproblemas de tamanho n, slash, 2.
Cada um dos subproblemas de tamanho n, slash, 2 ordena recursivamente dois subarrays de tamanho left parenthesis, n, slash, 2, right parenthesis, slash, 2, ou n, slash, 4. Como há dois subproblemas de tamanho n, slash, 2, há quatro subproblemas de tamanho n, slash, 4. Cada um desses quatro subproblemas intercala um total de n, slash, 4 elementos, e então o tempo para intercalar cada um dos quatro subproblemas é c, n, slash, 4. Somados os quatro subproblemas, podemos verificar que o tempo total de intercalação de todos os quatro subproblemas de tamanho n, slash, 4 é 4, dot, c, n, slash, 4, equals, c, n:
O que você acha que aconteceria com subproblemas de tamanho n, slash, 8? Haverá oito deles, e o tempo de intercalação para cada um será c, n, slash, 8, com um tempo de intercalação total de 8, dot, c, n, slash, 8, equals, c, 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 é c, n 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 \Theta, left parenthesis, 1, right parenthesis para ordenar subarrays de tamanho 1, porque temos que testar se p, is less than, 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 \Theta, left parenthesis, 1, right parenthesis, vamos dizer que juntos os casos bases levam um tempo c, 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, dot, c, n. 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, equals, log, start base, 2, end base, n, plus, 1. Por exemplo, se n, equals, 8, então log, start base, 2, end base, n, plus, 1, equals, 4, e com certeza a árvore tem quatro níveis: n, equals, 8, comma, 4, comma, 2, comma, 1. O tempo total para o mergeSort, entã,o é c, n, left parenthesis, log, start base, 2, end base, n, plus, 1, right parenthesis. Quando usamos a notação Θ-grande para descrever esse tempo de execução, podemos descartar o termo de menor ordem (plus, 1) e o coeficiente constante (c), ficando com um tempo de execução de \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, 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?
Nenhuma postagem por enquanto.