Complexidade de pior caso Insertion-Sort - Parte2

O pior caso resulta de quando o arranjo A está totalmente invertido ou em ordem decrescente. Neste caso a linha 4 será executada tanto quanto for o comprimento do arranjo A menos um, ou seja, j vezes porque neste caso, A[i] > k levando a execução das linhas 5 e 6 j - 1 vezes. Disto resulta o somatório de j=2 até n(j) = [n(n + 1)/2]-1 para a linha 4 e j=2 até n(j-1) = n(n-1)/2 para as linhas 5 e 6. Substituindo na nossa fórmula encontrada no post passado e ignorando a constante que é a mesma e sabemos agora não alterará o que queremos saber, que é complexidade da função, temos:

T(n)= n + (n-1) + (n-1) + [n(n+1)/2]-1 + [n(n-1)/2] + [n(n-1)/2 + (n-1) = 3n^2 + 7/2n - 4 

que é uma função quadrática ou do segundo grau. Assim, a complexidade de pior caso deste algorítimo é de quadrática. A complexidade do caso médio não nos interessa a esta análise e normalmente não é utilizada. No próximo post, evoluímos desta fórmula para uma notação mais simples, a ordem de crescimento da função.

1-            for j = 2 to A.comprimento                                    c1  n

2-                k = A[ j ]                                                             c2 (n-1)

3-                i = j - 1                                                                c3 (n-1)

4-                while i > 0 e A[ i ]> k                                         c4 [n(n+1)/2]-1

5-                        A[ i + 1] = A[ i ]                                         c5 [n(n-1)/2]

6-                         i = i - 1                                                       c6 [n(n-1)/2]

7-                A[ i + 1 ] = k                                                       c7 (n-1)

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

 

Ordenação Insertion-Sort parte 2 - complexidade de melhor caso

Medimos a complexidade na unidade tempo de execução na maioria das vezes. Em algorítimos como o Insertion-Sort esse tempo de dois fatores: O tamanho da entrada e a ordenação desta entrada. Para ordenar 3 números exige-se um tempo menor do que para ordenar 100. Da mesma maneira, a ordenação destes mesmos números em ordem decrescente leva mais tempo do que se apenas uma parte estiver desordenada. Na análise a seguir, admitamos a constante c em cada linha do pseudo-código como constante de tempo em função da quantidade n de vezes em que esta linha é executada. Daí somamos as resultantes para determinar o tempo de execução. Esta fórmula encontrada será usada para definir uma notação simples para comparar a eficiência de um algorítimo com outro:

linha do pseudo-code                                 constante c de Tempo e número n de vezes da execução

1-            for j = 2 to A.comprimento                                    c1  n

2-                k = A[ j ]                                                             c2 (n-1)

3-                i = j - 1                                                                c3 (n-1)

4-                while i > 0 e A[ i ]> k                                         c4 [n(n+1)/2]-1

5-                        A[ i + 1] = A[ i ]                                         c5 [n(n-1)/2]

6-                         i = i - 1                                                       c6 [n(n-1)/2]

7-                A[ i + 1 ] = k                                                       c7 (n-1)

Associamos ao c o número da linha por razões didáticas. A soma destas linhas é igual ao tempo de execução do algorítimo T(n). 

T(n)= c1n + c2(n-1) + c3(n-1) + c4[n(n+1)/2]-1 + c5[n(n-1)/2] + c6[n(n-1)/2 + c7(n-1) 

percebe-se que o tempo de ordenação fica amarrado ao tamanho da entrada n e eventualmente à sua ordenação. Observe que para uma entrada hipoteticamente totalmente ordenada resulta no que chamamos de melhor caso. Vemos que na linha 4 o valor A[i] será <= k e neste caso nunca entraremos no laço, por consequência, esta linha será executada (n-1) vezes e as linhas 5 e 6 não serão executadas. Portanto, T(n)= c1 + c2(n-1) + c3(n-1) + c4(n-1) + c7(n-1)=

= (c1 + c2 + c3 + c4 + c7)n - (c2 + c3 + c4 + c7)  o que nada mais é que uma função de primeiro grau an+b para duas constantes a e b. Em resumo, o tempo de execução do melhor caso é T(n)=an+b.

A seguir, próximo post, análise do pior caso

Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.

Algorítimo de ordenação Insertion-Sort

Seguindo o assunto da análise de complexidade de algorítimos, vamos começar analisando um problema clássico que é o de ordenar números naturais de um determinado arranjo de entrada em um arranjo semelhante, entretanto, ordenado de forma crescente. Existem várias abordagens clássicas que solucionam esse problema, mas, precisamos aqui de apenas duas para poder analisar as suas complexidades e estabelecer o "melhor" neste caso.  Inicialmente vamos ver o algorítimo que faz isso por inserção. Ele se chama Insertion-Sort. O problema a ser resolvido é: dado um arranjo A[ a1, a2, a3 ... an ] organizar o arranjo A de forma que A[a1 < a2  < a3 < .... < an]. Segue o pseudo-código de um dos algorítimos que se propõem a realizar esta tarefa:

1-            for j = 2 to A.comprimento

2-                k = A[ j ]

3-                i = j - 1

4-                while i > 0 e A[ i ]> k

5-                        A[ i + 1] = A[ i ]

6-                         i = i - 1

7-                A[ i + 1 ] = k

Este algorítimo começa com o índice j assumindo o valor 2 inicialmente, uma vez que a primeira posição no array já está ordenada. A variável k guarda o valor da posição que está sendo ordenada. O valor do índice i é empurrado uma posição de cada vez para a direita desde que ele seja maior que 0 e seu valor no arranjo maior que a varável k o que implica ser maior que j já que nesta altura da execução k = j. 

fig.:           i  j 

           1,2,3,4,5

      A [5|4|7|9|2]

A corretude (funcionamento correto) deste algorítimo pode ser comprovada aplicando uma técnica semelhante a indução matemática chamada de invariante de laço (loop invariant) com a qual demonstramos o funcionamento do algorítimo. Os passos da invariante de laço são três:

1- Inicialização: Onde a propriedade é verdadeira antes da primeira iteração

2- Manutenção: Se é verdadeiro antes da primeira iteração, será verdadeiro antes da próxima iteração

3- Término: Quando o loop acaba, a invariante nos fornece o resultado do loop, uma propriedade útil.

Observe no algorítimo que a primeira propriedade está comprovada pois se j = 1, o arranjo 1 até j está ordenado pois só tem um componente que é ele mesmo. A manutenção também é verdade por hipótese, uma vez que é verdade antes da primeira iteração. Agora, executando j a partir do índice 2 mostramos que o loop funciona quando ele retorna um valor útil indicando o término com sucesso. A invariante de laço é usada para provar algorítimos iterativos, porém, quando tratamos de algorítimos recursivos, como o próximo que veremos, o merge-Sort, usamos de fato, a indução matemática para mostrar que a função recursiva funciona. No próximo post, continuamos a análise verificando a complexidade do mesmo.

Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.

O que é análise de complexidade de um algorítimo?

Propomos um algorítimo com a finalidade de resolver problemas do mundo real. Porém, não é raro haver várias propostas de algorítimos para resolver o mesmo problema. E aí neste caso, qual o melhor algorítimo? Então buscamos mensurar a quantidade de recursos que um algorítimo precisa para funcionar. Recursos de processamento, memória e às vezes, largura de banda são os que primeiro nos vêm à mente. No entanto, quando analisamos um algorítimo é muito importante analisa-lo levando em conta o tempo de computação. No modelo de computação genérico temos instruções pré-definidas como instruções de soma, subtração, divisão, multiplicação, desvio condicional, carregamento, cópia e muitas outras. Cada instrução dessa leva um tempo constante para ser realizada. Mas, há algumas tarefas que precisam ser construídas, como por exemplo a ordenação de números naturais. Para isso precisamos construir um algorítimo que realize a tarefa com as operações que a máquina já contempla. Dessa forma, vários modos de realizar a mesma tarefa surgem, e analisar a complexidade de cada solução se torna necessário para eleger a mais aplicável aos recursos disponíveis. No próximo post trarei um problema de ordenação e uma solução para ele. A partir daí, iremos analisar esta proposta e determinar a sua complexidade. Depois vamos verificar outra proposta, com uma abordagem diferente, analisar sua complexidade, e inferir qual o mais eficiente. Inicialmente, o faremos de uma forma generalista, e depois usando ferramentas luxuosas de medida de complexidade, tratando o algorítimo como um modelo matemático de solução de problemas.

Algorítimos, Cormen, et al, 2012 3ed. capítulo 2.  

Redes Centradas na Informação - Uma nova abordagem para a internet

A pilha de protocolos TCP/IP é uma das maiores invenções da humanidade. Ela é o principal pilar sustentador da internet, ou seja, a internet do modo como conhecemos hoje só é possível por causa destes protocolos. Com sua capacidade indiscutivelmente incrível de rotear pacotes entre redes atribuída ao IP, seus protocolos de transporte que satisfazem tanto aplicações que exigem confirmação, como as que não possuem esta exigência, este protocolo atende bravamente demandas importantes de dados, vídeo e voz, mesmo sendo projetado numa época em que algumas dessas demandas não existiam ou tinham uma magnitude imensamente menor. Por outro lado, estas mesmas demandas crescentes, vem clamando por ajustes cada vez mais exaustivos para essa pilha de protocolos idosa. Além da escassez de endereços cuidada paliativamente pelo NAT, a dificuldade de mobilidade, necessidade de sistemas de conversão e resolução, esquema de segurança frágil, detre outros, trazem à tona a necessidade de se pensar em substituir esta arquitetura.

O paradigma ICN, Information Centric Network, principalmente, em sua implementação mais conhecida a NDN, named-data network é uma das abordagens mais promissoras. Saiba mais em https://named-data.net

Identificando a Classe do endereço IP pelo primeiro octeto

As faixas de endereços IPv4 são divididas em classes. A classe do endereço ajudou muito a seccionalizar o uso destes endereços. Claro que hoje em dia esse conceito não assume a importância que assumia antigamente, e provavelmente, a importância das classe A, B e C não detém tanta relevância. Porém, as classes D e E ainda identificam ranges de endereço de uso especial ainda muito aplicáveis e de grande relevância. Abaixo uma tabela com os ranges em decimal e suas classes:

Classe    Range de Endereços                         

A           0.0.0.1 - 126.255.255.255

B           128.0.0.0 - 191.255.255.255

C           192.0.0.0 - 223.255.255.255

D           224.0.0.0 - 234.255.255.255   multicast

E            240.0.0.0 - 255.255.255.254  reservado para testes IETF  

Uma forma rápida de identificar estes ranges é considerando estes números em binário. Existe uma regra chamada regra do primeiro octeto com a qual podemos identificar qual a classe do endereço facilmente:

Na classe A o primeiro bit é o 0

Na classe B os primeiros dois bits são 10

Na classe C os primeiros três bits são 110

Na classe D os primeiros quatro bits são 1110

Na classe E os primeiros cinco bits são 11110

Como o NAT direciona pacotes para o host correto na rede interna?

O protocolo TCP/IP é inquestionavelmente a pilha de protocolos mais usada no mundo. Essa maravilhosa invenção tornou possível a internet do modo como a conhecemos. De fato, escalonável, confiável e robusto este vovô parece imbatível ao passar dos anos. Porém, ele precisou de alguns remendos em sua trajetória. Devido aos 32 bits de endereçamento, ele é limitado no seu número de dispositivos endereçáveis. Muitas ações foram adotadas para poder retardar a exaustão completa do número de endereços. A separação de endereços públicos e privados foi uma delas. E é sobre isso que de que se trata o NAT. Network Address Translate é um artifício para que muitas máquinas em uma LAN usando endereços privados possam acessar a internet através de poucos ou até mesmo um único endereço público de WAN. No modo mais tradicional, um único endereço publico fornecido dinamicamente pela operadora pode carregar solicitações de vários hosts de uma rede privada. Isso é chamado de NAT overload ou Port Address Translate. Desse modo, por exemplo, uma rede privada com 14 hosts em um range 192.168.0.0/28 pode acessar a internet saindo por um endereço público apenas, digamos 200.2.2.1. Mas, daí surge uma questão: se todos os hosts estão acessando a internet pelo mesmo IP privado, como o roteador com NAT sabe de quem é determinado pacote de resposta? A solução está nas portas. Não é apenas a camada de transporte que usa portas. Além das portas típicas UDP/TCP, temos as portas lógicas do IP. Ou seja, quando um pacote sai para a internet através de um roteador NAT, ele registra a porta pela qual o dado será encaminhado como resposta, e daí, o nome Port Address Translate. Veja a tabela a seguir: 

R1# show ip nat translations
Pro Inside global           Inside local            Outside local         Outside global

udp 200.2.2.1:53427  192.168.0.6:53427      74.200.84.4:53        74.200.84.4:53

udp 200.2.2.1:53427  192.168.0.6:53427      195.170.0.1:53        195.170.0.1:53

tcp 200.2.2.1:53638   192.168.0.6:53638      64.233.189.99:80    64.233.189.99:80

tcp 200.2.2.1:57585   192.168.0.7:57585      69.65.106.48:110    69.65.106.48:110

tcp 200.2.2.1:57586   192.168.0.7:57586      69.65.106.48:110    69.65.106.48:110

Na exibição do comando acima vemos o host 192.168.0.6 usar a porta 53638 para acessar um serviço na internet através do IP público 200.2.2.1 que é o endereço de WAN do roteador onde está aplicado a NAT overload. Na mesma rede privada o host 192.168.0.7 usa a porta 57585 para acessar pelo mesmo IP público outro serviço na internet. Quando o pacote retorna, o host de destino é identificado à partir desta porta, assim, um único endereço válido na internet é usado por vários hosts não válidos para tráfego.