Conteúdo principal
Computer science theory
Curso: Computer science theory > Unidade 1
Lição 4: Selection sortAnálise do selection sort
Ordenação por seleção itera sobre índices de array; para cada índice, a ordenação por seleção chama , existem índices no array.
indexOfMinimum
e swap
. Se o tamanho do array é Uma vez que cada execução do corpo do laço executa duas linhas de código, você pode pensar que linhas de código são executadas pela ordenação por seleção. Mas isso não é verdade! Lembre que
indexOfMinimum
e swap
são funções: quando uma ou outra é chamada, algumas linhas de código são executadas.Quantas linhas de código são executadas por um única chamada da
swap
? Em implementações comuns, são três linhas, de modo que cada chamada da swap
lava um tempo constante.Quantas linhas de código são executadas por uma única chamada da vezes. Se o tamanho do subarray for 6, então o corpo do laço executa 6 vezes.
indexOfMinimum
? Temos que levar em conta o laço dentro de indexOfMinimum
. Quantas vezes este laço executa em uma dada chamada da indexOfMinimum
? Isso depende do tamanho do subarray que será percorrido. Se o subarray é o array inteiro (como é no primeiro passo), o corpo do laço executa Por exemplo, digamos que o array inteiro tenha tamanho 8 e vamos pensar em como a ordenação por seleção funciona.
- Na primeira chamada da
indexOfMinimum
, ela precisa verificar todos os valores do array, portanto o laço emindexOfMinimum
é executado 8 vezes. - Na segunda chamada da
indexOfMinimum
, ela precisa verificar cada valor no subarray do índice 1 ao 7, portanto o laço emindexOfMinimum
é executado 7 vezes. - Na terceira chamada, os índices do 2 ao 7 são verificados no subarray; o laço é executado 6 vezes.
- Na quarta chamada, ela verifica o subarray do índice 3 ao 7; o laço é executado 5 vezes.
- …
- Na oitava e última chamada de
indexOfMimimum
, o laço é executado apenas uma vez.
Se somarmos o número de vezes que o interior do laço da
indexOfMinimum
executa, temos 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 vezes.Nota: Calculando somas de 1 a
Como você pode calcular a soma de 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 rapidamente? Aqui está um truque. Vamos somar os números em uma ordem engenhosa. Primeiro, vamos adicionar 8 + 1, os valores maiores e menores. Temos 9. Então, vamos adicionar 7 + 2, o segundo maior e segundo menor valo. Interessante, obtemos 9 outra vez. Que tal 6 + 3? Também 9. Finalmente, 5 + 4. Mais uma vez, 9! Então o que temos?
Havia quatro pares de números, cada um somando 9. Então, aqui está o truque geral para somar qualquer sequência de números inteiros consecutivos:
- Some o menor e o maior número.
- Multiplique pelo número de pares.
E se o número de inteiros na sequência for ímpar, de modo que você não consiga formar pares com todos eles? Não importa! Simplesmente conte o número sem par no meio da sequência como meio par. Por exemplo, vamos somar 1 + 2 + 3 + 4 + 5. Temos dois pares completos (1 + 5 e 2 + 4, cada um somando 6) e um "meio par" (3, que é a metade de 6), em um total de 2,5 pares. Multiplicamos , e temos a resposta certa.
E se a sequência de somas for de 1 a ? Nós chamamos isto de série aritmética. A soma do menor e maior números é . Porque existem números no total, existem pares (seja ímpar ou par). Portanto, a soma dos números de 1 a é , que é igual a . Tente esta fórmula para e .
Análise assintótica do tempo de execução da ordenação por seleção
O tempo total de execução do selection sort tem três partes:
- O tempo de execução para todas as chamadas de
indexOfMinimum
. - O tempo de execução para todas as chamadas de
swap
. - O tempo de execução para o resto do laço na função
selectionSort
.
As partes 2 e 3 são fáceis. Sabemos que há chamadas de . O resto do laço em , para outro tempo .
swap
, e cada chamada leva um tempo constante. Usando nossa notação assintótica, o tempo para todas as chamadas de swap
é selectionSort
é realmente só para testar e incrementar a variável de laço e chamar indexOfMinimum
e swap
, e isso leva um tempo constante para cada uma das iterações Para a parte 1, o tempo de execução de todas as chamadas da na primeira chamada, depois , em seguida , e assim por diante. Vimos que esta soma, , é uma série aritmética e ela resulta em , ou . Portanto, o tempo total para todas as chamadas da . Em termos da notação grande-Θ, não nos importamos com esse fator constante, nem tampouco com o fator 1/2 ou o termo de baixa ordem. O resultado é que o tempo de execução de todas as chamadas da .
indexOfMinimum
, já fizemos a parte mais difícil. Cada iteração individual do laço em indexOfMinimum
leva um tempo constante. O número de iterações deste laço é indexOfMinimum
é um tempo constante vezes indexOfMinimum
é Adicionando o tempo de execução para as três partes, temos para as chamadas da para as chamadas da para o resto do laço em é mais significativo, por isso dizemos que o tempo de execução da ordenação por seleção é .
indexOfMinimum
, swap
, e selectionSort
. O termo Observe também que nenhum caso é particularmente bom ou particularmente ruim para a ordenação por seleção. O laço em iterações, independentemente da entrada. Portanto, podemos dizer que a ordenação por seleção é executada no tempo em todos os casos.
indexOfMinimum
sempre fará Vamos ver como o tempo de execução afeta o tempo real de execução. Digamos que a ordenação por seleção leva aproximadamente segundos para ordenar valores. Vamos começar com um valor bastante pequeno de , digamos . Então o tempo de execução da ordenação por seleção é em torno de segundo. Isso parece bastante rápido. Mas e se ? A ordenação leva em torno de segundo. O array cresceu por um fator de 10, mas o tempo de execução aumentou 100 vezes. O que acontece se ? O ordenação por seleção leva segundos, o que é um pouco mais que 11,5 dias. Aumentar o tamanho do array por um fator de 1000 aumenta o tempo de execução em um milhão de vezes!
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.