Algorithm Analysis

Mere som dette

RH

af Francielle Vertelo

Princípios do Controle na Administração Pública Estatal

af Marcia Santos Viera

Arquitetura de Computadores

af Gustavo Belmonte

Como diminuir o consumo de água em SP?

af Pedro Germano

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.