Conteúdo principal
Computer science theory
Análise do merge sort
Dado que a função quando está intercalando elementos, como podemos demonstrar que o ? 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 elementos em todo o array.
merge
é executada em um tempo mergeSort
é executado em um tempo - 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
dos índices e . Lembre que na notação Θ-grande, nós denotamos o tempo constante como . - O passo da conquista, em que nós ordenamos recursivamente dois subarrays de aproximadamente
elementos cada, leva algum tempo, mas vamos contar esse tempo quando considerarmos os subproblemas. - O passo da combinação intercala um total de
elementos, levando um tempo .
Se pensarmos nos passos da divisão e combinação juntos, o tempo de execução do passo da divisão é de ordem menor quando comparado com o tempo de execução do passo da combinação. Então vamos considerar que os passos da divisão e combinação juntos levam um tempo . Para deixar as coisas mais concretas, vamos dizer que os passos da divisão e da combinação levam tempo em que é alguma constante.
Para manter tudo mais simples, vamos assumir que se , então é sempre par, assim quando precisarmos pensar sobre , estaremos sempre pensando em um inteiro. (Contando o caso em que é ímpar não muda o resultado em termos da notação Θ-grande.) Então agora podemos pensar no tempo de execução do elementos como a soma do tempo de duas execuções do elementos (para o passo da conquista) mais (para os passos da divisão e combinação—na verdade apenas para a intercalação de elementos).
mergeSort
para um subarray de mergeSort
em um subarranjo de Agora temos que verificar o tempo de execução para duas chamadas recursivas de elementos. Cada uma dessas duas chamadas recursivas leva duas vezes o tempo de execução do elementos (porque temos que dividir pela metade) mais para intercalar. Nós temos dois subproblemas de tamanho , e cada um leva um tempo para intercalar, então o tempo total que gastamos para intercalar subproblemas de tamanho é .
mergeSort
em um subarray de 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 para o array de elementos original. Abaixo da raiz há dois nós filhos, cada um indicado por para representar os tamanhos de subarray para os dois subproblemas de tamanho .
Cada um dos subproblemas de tamanho ordena recursivamente dois subarrays de tamanho , ou . Como há dois subproblemas de tamanho , há quatro subproblemas de tamanho . Cada um desses quatro subproblemas intercala um total de elementos, e então o tempo para intercalar cada um dos quatro subproblemas é . Somados os quatro subproblemas, podemos verificar que o tempo total de intercalação de todos os quatro subproblemas de tamanho é :
O que você acha que aconteceria com subproblemas de tamanho ? Haverá oito deles, e o tempo de intercalação para cada um será , com um tempo de intercalação total de :
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 é 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 para ordenar subarrays de tamanho 1, porque temos que testar se , e esse teste leva tempo. Quantos subarrays de tamanho 1 existem? Como nós começamos com elementos, deve haver subarrays de tamanho 1. Como cada caso base leva , vamos dizer que juntos os casos bases levam um tempo :
Agora sabemos quanto tempo a intercalação leva para cada tamanho de subproblema. O tempo total para o níveis na árvore, então o tempo de intercalação total é . Então o que é o ? Começamos com subproblemas de tamanho 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 é . Por exemplo, se , então , e com certeza a árvore tem quatro níveis: . O tempo total para o . Quando usamos a notação Θ-grande para descrever esse tempo de execução, podemos descartar o termo de menor ordem ( ) e o coeficiente constante ( ), ficando com um tempo de execução de , conforme prometido.
mergeSort
é a soma dos tempos de intercalação para todos os níveis. Se há mergeSort
, entã,o é 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.