Please enable JavaScript.

Coggle requires JavaScript to display documents.

Selection sort e Bubble sort, Dividir e conquistar, Decrescer e conquistar…

- - - - Pertence a \(\Theta(n^2)\) para todos os seus inputs
  - - - Esse número é \(n-1\)
        
        Uma para cada repetição do loop
- - - - Pertence a \(\Theta(n^2)\)
  - - - Pertence a \(\Theta(n^2)\)
- - - - \(T(n)=a\cdot T(\frac{n}{b})+f(n)\)
        
        \(f(n)\) é uma função que marca o tempo necessário para dividir o problema de tamanho \(n\) em problemas menores de tamanho \(\frac{n}{b}\) e combinar suas soluções
- - - - Resultados análogos para \(O \text{ e }\Omega\)
- - - - 2 ponteiros são inicializados para apontar para o primeiro elemento de cada um dos arrays que estão sendo unidos
      - Os elementos que estão sendo apontados são comparados e o menor é adicionado a um novo array
      - O índice do menor elemento é incrementado para apontar para o sucessor imediato no array
      - Repetir a operação até que um dos array seja esgotado e, depois, adicionar os elementos restantes ao novo array
      - Eficiência
        
        No pior caso, é: \(\left(n\cdot\log_2n\ -n-1\right)\)
        
        Pertence a \(\Theta(n\log n)\)
- - - - Geralmente, essa constante é igual a 1
    - - Relação entre a solução para uma instância de tamanho \(n\) e uma instância de tamanho \(n-1\)
        
        \(a^n=a^{n-1}\cdot a\)
        
        \(f(n)=a^n\) computada top down
        
        Definição recursiva
        
        \(f(n)=a^n\) computada bottom up
        
        Multiplicar \(1\) por \(a\ n\) vezes
  - - - Geralmente, esse fator é igual a 2
    - - Se a instância de tamanho \(n\) é para computar \(a^n\), a instância da metade do tamanho é computar \(a^{n/2}\)
        
        A relação é \((a^{n/2})^2\)
        
        Não funciona para \(n\) ímpar
        
        Estamos considerando expoentes inteiros
        
        Se \(n\) for ímpar, é preciso computar \(a^{n-1}\) e depois multiplicar o resultado por \(a\)
        
        Calculando \(a^n\) de forma recursiva e medindo a eficiência
        
        O algoritmo deve pertencer a \(\Theta(\log n)\)
        
        Em cada iteração, o tamanho é reduzido pela metade em uma ou duas multiplicação
  - - - \(MDC(m, n) = MDC(n,\ m\text{ mod }n)\)
        
        O valor do segundo argumento é sempre menor que o valor do primeiro, mas ele não decresce por um valor constante nem por um fator constante
- - - - O número de comparações é \(\frac{n\left(n-1\right)}{2}\)
        
        Pertence a \(\Theta(n)\)