ATPS - Análise e Complexidade de Algoritmos

...

Na área de análise de algoritmos existem dois tipos de problemas bem distintos, conforme apontou Knuth (1971):

- Análise de um algoritmo particular; e

- Análise de uma classe de algoritmo.

Quando determinamos que o custo de um algoritmo é igual ao menor custo possível, então é possível concluir que o algoritmo é ótimo para a medida de custo considerada.

- Medida de Complexidade de Algoritmo Ômicron

A complexidade de um algoritmo depende da quantidade de vezes que será executado sua operação elementar, tais quais podem variam de acordo com a entrada de tamanho n.

Sugerido por Knuth (1968) uma notação para dominação assintótica, O (ômicron) é utilizado para expressar comparativamente o crescimento assintótico e representa a velocidade com que a função tende ao infinito. Representar a medida do pior caso possível, ou o mais demorado, baseando-se no tempo de execução sobre todas as entradas de tamanho n. É o método mais fácil de se obter.

Dado um arquivo com n registros, sendo cada registro uma chave única, e dado um problema localizar uma chave qualquer no arquivo, podemos considerar que o pior caso é f(n) ou O(n) (chave é igual ao último registro ou é inexistente).

- Implementação do Algoritmo

Algoritmo desenvolvido em C++ que realiza o tratamento de uma dada variável do tipo string, removendo alguns caracteres específicos que estão acentuados.

O algoritmo implementa declarações e declarações simples, laços e laços aninhados e expressões condicionais if-then-else.

ENTRADA: “José Mário da Silva Mourão”.

SAÍDA: “Jose Mario da Silva Mourao”.

#include

#include

#include

#include

using namespace std;

string RemoverAcentuacao(string texto) {

//Caracteres que o algoritmo deve considerar como proibidos...

string caracteresProibidos = "áéíóúãõÁÉÍÓÚÃÕ";

//Caracteres de troca...

string caracteresPermitidos = "aeiouaoAEIOUAO";

//Variável que armazena o tamanho do texto passado como argumento...

int nTexto = texto.size();

//Variável que armazena o tamanho da constante de

//caracteres proibidos...

int nProibidos = caracteresProibidos.size();

//Variável utilizada para guardar o caractere

//que está sendo analisado...

char caractere;

//Variável que será retornada pelo algoritmo...

string result;

//1º Laço: deve percorrer todos os caracteres

//do texto passado como argumento...

for(int i = 0; i

caractere = texto[i];

//2º Laço: percorre a constante de caracteres proibidos

//checando por comparação, se o caractere analisado é

//um caractere proibido ou não...

for(int j = 0; j

//Se o caractere analisado for um caractere proibido,

//então deve ser substituído por um caractere permitido

//relativo – mesma posição nos vetores;

if (caractere == caracteresProibidos[j])

{

caractere = caracteresPermitidos[j];

break;

}

}

//Concatenação da string que será retornada com o caractere

//analisado e devidamente tratado...

result += caractere;

}

//Retorno do algoritmo...

return result;

}

int main() {

setlocale(LC_ALL, "Portuguese");

string teste = "José Mário João";

cout

cout

cin.get();

return EXIT_SUCCESS;

}

---------------------------------------------------------------

- Algoritmos de Ordenação

Algoritmo de ordenação constituem bons exemplos de como resolver problemas utilizando computadores, Ziviani (2004).

Ordenar corresponde ao processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente. O Objetivo principal da ordenação é facilitar a recuperação posterior dos dados, tornando as buscas mais eficientes.

- Ordenação por Seleção

O algoritmo percorre a lista de itens, selecionando um elemento de cada vez e colocando-o na posição correta conforme a ordenação (crescente ou decrescente). Sua principal vantagem é o bom desempenho em listas pequenas, e também não consome muito espaço, pois não necessita de mais memória para armazenamento além do já ocupado pela lista.

A principal desvantagem deste algoritmo de ordenação está