Estrutura de dados Aula 01

Prévia do material em texto

Estrutura de dados – Aula 01
Ao projetarmos um algoritmo, uma etapa fundamental é a especificação o projeto de seus dados de entrada. Esses mesmos são projetados pensando na aplicação e apresentarão tipos distintos. Dentre os tipos primitivos de dados podemos citar: inteiro, real, caractere e booleano.
Os tipos de dados manipulados por um algoritmo podem ser classificados em duas categorias distintas: dados primitivos (ou atômicos), que são dados indivisíveis, assim como inteiro, real, caractere e booleano; dados complexos que podem ser decompostos (complexos).
Se um dado pode ser dividido, isso significa que ele tem uma estrutura por trás, dando assim o nome de dado estruturado, o qual faz parte de uma estrutura de dados.
Estrutura de dados homogênea são aquelas que só podem trabalhar com um único tipo de dado, são grandes exemplos as matrizes e vetores.
Vetor
O vetor em suma, é inicializado pela sua primeira posição, ex.: (int) sendo 0x10 o primeiro endereço, o segundo sendo 0x14 e assim por diante... Tendo isso em mente:
Endereço n = Endereço inicial + (posição * quantidade de bytes (nesse caso, 4)).
Matrizes
Para cada dimensão de uma matriz, é necessário utilizar-se de um índice diferente. Considerando duas dimensões é necessário um índice i e j (sendo i para linha e j para colunas). O cálculo do endereço de uma matriz é:
Endereço n = Endereço inicial + (índice linha * índice coluna * quantidade de bytes) + (índice coluna * quantidade de bytes)
Estruturas de dados heterogênea ao contrário de homogênea, trabalha com tipos distintos de dados em uma estrutura, vide Struct (Registro).
Análise de complexidade de algoritmos
Ao programarmos uma solução para x problema, tencionamos a ver n soluções, e precisamos de uma maneira eficiente de se ter uma análise dessa solução em termos performáticos, para isso, temos a análise de complexidade dada por dois parâmetros vitais: tempo de execução e uso de memória volátil (RAM).
É importante denotar que, à medida que o conjunto de entradas de um programa cresce seu tempo de execução tende a crescer junto.
Função de custo do algoritmo
O custo em tempo de execução de um programa é o tempo que ele demora para encerrar sua execução. Podemos realizar o cálculo desse custo de forma empírica através de compiladores e afins, mas é bom salientar que, é pouco confiável e trabalhosa.
Como forma de abstrair nossa análise de hardware e de software que são alheios aos nossos ambientes, encontramos uma forma matemática de mensurar a nossa função custo, encontrando esse recurso podemos prever recursos utilizado pelo algoritmo.
Sendo a função custo: 
T(n) = Tempo de execução + Memória gasta
Em nossas análises utilizaremos a função custo desprezando a memória gasta para se adequar a medições feitas normalmente em ambientes de desenvolvimento.
Para encontrarmos esse custo em tempo de execução, consideramos as seguintes restrições no nosso ambiente de desenvolvimento:
Nossos códigos rodarão em um, e somente um, microprocessador por vez;
Não existirão operações concorrentes, somente sequenciais;
Consideraremos que todas as instruções do programa contêm um custo unitário, fixo e constante.
Uma instrução será uma operação ou manipulação simples realizada pelo programa, como: atribuição de valores, acesso a valores de variáveis, comparação de valores e operações aritméticas básicas.
Considerando as restrições citadas, observemos o código a seguir, que é um recorte contendo uma atribuição de uma variável e um laço de repetição vazio do tipo PARA.
Figura 1 – Código exemplo para contagem de instruções
Neste código temos várias instruções que podem ser contadas de forma unitária para determinamos sua função de custo. A figura a seguir resume todas as instruções unitárias, seus significados e respectiva linha em que aparecem.
Figura 2.
Algumas dessas instruções ocorrem somente uma vez no programa. É o caso da linha 3, linha 4 (primeira vez). Todas estas linhas totalizam 3 instruções. Porém, na linha 4 temos o laço de repetição. Esse laço será executado enquanto sua condição for satisfeita. Para cada execução dele, perceba que teremos duas instruções executando, portanto, serão 2n, em que n é o número de vezes que o nosso loop será executado menos um, pois, nesse caso, a primeira execução sempre ficará independente de qualquer coisa. Com isso, definimos que a função custo de tempo de execução da figura 2 se dá pela seguinte equação:
T(n) = 2n + 3
Vamos analisar agora, um segundo código. Esse mesmo, encontra o maior valor dentro de um vetor de dimensão variável.
Figura 3.
Observe que temos duas linhas de código a mais que o exemplo da figura 2: uma condicional (linha 9) e uma atribuição (linha 10), e que ambas as linhas são executadas n vezes dentro de um laço de repetição, ou seja, estão atrelados a ele (ao laço).
Nesse código temos diversas instruções de custo unitário para encontrarmos a função de custo deste.
Figura 4 – Contagem de instruções unitárias do código apresentado na figura 3.
Análise assintótica de algoritmos
Já entendemos um pouco sobre fazer o cálculo matemático por trás da complexidade computacional de um código, e alguns fatores que impactam em seu desempenho. Também vimos como é trabalhosa a realização da contagem manual de instruções até chegarmos às equações de custo apresentadas anteriormente.
Para nossa sorte, não precisaremos fazer a contagem minuciosa de instruções toda vez que precisarmos da função de custo de um algoritmo, porque podemos fazer a análise assintótica.
Nesse tipo de análise, encontraremos uma curva de tendência aproximada ao desempenho do algoritmo. A análise baseia-se na extrapolação do conjunto de dados de entrada, fazendo-os tenderem ao infinito e permitindo que negligenciemos alguns termos de nossas equações. Em outras palavras, descartamos de nossas equações termos que crescem lentamente à medida que nosso conjunto de entradas tendem a infinito.
Para obtermos o comportamento assintótico de qualquer função, pegamos o termo de maior grau (maior crescimento) da equação, negligenciando todos os outros, inclusive o coeficiente multiplicador do termo de maior grau, vide ex.: 6n + 4, T(n) = n.
Um código sem laços de repetições terá seu comportamento assintótico com custo unitário fixo (1).
Figura 5.
Notações de análise assintótica
GRANDE-O (BIG-O) O(n)
Define o comportamento assintótico superior;
É o pior caso de um algoritmo;
Mais instruções sendo executadas.
GRANDE-ÔMEGA Ω (n)
Define o comportamento assintótico inferior;
É o melhor caso do algoritmo (caso ótimo);
Menos instruções sendo executadas.
GRANDE-THETA Θ (n)
Define o comportamento assintótico firme;
Caso médio de um algoritmo;
É o comportamento considerando a grande maioria dos casos.
Recursão
Recursão é o processo de chamada de uma função por si mesma, um grande exemplo é o fatorial. As chamadas da função por ela mesma são colocadas numa pilha e são resolvidas posteriormente.
Figura 6 – Pilha de chamadas.
Complexidade assintótica
A complexidade padrão Big-O para recursividade será sempre de O (log n).