Introdução a algoritmos

Paginas de algoritmos:

1. Selection Sort
2. Merge Sort
3. Algoritmo do caminho mínimo
4. Técnica backtracking

Introdução

Um dos principais conceitos da ciência da computação é o conceito de algoritmos. Mas, afinal, o que vem a ser um algoritmo?

Quando precisamos escrever um programa de computador que realize uma determinada função, esse programa requer pelo menos uma solução para que a devida função seja realizada. O algoritmo é uma representação da solução. É muito comum um algoritmo ser escrito em uma linguagem chamada pseudocódigo. Onde, se tenta criar uma solução generalizada, independente de linguagem de programação.

Vamos a um exemplo:

Vamos supor que você precise escrever um programa que, dado um vetor de inteiros qualquer, o programa deve imprimir o menor inteiro do vetor. Veja abaixo um possível algoritmo para a solução do problema:

  calcula_menor( vetor, n )       
    menor = INFINITY              
    for i = 0 to n-1 do           
       if ( vetor[ i ] < menor )  
         menor = vetor[ i ]       
    return menor;                 

O algoritmo acima é a representação em pseudocódigo de uma função/método que retorne o menor inteiro armazenado em um vetor de 'n' elementos.

Complexidade do algoritmo

Após a criação de um algoritmo, se pode querer estimar qual o tempo necessário para a execução do algoritmo. Então, podemos considerar que a atribuição a variável menor, na linha 2, leve um tempo 'c1' para ser executado e, o for da linha 3, tem a inicialização da variável 'i' que também leva um tempo 'c1' para se executada, o incremento da variável 'i' que acontece a cada iteração do laço, isto é, 'n' vezes e a execução da condição de parada que acontece 'n+1' vezes. O conteúdo do for, também é executado 'n' vezes. Então temos:

    T(n)=c1 + c1 + (n*c2) + ((n+1)*c3) + (n*c4) + c5
    T(n)=2*c1 + c2*n + c3*n + c3 + c4*n + c5
    T(n)=(c2 + c3 + c4)*n + 2*c1 + c3 + c5
    T(n)=a*n + b

O termo de T(n) de maior grau é 'a*n', logo a complexidade do algoritmo, também conhecida como ordem de crescimento, é:

    θ(n)

Para mais detalhes e aprofundamento sobre a o tema: ordem de crescimento e complexidade de algoritmos, recomendo estudar o conteúdo da página abaixo:

Artigo sobre o Selection Sort.

Finalizando

Aqui finaliza essa breve introdução sobre algoritmos. Para maior aprofundamento no assunto, você pode acessar os outros artigos clicando aqui.