Ordenação por seleção itera sobre índices de array; para cada índice, a ordenação por seleção chama indexOfMinimum e swap. Se o tamanho do array é n n , existem n n índices no array.
Uma vez que cada execução do corpo do laço executa duas linhas de código, você pode pensar que 2n 2 n 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 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 n n vezes. Se o tamanho do subarray for 6, então o corpo do laço executa 6 vezes.
Por exemplo, digamos que o array inteiro tenha tamanho 8 e vamos pensar em como a ordenação por seleção funciona.
  1. Na primeira chamada da indexOfMinimum, ela tem de verificar todos os valores do array, portanto o laço em indexOfMinimum executa 8 vezes.
  2. Na segunda chamada da indexOfMinimum, ela precisa verificar cada valor no subarray do índice 1 ao 7, portanto o laço na indexOfMinimum executa 7 vezes.
  3. Na terceira chamada, são verificados no subarray os índices de 2 ao 7; o corpo do laço executa 6 vezes.
  4. Na quarta chamada, verifica o subarray do índice 3 ao 7; o corpo do laço executa 5 vezes.
  5. Na oitava e última chamada da indexOfMimimum, o corpo do laço executa 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 n n

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?
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=49=36 . \begin{aligned} (8 + 1) + (7 + 2) + (6 + 3) + (5 + 4) &= 9 + 9 + 9 + 9 \\ &= 4 \cdot 9 \\ &= 36 \ . \end{aligned}
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:
  1. Some o menor e o maior número.
  2. 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 2.56=15 2.5 \cdot 6 = 15 , e temos a resposta certa.
E se a sequência de somas for de 1 a n n ? Nós chamamos isto de série aritmética. A soma do menor e maior números é n+1 n + 1 . Porque existem n n números no total, existem n/2 n/2 pares (seja n n ímpar ou par). Portanto, a soma dos números de 1 a n n é (n+1)(n/2) (n + 1)(n / 2) , que é igual a n2/2+n/2 n^2/2 + n/2 . Tente esta fórmula para n=5 n = 5 e n=8 n = 8 .

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:
  1. O tempo de execução para todas as chamadas de indexOfMinimum.
  2. O tempo de execução para todas as chamadas de swap.
  3. 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á n n chamadas de swap, e cada chamada leva um tempo constante. Usando nossa notação assintótica, o tempo para todas as chamadas de swap é Θ(n) \Theta(n) . O resto do laço em 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 n n , para outro tempo Θ(n) \Theta(n) .
Para a parte 1, 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 é n n na primeira chamada, depois n1 n-1 , em seguida n2 n-2 , e assim por diante. Vimos que esta soma, 1+2++(n1)+n 1 + 2 + \cdots + (n-1) + n , é uma série aritmética e ela resulta em (n+1)(n/2) (n+1)(n/2) , ou n2/2+n/2 n^2/2 + n/2 . Portanto, o tempo total para todas as chamadas da indexOfMinimum é um tempo constante vezes n2/2+n/2 n^2/2 + n/2 . 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 é Θ(n2) \Theta(n^2) .
Adicionando o tempo de execução para as três partes, temos Θ(n2) \Theta(n^2) para as chamadas da indexOfMinimum, Θ(n) \Theta(n) para as chamadas da swap, e Θ(n) \Theta(n) para o resto do laço em selectionSort. O termo Θ(n2) \Theta(n^2) é mais significativo, por isso dizemos que o tempo de execução da ordenação por seleção é Θ(n2) \Theta(n^2) .
Observe também que nenhum caso é particularmente bom ou particularmente ruim para a ordenação por seleção. O laço em indexOfMinimum sempre fará n2+n/2 n^2 + n/2 iterações, independentemente da entrada. Portanto, podemos dizer que a ordenação por seleção executa no tempo Θ(n2) \Theta(n^2) em todos os casos.
Vamos ver como o tempo de execução Θ(n2) \Theta(n^2) afeta o tempo real de execução. Digamos que a ordenação por seleção leva aproximadamente n2/106 n^2/10^6 segundos para ordenar n n valores. Vamos começar com um valor bastante pequeno de n n , digamos n=100 n = 100 . Então o tempo de execução da ordenação por seleção é em torno de 1002/106=1/100 100^2/10^6 = 1/100 segundo. Isso parece bastante rápido. Mas e se n=1000 n = 1000 ? A ordenação leva em torno de 10002/106=1 1000^2/10^6 = 1 segundo. O array cresceu por um fator de 10, mas o tempo de execução aumentou 100 vezes. O que acontece se n=1.000.000 n = 1{.}000{.}000 ? O ordenação por seleção leva 1.000.0002/106=1.000.000 1{.}000{.}000^2/10^6 = 1{.}000{.}000 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.
Carregando