Mês: janeiro 2015

2.2 – Análise de Algoritmos

meitcherDeixe um comentário

Analisar um algoritmo é algo fundamental para qualquer desenvolvedor, independente da linguagem. As métricas de análise podem ser várias e a maioria delas são válidas. Nesse capítulo é apresentada a análise do tempo de execução, apenas de modo informal através da ordem de crescimento e cálculo dos custos em cada parte do algoritmo.

Continuar lendo →

1 – Fundamentos – Problemas

meitcher2 Comentários

1.1 – Comparação entre tempos de execução:

Para cada função f(n) e cada tempo t na tabela a seguir, determine o maior tamanho de n de um problema que pode ser resolvido no tempo t, considerando que o algoritmo para resolver o problema demore f(n) microssegundos.

1 seg. 1 min. 1 hora 1 dia 1 mês 1 ano 1 século
lg n 2^{10^{6}} 2^{6 \times 10^7} 2^{36 \times 10^8} 2^{864 \times 10^8} 2^{2592 \times 10^9} 2^{31104 \times 10^{13}} 2^{31104 \times 10^{15}}
\sqrt{n} 10^{12} 36 \times 10^{14} 1296 \times 10^{16} 746496 \times 10^{16} 6718464 \times 10^{18} 967458816 \times 10^{26} 967458816 \times 10^{30}
n 10^6 6 \times 10^7 36 \times 10^8 864 \times 10^8 2592 \times 10^9 31104 \times 10^{13} 31104 \times 10^{15}
nlg n 62746 2801417 133378058 2755147513 71870856404 787089606198 67699498463600
n^2 10^3 \sqrt{6} \times 10^{3.5} 6 \times 10^4 \sqrt{864} \times 10^4 \sqrt{2592} \times 10^{4.5} \sqrt{31104} \times 10^{13/2} \sqrt{31104} \times 10^{15/2}
n^3 10^2 \sqrt[3]{6} \times 10^{7/3} \sqrt[3]{36} \times 10^{8/3} \sqrt[3]{864} \times 10^{8/3} \sqrt[3]{2592} \times 10^{3} \sqrt[3]{31104} \times 10^{10/3} \sqrt[3]{31104} \times 10^{5}
2^n 20 25 31 36 41 44 51
n! 9 11 12 13 15 16 17

Cálculos realizados para chegar na tabela acima foram os seguintes:

Continuar lendo →

1.1 – Algoritmos

meitcherDeixe um comentário

Então pessoal, começarei com o primeiro capítulo do CLRS. Para quem não conhece, o CLRS é o livro Introdução à Algoritmos, 3 edição, escrito pelo Cormem, Leiserson, Rivest e Stein. É amplamente utilizado nos cursos de graduação de computação e afins para cadeiras que envolvem elaboração de algoritmos.

O que é um algoritmo? Uma definição poderia ser descrita como: Qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída [1]. A formalização de algoritmo é universalmente conhecida e aceita como uma Máquina de Turing.

Continuar lendo →