Algorithm Analysis

Meer zoals dit

DA001 - Princípios da Administração Publica

door Eduardo Savarro

FUNÇÕES PSÍQUICAS

door ednara teixeira

China

door Danielle Bandeira

MEMÓRIA

door Danilo Messias

Algorithm Analysis

Funções de Multiplicação

Os relacionamentos Big Oh são transitivos.

Transitividade * Se f(n)=O(g(n)) e g(n)=O(h(n)), então f(n)=O(h(n))

Multiplicação de Funções: ambas as funções são importantes, a menos que uma delas seja dominante.

Multiplicação por funções * O(f(n))*O(g(n)) → O(f(n)*g(n)) * Ω(f(n))*Ω(g(n)) → Ω(f(n)*g(n)) * Θ(f(n))* Θ(g(n)) → Θ(f(n)*g(n))

A multiplicação por uma constante não afeta o comportamento assintótico de uma função.

Multiplicação por constante * O(c · f(n)) → O(f(n)) * Ω(c · f(n)) → Ω(f(n)) * Θ(c · f(n)) → Θ(f(n))

Relações de Dominância

Classes de dominância: * Constante * Logarítmica * Linear * Super linear * Quadrática * Cúbica * Exponencial * Fatorial

Agrupa funções em classes. Funções da mesma classe têm a mesma ordem de crescimento. Funções de classes diferentes são diferentes em relação à notação.

Taxas de Crescimento e Relações de Dominância

Ignora as diferenças entre constantes multiplicativas. As diferenças não afetam o crescimento.

Notação "Big Oh"

Definições f(n) = O(g(n)) f(n) = Ω(g(n)) f(n) = Θ(g(n))

Simplifica complexidades de tempo. Ignora detalhes intricados. Foca nas tendências gerais. Importante para comparar a eficiência de algoritmos. Análise simplificada.

Melhor, Pior e Complexidade de Caso Médio

A notação "Big Oh" simplifica a complexidades de tempo.

na prática a complexidade do Pior Caso é a mais útil.

Caso Médio: Número médio de passos.

Pior Caso: Número máximo de passos.

Melhor Caso: Número mínimo de passos.

O Modelo de Computação RAM

Utilidades: Entender como um algoritmo funcionará em um computador real. Análise de algoritmos independente da máquina.

Computador hipotético. Projeta algoritmos independentes de máquina.

Características: Operações simples levam um passo de tempo. Acessos à memória levam um passo de tempo. Loops e sub-rotinas envolvem várias operações. Memória é ilimitada.