Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algorítimos Computacionais (Complex Algoritimos (Notação (Ordem O (Exemplo…

- - - - Função de n
      - n - > Parâmetro Caract. do Algorít.
        
        Qdo n ˜= œ
        
        Assintótico
  - - - O(g(n)) Conj das Func.
        
        f(n)
        
        f1(n) = 2nˆ2 + 500 = O(nˆ2)
        
        f2(n) = 500n + 4000 = O(n)
    - - f (n) : ∃ constantes c e n0 tais que 0 ≤ f (n) ≤ cg(n) para n ≥ n0.
      - Mais explicitamente: f é assintoticamente não negativa se existe n0 tal que f(n) ≥ 0 para todo n maior que n0
      - Exemplo
        
        Exemplo 2: Suponha que f(n) = 2n² + 3n + 4 e g(n) = n². Observe que
        
        2n2 + 3n + 4 ≤ 2n2 + 3n2 + 4n2 = 9n2
        
        desde que n ≥ 1. Resumindo, f(n) ≤ 9 g(n) para todo n ≥ 1. Portanto, f(n) = Ο(g(n)).
      - Custo Alg. Pior Caso
        
        Alg. Nunca pior que O(n...)
        
        Lim. ASsint. Sup
      - O(1) Constante
        
        Número Fixo Execuções
      - O(log N) Logarít.
        
        1 Problema
        
        Em Menores Probs.
        
        Search Arvore Binaria
      - O(n) Linear
        
        Ops em cada elem da ent.
      - O(n Log n) Log Linear
        
        1 Prob em Menores
        
        Depois une tudo
      - O(nˆx) Plinom.
        
        Aninhamentos
      - O(2ˆn) Expon.
        
        Força Bruta
    - - f(n) : ∃ constantes c e n0 tais que 0 ≤ cg(n) ≤ f(n) para n ≥ n0
      - f está na ordem Omega de g e escrevemos f = Ω(g) se f(n) ≥ c · g(n)
      - Lim Inferior. Alg.
        
        Melhor caso
    - - Dizemos que f e g estão na mesma e escrevemos f = Θ(g) se f = Ο(g) e f = Ω(g)
      - f = Θ(g) significa que existe números positivos c e d tais que c g(n) ≤ f(n) ≤ d g(n)
  - - - Já Conhecido
  - - - Cota dp Algor. = Cota Inferior
    - - Tempo Relacionado ao Prob.
- - - - Raiz
        
        Galhos / FIlhos
        
        Folha/ Nó terminal
      - Ordem
        
        Num. Max Galhos
        
        Por nó
    - - Percor. Cada Elem
        
        Unica vez
        
        Pre-Ordem
        
        Pai para Filho
        
        Pós Ordem
        
        Filho para Pai
        
        Em Ordem
        
        Filho a esq.
        
        Nó
        
        Filho a Direita
    - - Video
      - Lógica Procura
        
        Menor -> Esquerda
        
        Maior -> DIreita