Analise o seguinte trecho de código:
para i = 1 até n - 1
para j = i + 1 até n
se (A[i] > A[j]) então
troque A[i] e A[j]Quantas vezes é executada a comparação da terceira linha?
Analisamos isso da seguinte forma:
Assim, o total de comparações é (Equação 1.1):
\begin{align*} (n - 1) + (n - 2) + ... + 1 \end{align*}Para $n = 5$, por exemplo, temos:
\begin{align*} (n - 1) + (n - 2) + ... + 1 = \\ (5 - 1) + (5 - 2) + ... + 1 = \\ 4 + 3 + 2 + 1 = 10 \end{align*}O código a seguir, em Python, demonstra esse comportamento:
In [1]:
n = 5
k = 0
for i in range(n - 1): # range(n) gera n números, de 0...n-1
for j in range(i + 1, n):
print('Comparando A[%d] > A[%d]' % (i + 1, j + 1)) # + 1 para facilitar a interpretação da saída
k = k + 1
print(k, ' Comparações')
Podemos melhorar o raciocínio para interpretar a contagem da quantidade de comparações utilizando a linguagem de conjuntos. Suponha que o conjunto $S$ contenha todas as comparações feitas pelo algoritmo. Dividimos o conjunto $S$ em $n - 1$ partes (ou conjuntos menores, ou, ainda subconjuntos):
Assim, descobrimos o número de comparações em cada conjunto $S_i$ e acumulamos para obter o tamanho do conjunto $S$.
Exemplo:
Para $n = 5$:
Cada conjunto $S_i$ é um conjunto disjunto dos demais porque as comparações que cada um contém são diferentes das presentes nos outros conjuntos. Em outras palavras, conjuntos são chamados disjuntos quando não possuem elementos em comum. Assim, $S = \{S_1, S_2, ..., S_m\}$ (com $m = n - 1$) é uma família de conjuntos mutuamente disjuntos. Seguindo esse pensamento podemos estabelecer o Princípio da adição:
Princípio da adição
O tamanho da união de uma família de conjuntos finitos mutuamente disjuntos é a soma dos tamanhos dos conjuntos.
Podemos aplicar o princípio da adição para resolver o problema em questão. Considere que $|S|$ indique o tamanho do conjunto $S$, então:
\begin{align*} \left|S_1 \cup S_2 \cup ... \cup S_m\right| = \left|S_1\right| + \left|S_2\right| + ... + \left|S_m\right| \end{align*}ou, usando a notação de união:
\begin{align*} \left|\bigcup_{i = 1}^m S_i \right| = \sum_{i = 1}^m \left|S_i\right| \end{align*}Exemplo:
Para $n = 5$:
\begin{align*} \left|\bigcup_{i = 1}^m S_i \right| = \left|S_1\right| + \left|S_2\right| + \left|S_3\right| + \left|S_4\right| \\ = 4 + 3 + 2 + 1 \\ = 10 \end{align*}Quando $S = \bigcup_{i = 1}^k S_i$, então temos um $S$ particionado nos conjuntos $S_1, S_2, ..., S_k$ e estes formam uma partição de $S$.
Exemplo:
Isso permite redefinir o Princípio da adição:
Princípio da adição
Se um conjunto finito $S$ foi dividido em blocos, então o tamanho de $S$ é a soma do tamanho dos blocos.
Voltando para a Equação 1.1, ela pode ser escrita como:
\begin{align*} \sum_{i = 1}^{n - 1}(n - i) \end{align*}Demonstramos assim, para $n = 5$:
\begin{align*} \sum_{i = 1}^{n - 1}(n - i) = (5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 4 + 3 + 2 + 1 = 10 \end{align*}Isso mostra que, na prática:
\begin{align*} \sum_{i = 1}^{n - 1}(n - i) = 1 + 2 + 3 + 4 = \sum_{1 = 1}^{n - 1}i \end{align*}Entretanto, podemos tentar encontrar uma forma de reduzir ou simplificar essa equação. Vamos experimentar o seguinte:
Esses artifícios são feitos para que a soma entre os elementos correspondentes de $s_1$ e $s_2$ seja igual ao mesmo elemento em $s_3$. Esse raciocínio leva a algumas conclusões:
A conclusão final desse raciocínio é que:
\begin{align*} \sum_{i = 1}^{n - 1}(n - i) = \sum_{1 = 1}^{n - 1}i = \frac{n \times (n - 1)}{2} \end{align*}Esse artifício foi utilizado por Carl Friedrich Gauss e, por fim, fornece uma forma útil para situações que envolvam encontrar a soma de uma série de valores ou variáveis.
Seguindo a mesma abordagem para entender o princípio da adição, veja o seguinte trecho de código que encontra o produto de duas matrizes ($A \times B = C$):
para i = 1 até r
para j = 1 até m
s = 0
para k = 1 até n
s = s + A[i, k] * B[k, j]
C[i, j] = sQuantas multiplicações (A[i, k] * B[k, j]) esse código executa ao final de todas as iterações (em termos de r, m, e n)?
O laço mais interno executa exatamente $n$ multiplicações. O laço anterior, repete o laço mais interno $m$ vezes. Assim, executa $n \times m$ multiplicações. Pensando no contexto de conjuntos, como foi feito na abstração do princípio da adição, temos que para todo $i$ o conjunto de multiplicações pode ser dividido em:
Seja $T_i$ o conjunto das multiplicações para todo $i$. Este conjunto é a união dos conjuntos $S_j$:
\begin{align*} T_i = \bigcup_{j = 1}^m S_j \end{align*}Usando o princípio da adição, o tamanho de $T_i$ é igual à soma dos tamanhos de cada conjunto $S_j$. A soma de $m$ números, cada um igual a $n$ é $m \times n$ (Equação 1.3):
\begin{align*} \left| T_i \right| = \left| \bigcup_{j = 1}^m S_j \right| = \sum_{j = 1}^m \left| S_j \right| = \sum_{j = 1}^m n = m \times n \end{align*}Princípio do produto
O tamanho da união de conjuntos disjuntos $m$, sendo cada um de tamanho $n$, é $m \times n$.
Pelo princípio do produto, concluímos que o código do produto entre duas matrizes executa $r \times m \times n$ multiplicações.
Voltemos ao código usado no princípio da adição. Algumas considerações:
Para cada número de $i$ e $j$, é feita a comparação entre $A[i]$ e $A[j]$ exatamente uma vez. Desta forma, o número de comparações é o mesmo que o número de subconjuntos de dois elementos do conjunto $\{1, 2, ..., n\}$. Uma questão importante é: de quantas maneiras diferentes podemos escolher dois elementos desse conjunto?
Antes de responder essa pergunta, é importante apresentar o conceito de par ordenado. Um par ordenado contém um elemento na primeira posição e outro na segunda. Por exemplo, temos o par ordenado $(2, 5)$, que é diferente do par ordenado $(5, 2)$, pois a ordem dos elementos é importante aqui.
O problema se torna descobrir a quantidade de pares ordenados que podem ser criados com os elementos do conjunto em questão.
O raciocínio é este: ao escolhermos determinados primeiro e segundo elemento, existem $n$ maneiras de se escolher o primeiro elemento, e para cada escolha dele, há $n - 1$ maneiras de se escolher o segundo. Numericamente, para $n = 5$, escolhendo para primeiro elemento, nesta ordem, $1, 2, 3, 4$:
Assim, pelo princípio do produto, poderíamos concluir que a quantidade de pares ordenados é $n \times (n - 1)$. Para $n = 5$, teríamos $5 \times (5 - 1) = 20$.
Como cada par $(x, y)$ de elementos de $\{1, 2, ..., n\}$ pode ser ordenado de duas formas, basta contar cada par apenas uma vez. Assim, o número de subconjuntos com dois elementos em $\{1, 2, ..., n\}$ é $n \times (n - 1) / 2$. Isso também pode ser representado usando a notação $\binom{n}{2}$, que pode ser lida como "n escolha 2". Assim:
\begin{align*} 1 + 2 + ... + (n - 1) = \binom{n}{2} = \frac{n \times (n - 1)}{2} \end{align*}
In [2]:
n = 5
S = [i for i in range(1, n + 1)]
print('S = {', ', '.join([str(i) for i in S]), '}')
Pares = []
for i in range(n):
for j in range(i + 1, n):
Pares.append('(%d, %d)' % (i + 1, j + 1))
print('Pares = {', ', '.join([i for i in Pares]), '}')
print(len(Pares), ' Pares')