ATPS Complexidade

Analise Assintotica: É um método de descrever o comportamento de limite.

Exemplos incluem o desempenho de algoritmos quando aplicados a um volume muito grande de dados de entrada

Análise de Algoritmo: Tempo de processamento em função dos dados de entrada, espaço de memória, cumprimento total do código, robustez, correta obtenção do resultado pretendido.

Porquê o estudo da Complexidade?: Escolher o algoritmo mais eficiente, desenvolver algoritmos mais eficientes, complexidade computacional viavel ou nao.

Tipos de complexidade: Espacial (Representa espaço de memória usado para executar o algoritmo), Temporal (Tempo Real: Tempo necessário à execução do algoritmo, Numreo de instruções necessárias à execução.`

Medidas de Análise: Independete da plataforma, Tempo de execução (t = F(n)), conjunto de operações, Custo, Espaço em memória.

Operações primitivas: Atribuição a variaveis, chamada de métodos, op. Aritmética, comparação entre numeros, Array, acesso a objeto, retorno de um método

Notações assintóticas:

Complexidade do algoritmo: Melhor caso, caso medio, pior caso.

Melhor Caso: Definido pela letra grega (Ômega), é o menor tempo de execu

Caso Médio: Definido pela letra grega (Theta), das três é a mais dificil de se determinar . Obtem a média dos tempos de execução de todas as entradas de tamanho N ou baseado em probabilidade de determinada condição ocorrer.

Pior Caso: Determinado pela letra grega O (Ômicron), é o método mais fácil de se obter. Basea-se no maior tempo de execução sobre todas as entradas de tamanho N.

Ordenação

BUBLLE

void bubble(int v[], int tam) {

int i, aux,trocou;

do {

tam--;

trocou = 0; //usado para otimizar o algoritmo

for(i = 0; i < tam; i++)

if(v[i] > v[i + 1]) {

}

} while(trocou);

}

Selection

void selection_sort(int num[], int tam) {

int i, j, min;

for (i = 0; i < (tam-1); i++) {

min = i;

for (j = (i+1); j < tam; j++) {

if(num[j] < num[min]) {

min = j;

}

}

if (i != min) {

int swap = num[i];

num[i] = num[min];