Conteúdo principal

Curso: Computer science theory > Unidade 1

Lição 4: Selection sort

Análise do selection sort

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

, existem

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

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

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.

Na primeira chamada da indexOfMinimum, ela precisa verificar todos os valores do array, portanto o laço em indexOfMinimum é executado 8 vezes.
Na segunda chamada da indexOfMinimum, ela precisa verificar cada valor no subarray do índice 1 ao 7, portanto o laço em indexOfMinimum é 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 $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?

\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:

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

2, 5 \cdot 6 = 15

, e temos a resposta certa.

E se a sequência de somas for de 1 a

n

? Nós chamamos isto de série aritmética. A soma do menor e maior números é

n + 1

. Porque existem

n

números no total, existem

n / 2

pares (seja

n

ímpar ou par). Portanto, a soma dos números de 1 a

n

(n + 1) (n / 2)

, que é igual a

n^{2} / 2 + n / 2

. Tente esta fórmula para

n = 5

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:

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á

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)

. 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

, para outro tempo

Θ (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

na primeira chamada, depois

n - 1

, em seguida

n - 2

, e assim por diante. Vimos que esta soma,

1 + 2 + \dots + (n - 1) + n

, é uma série aritmética e ela resulta em

(n + 1) (n / 2)

, ou

n^{2} / 2 + n / 2

. Portanto, o tempo total para todas as chamadas da indexOfMinimum é um tempo constante vezes

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 é

Θ (n^{2})

Adicionando o tempo de execução para as três partes, temos

Θ (n^{2})

para as chamadas da indexOfMinimum,

Θ (n)

para as chamadas da swap, e

Θ (n)

para o resto do laço em selectionSort. O termo

Θ (n^{2})

é mais significativo, por isso dizemos que o tempo de execução da ordenação por seleção é

Θ (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á

n^{2} + n / 2

iterações, independentemente da entrada. Portanto, podemos dizer que a ordenação por seleção é executada no tempo

Θ (n^{2})

em todos os casos.

Vamos ver como o tempo de execução

Θ (n^{2})

afeta o tempo real de execução. Digamos que a ordenação por seleção leva aproximadamente

n^{2} / 10^{6}

segundos para ordenar

n

valores. Vamos começar com um valor bastante pequeno de

n

, digamos

n = 100

. Então o tempo de execução da ordenação por seleção é em torno de

100^{2} / 10^{6} = 1 / 100

segundo. Isso parece bastante rápido. Mas e se

n = 1000

? A ordenação leva em torno de

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

? O ordenação por seleção leva

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.

Quer participar da conversa?

Entrar

Classificar por:

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.

Computer science theory

Curso: Computer science theory > Unidade 1

Nota: Calculando somas de 1 a n‍

Análise assintótica do tempo de execução da ordenação por seleção

Quer participar da conversa?

Nota: Calculando somas de 1 a $n$ ‍